1. Independent sets in hypergraphs omitting an intersection.
- Author
-
Bohman, Tom, Liu, Xizhi, and Mubayi, Dhruv
- Subjects
INDEPENDENT sets ,HYPERGRAPHS ,RAMSEY theory ,RAMSEY numbers ,STOCHASTIC processes - 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 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]
- Published
- 2022
- Full Text
- View/download PDF