2023/03/16 by Maria Axenovich, Axenovich, Maria, Dhruv Mubayi +3
Computer Science · Engineering · Mathematics · #05 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2303.09578
openalex publication_date 2023/03/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The 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≤ f ≤ \binomm2, then we obtain large homogeneous sets. For triple systems, in the first nontrivial case m=4, for every S ⊆ \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.