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]

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]

A hypergraph $\mathcal{F}$ is non-trivial intersecting if every pair of edges in it have a nonempty intersection, but no vertex is contained in all edges of $\mathcal{F}$. Mubayi and Verstraëte showed that for every $k \ge d+1 \ge 3$ and $n \ge (d+1)k/d$ every $k$ -graph $\mathcal{H}$ on $n$ vertices without a non-trivial intersecting subgraph of size $d+1$ contains at most $\binom{n-1}{k-1}$ edges. They conjectured that the same conclusion holds for all $d \ge k \ge 4$ and sufficiently large $n$. We confirm their conjecture by proving a stronger statement. They also conjectured that for $m \ge 4$ and sufficiently large $n$ the maximum size of a $3$ -graph on $n$ vertices without a non-trivial intersecting subgraph of size $3m+1$ is achieved by certain Steiner triple systems. We give a construction with more edges showing that their conjecture is not true in general. [ABSTRACT FROM AUTHOR]

A k‐uniform hypergraph with n vertices is an (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐omitting system if it has no two edges with intersection size ℓ$$ \ell $$. If in addition it has no two edges with intersection size greater than ℓ$$ \ell $$, then it is an (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐system. Rödl and Šiňajová proved a sharp lower bound for the independence number of (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐systems. We consider the same question for (n,k,ℓ)$$ \left(n,k,\ell \right) $$‐omitting systems. Our proofs use adaptations of the random greedy independent set algorithm, and pseudorandom graphs. We also prove related results where we forbid more than two edges with a prescribed common intersection size leading to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number rk(F,t)$$ {r}_k\left(F,t\right) $$, where F is the k‐uniform Fan. The behavior is quite different than the case k=2$$ k=2 $$ which is the classical Ramsey number r(3,t)$$ r\left(3,t\right) $$. [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]

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]