Independent sets in hypergraphs omitting an intersection. Issue 3 (14th December 2021) - Bohman, Tom
Abstract: 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 r k ( 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) $$ .