Homogeneous sets in hypergraphs with forbidden order-size pairsThe well-known Erdős-Hajnal conjecture states that for any graph $F$,
there exists $ε>0$ such that every $n$-vertex graph $G$ that contains no
induced copy of $F$ has a homogeneous set of size at least $n^ε$. 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\leq f \leq \binom{m}{2}$, 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$. For all $S$ we determine if the growth rate is
polylogarithmic. Several open problems remain.
arxiv.org