Search

A triple system is cancellative if it does not contain three distinct sets A , B , C such that the symmetric difference of A and B is contained in C. We show that every cancellative triple system H that satisfies a particular inequality between the sizes of H and its shadow must be structurally close to the balanced blowup of some Steiner triple system. Our result contains a stability theorem for cancellative triple systems due to Keevash and Mubayi as a special case. It also implies that the boundary of the feasible region of cancellative triple systems has infinitely many local maxima, thus giving the first example showing this phenomenon. [ABSTRACT FROM AUTHOR]

Grosu (2016) [11] asked if there exist an integer r ≥ 3 and a finite family of r -graphs whose Turán density, as a real number, has (algebraic) degree greater than r − 1. In this note we show that, for all integers r ≥ 3 and d , there exists a finite family of r -graphs whose Turán density has degree at least d , thus answering Grosu's question in a strong form. [ABSTRACT FROM AUTHOR]

The feasible region Ω ind (F) of a graph F is the collection of points (x , y) in the unit square such that there exists a sequence of graphs whose edge densities approach x and whose induced F -densities approach y. A complete description of Ω ind (F) is not known for any F with at least four vertices that is not a clique or an independent set. The feasible region provides a lot of combinatorial information about F. For example, the supremum of y over all (x , y) ∈ Ω ind (F) is the inducibility of F and Ω ind (K r) yields the Kruskal-Katona and clique density theorems. We begin a systematic study of Ω ind (F) by proving some general statements about the shape of Ω ind (F) and giving results for some specific graphs F. Many of our theorems apply to the more general setting of quantum graphs. For example, we prove a bound for quantum graphs that generalizes an old result of Bollobás for the number of cliques in a graph with given edge density. We also consider the problems of determining Ω ind (F) when F = K r − , F is a star, or F is a complete bipartite graph. In the case of K r − our results sharpen those predicted by the edge-statistics conjecture of Alon et al. while also extending a theorem of Hirst for K 4 − that was proved using computer aided techniques and flag algebras. The case of the 4-cycle seems particularly interesting and we conjecture that Ω ind (C 4) is determined by the solution to the triangle density problem, which has been solved by Razborov. [ABSTRACT FROM AUTHOR]

We present a method which provides a unified framework for most stability theorems that have been proved in graph and hypergraph theory. Our main result reduces stability for a large class of hypergraph problems to the simpler question of checking that a hypergraph H with large minimum degree that omits the forbidden structures is vertex-extendable. This means that if v is a vertex of H and H − v is a subgraph of the extremal configuration(s), then H is also a subgraph of the extremal configuration(s). In many cases vertex-extendability is quite easy to verify. We illustrate our approach by giving new short proofs of hypergraph stability results of Pikhurko, Hefetz-Keevash, Brandt-Irwin-Jiang, Bene Watts-Norin-Yepremyan and others. Since our method always yields minimum degree stability, which is the strongest form of stability, in some of these cases our stability results are stronger than what was known earlier. Along the way, we clarify the different notions of stability that have been previously studied. [ABSTRACT FROM AUTHOR]

Let F be a family of r -uniform hypergraphs. The feasible region Ω (F) of F is the set of points (x , y) in the unit square such that there exists a sequence of F -free r -uniform hypergraphs whose shadow density approaches x and whose edge density approaches y. The feasible region provides a lot of combinatorial information, for example, the supremum of y over all (x , y) ∈ Ω (F) is the Turán density π (F) , and Ω (∅) gives the Kruskal-Katona theorem. We undertake a systematic study of Ω (F) , and prove that Ω (F) is completely determined by a left-continuous almost everywhere differentiable function; and moreover, there exists an F for which this function is not continuous. We also extend some old related theorems. For example, we generalize a result of Fisher and Ryan to hypergraphs and extend a classical result of Bollobás by almost completely determining the feasible region for cancellative triple systems. [ABSTRACT FROM AUTHOR]