Independent sets in hypergraphs omitting an intersection. Issue 3 (14th December 2021)

• Record Type: Journal Article
• Authors: Bohman, Tom; Liu, Xizhi; Mubayi, Dhruv
• Is Part Of: Random structures & algorithms. Volume 61:Issue 3(2022)
• Page Start: 493
• Page End: 519
• Publication Date: 2021-12-14
• Subjects: independent sets -- L‐intersecting families -- pseudorandom hypergraphs -- random greedy processes; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21071
• Languages: English
• ISSNs: 1042-9832

Abstract

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) $$ .