Disperse Hypergraphs

Abstract

For $\ell \ge 3$, an $\ell$-uniform hypergraph is disperse if the number of edges induced by any set of $\ell +1$ vertices is 0, 1, $\ell$ or $\ell +1$. We show that every disperse $\ell$-uniform hypergraph on $n$ vertices contains a clique or independent set of size $n^{{\Omega }_{\ell }(1)}$, answering a question of the first author and Tomon. To this end, we prove several structural properties of disperse hypergraphs.