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 -