Homogeneous sets in hypergraphs with forbidden order-size pairs

MaRDI QIDQ6429877zbMATH OpenFDO

Authors Maria Axenovich, Dhruv Mubayi, Lea Weber

Publication date 16 March 2023

Mathematics Subject Classification ID

Combinatorics (05-XX)

Abstract: The well-known ErdH{o}s-Hajnal conjecture states that for any graph $F$, there exists $epsilon>0$ such that every $n$-vertex graph $G$ that contains no induced copy of $F$ has a homogeneous set of size at least $n^{epsilon}$. We consider a variant of the ErdH{o}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 $$, then we obtain large homogeneous sets. For triple systems, in the first nontrivial case $m=4$, for every $Ssubseteq0,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.

This page was built for publication: Homogeneous sets in hypergraphs with forbidden order-size pairs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429877)