Large cliques or co-cliques in hypergraphs with forbidden order-size pairs

Abstract

The well-known Erdős-Hajnal conjecture states that for any graph $F$, there exists $\hat{I}\mu >0$ such that every $n$-vertex graph $G$ that contains no induced copy of $F$ has a homogeneous set of size at least $n^{\hat{I}}\mu$. We consider a variant of the Erdős-Hajnal problem for hypergraphs where we forbid a family of hypergraphs described by their orders and sizes. For graphs, we observe that if we forbid induced subgraphs on $m$ vertices and $f$ edges for any positive $m$ and $0\le f\le \left(\genfrac{}{}{0ex}{}{m}{2}\right)$, then we obtain large homogeneous sets. For triple systems, in the first nontrivial case $m=4$, for every $S\subseteq \{0,1,2,3,4\}$, we give bounds on the minimum size of a homogeneous set in a triple system where the number of edges spanned by every four vertices is not in $S$. In most cases the bounds are essentially tight. We also determine, for all $S$, whether the growth rate is polynomial or polylogarithmic. Some open problems remain.

A preliminary version of this manuscript appeared as arXiv:2303.09578