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]

The classical Kruskal–Katona theorem gives a tight upper bound for the size of an r -uniform hypergraph H as a function of the size of its shadow. Its stability version was obtained by Keevash who proved that if the size of H is close to the maximum with respect to the size of its shadow, then H is structurally close to a complete r -uniform hypergraph. We prove similar stability results for two classes of hypergraphs whose extremal properties have been investigated by many researchers: the cancellative hypergraphs and hypergraphs without expansion of cliques. [ABSTRACT FROM AUTHOR]

A fundamental result in extremal set theory is Katona's shadow intersection theorem, which extends the Kruskal–Katona theorem by giving a lower bound on the size of the shadow of an intersecting family of k -sets in terms of its size. We improve this classical result and a related result of Ahlswede, Aydinian and Khachatrian by proving tight bounds for families that can be quite small. For example, when k = 3 our result is sharp for all families with n points and at least 3 n − 7 triples. Katona's theorem was extended by Frankl to families with matching number s. We improve Frankl's result by giving tight bounds for large n. [ABSTRACT FROM AUTHOR]

We present new short proofs to both the exact and the stability result of two extremal problems. The first result is about the extension of Turán's theorem to hypergraphs, and the second result is about cancellative hypergraphs. Our proofs are concise and straightforward, but give a sharper version of stability theorems to both problems. [ABSTRACT FROM AUTHOR]

Let 3 ≤ d ≤ k and ν ≥ 0 be fixed. Let F ⊂ [ n ] k . The matching number of F , denoted by ν (F) , is the maximum number of pairwise disjoint sets in F. F is d -cluster-free if it does not contain d sets with union of size at most 2 k and empty intersection. In this paper, we give a lower bound and an upper bound for the maximum size of a d -cluster-free family with a matching number at least ν + 1. In particular, our result of the case ν = 1 settles a conjecture of Mammoliti and Britz. We also introduce a Turán problem in hypergraphs that allows multiple edges, which may be of independent interest. [ABSTRACT FROM AUTHOR]