Premium
Independent sets in hypergraphs omitting an intersection
Author(s) -
Bohman Tom,
Liu Xizhi,
Mubayi Dhruv
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21071
Subject(s) - hypergraph , intersection (aeronautics) , combinatorics , mathematical proof , ramsey's theorem , mathematics , ramsey theory , independent set , discrete mathematics , independence (probability theory) , upper and lower bounds , pseudorandom number generator , set (abstract data type) , independence number , graph , computer science , algorithm , mathematical analysis , statistics , geometry , engineering , aerospace engineering , programming language
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 numberr k ( F , t ) $$ {r}_k\left(F,t\right) $$ , where F is the k ‐uniform Fan. The behavior is quite different than the casek = 2 $$ k=2 $$ which is the classical Ramsey numberr ( 3 , t ) $$ r\left(3,t\right) $$ .