TY - JOUR
T1 - Tournaments and the strong Erdős–Hajnal Property
AU - Berger, Eli
AU - Choromanski, Krzysztof
AU - Chudnovsky, Maria
AU - Zerbib, Shira
N1 - Funding Information:
Eli Berger, Maria Chudnovsky and Shira Zerbib were supported by US-Israel BSF grant, Israel2016077.Maria Chudnovsky was supported by National Science Foundation, United States of America grant DMS-1763817. This material is based upon work supported in part by the U. S. Army Research Laboratory and the U. S. Army Research Office under Grant Number W911NF1610404.Shira Zerbib was supported by National Science Foundation, United States of America grant DMS-1953929.
Publisher Copyright:
© 2021 Elsevier Ltd
PY - 2022/2
Y1 - 2022/2
N2 - A conjecture of Alon, Pach and Solymosi, which is equivalent to the celebrated Erdős–Hajnal Conjecture, states that for every tournament S there exists ɛ(S)>0 such that if T is an n-vertex tournament that does not contain S as a subtournament, then T contains a transitive subtournament on at least nɛ(S) vertices. Let C5 be the unique five-vertex tournament where every vertex has two inneighbors and two outneighbors. The Alon–Pach–Solymosi conjecture is known to be true for the case when S=C5. Here we prove a strengthening of this result, showing that in every tournament T with no subtorunament isomorphic to C5 there exist disjoint vertex subsets A and B, each containing a linear proportion of the vertices of T, and such that every vertex of A is adjacent to every vertex of B.
AB - A conjecture of Alon, Pach and Solymosi, which is equivalent to the celebrated Erdős–Hajnal Conjecture, states that for every tournament S there exists ɛ(S)>0 such that if T is an n-vertex tournament that does not contain S as a subtournament, then T contains a transitive subtournament on at least nɛ(S) vertices. Let C5 be the unique five-vertex tournament where every vertex has two inneighbors and two outneighbors. The Alon–Pach–Solymosi conjecture is known to be true for the case when S=C5. Here we prove a strengthening of this result, showing that in every tournament T with no subtorunament isomorphic to C5 there exist disjoint vertex subsets A and B, each containing a linear proportion of the vertices of T, and such that every vertex of A is adjacent to every vertex of B.
UR - http://www.scopus.com/inward/record.url?scp=85117210171&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85117210171&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2021.103440
DO - 10.1016/j.ejc.2021.103440
M3 - Article
AN - SCOPUS:85117210171
SN - 0195-6698
VL - 100
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
M1 - 103440
ER -