We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Independent sets in hypergraphs omitting an intersection.
- Authors
Bohman, Tom; Liu, Xizhi; Mubayi, Dhruv
- 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) $$.
- Subjects
INDEPENDENT sets; HYPERGRAPHS; RAMSEY theory; RAMSEY numbers; STOCHASTIC processes
- Publication
Random Structures & Algorithms, 2022, Vol 61, Issue 3, p493
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.21071