2021/01/12 by Bohman, Tom, Liu, Xizhi, Mubayi, Dhruv
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2101.04258
A k-uniform hypergraph with n vertices is an (n,k,ℓ)-omitting system if it does not contain two edges whose intersection has size exactly ℓ. If in addition it does not contain two edges whose intersection has size greater than ℓ, then it is an (n,k,ℓ)-system. Rödl and Šiňajová proved a lower bound for the independence number of (n,k,ℓ)-systems that is sharp in order of magnitude for fixed 2 ≤ ℓ ≤ k-1. We consider the same question for the larger class of (n,k,ℓ)-omitting systems. For k≤ 2ℓ+1, we believe that the behavior is similar to the case of (n,k,ℓ)-systems and prove a nontrivial lower bound for the first open case ℓ=k-2. For k>2ℓ+1 we give new lower and upper bounds which show that the minimum independence number of (n,k,ℓ)-omitting systems has a very different behavior than for (n,k,ℓ)-systems. Our lower bound for ℓ=k-2 uses some adaptations of the random greedy independent set algorithm, and our upper bounds (constructions) for k> 2ℓ+1 are obtained from some pseudorandom graphs. We also prove some related results where we forbid more than two edges with a prescribed common intersection size and this leads to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number rk(Fk,t), where Fk is the k-uniform Fan. Here the behavior is quite different than the case k=2 which reduces to the classical graph Ramsey number r(3,t).