A $k$-uniform hypergraph with $n$ vertices is an $(n,k,ell)$-omitting system if it does not contain two edges whose intersection has size exactly $ell$. If in addition it does not contain two edges whose intersection has size greater than $ell$, then it is an $(n,k,ell)$-system. R{o}dl and v{S}iv{n}ajov{a} proved a lower bound for the independence number of $(n,k,ell)$-systems that is sharp in order of magnitude for fixed $2 le ell le k-1$. We consider the same question for the larger class of $(n,k,ell)$-omitting systems. For $kle 2ell+1$, we believe that the behavior is similar to the case of $(n,k,ell)$-systems and prove a nontrivial lower bound for the first open case $ell=k-2$. For $k>2ell+1$ we give new lower and upper bounds which show that the minimum independence number of $(n,k,ell)$-omitting systems has a very different behavior than for $(n,k,ell)$-systems. Our lower bound for $ell=k-2$ uses some adaptations of the random greedy independent set algorithm, and our upper bounds (constructions) for $k> 2ell+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 $r_{k}(F^{k},t)$, where $F^{k}$ 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)$.
Download