A Caltech Library Service

Two Erdős–Hajnal-type theorems in hypergraphs

Amir, Michal and Shapira, Asaf and Tyomkyn, Mykhaylo (2021) Two Erdős–Hajnal-type theorems in hypergraphs. Journal of Combinatorial Theory. Series B, 146 . pp. 417-438. ISSN 0095-8956.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The Erdős–Hajnal Theorem asserts that non-universal graphs, that is, graphs that do not contain an induced copy of some fixed graph H, have homogeneous sets of size significantly larger than one can generally expect to find in a graph. We obtain two results of this flavor in the setting of r-uniform hypergraphs. A theorem of Rödl asserts that if an n-vertex graph is non-universal then it contains an almost homogeneous set (i.e. one with edge density either very close to 0 or 1) of size Ω(n). We prove that if a 3-uniform hypergraph is non-universal then it contains an almost homogeneous set of size Ω(log n). An example of Rödl from 1986 shows that this bound is tight. Let R_r(t) denote the size of the largest non-universal r-graph G so that neither G nor its complement contain a complete r-partite subgraph with parts of size t. We prove an Erdős–Hajnal-type stepping-up lemma, showing how to transform a lower bound for R_r(t) into a lower bound for R_(r+1)(t). As an application of this lemma, we improve a bound of Conlon–Fox–Sudakov by showing that R₃ (t)≥t^(Ω(t)).

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Additional Information:© 2020 Elsevier Inc. Received 4 January 2019, Available online 10 March 2020. We thank Benny Sudakov and the anonymous referees for helpful comments. Supported in part by ISF Grant 1028/16. Supported in part by ISF Grant 1028/16 and ERC Starting Grant 633509. Supported in part by ERC Starting Grant 633509.
Funding AgencyGrant Number
Israel Science Foundation1028/16
European Research Council (ERC)633509
Subject Keywords:Hypergraphs; Ramsey theory; Erdős-Hajnal
Record Number:CaltechAUTHORS:20200310-105936216
Persistent URL:
Official Citation:Michal Amir, Asaf Shapira, Mykhaylo Tyomkyn, Two Erdős–Hajnal-type theorems in hypergraphs, Journal of Combinatorial Theory, Series B, Volume 146, 2021, Pages 417-438, ISSN 0095-8956, (
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:101823
Deposited By: Tony Diaz
Deposited On:10 Mar 2020 18:11
Last Modified:11 Dec 2020 22:40

Repository Staff Only: item control page