TY - JOUR

T1 - Tournaments and the strong Erdős–Hajnal Property

AU - Berger, Eli

AU - Choromanski, Krzysztof

AU - Chudnovsky, Maria

AU - Zerbib, Shira

N1 - 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 -