TY - JOUR
T1 - On the Erdős–Hajnal conjecture for six-vertex tournaments
AU - Berger, Eli
AU - Choromanski, Krzysztof
AU - Chudnovsky, Maria
N1 - Publisher Copyright:
© 2018 Elsevier Ltd
PY - 2019/1
Y1 - 2019/1
N2 - A celebrated unresolved conjecture of Erdős and Hajnal states that for every undirected graph H there exists ϵ(H)>0 such that every undirected graph on n vertices that does not contain H as an induced subgraph contains a clique or stable set of size at least nϵ(H). The conjecture has a directed equivalent version stating that for every tournament H there exists ϵ(H)>0 such that every H-free n-vertex tournament T contains a transitive subtournament of order at least nϵ(H). We say that a tournament is prime if it does not have nontrivial homogeneous sets. So far the conjecture was proved only for some specific families of prime tournaments (Berger et al., 2014; Choromanski, 2015 [3]) and tournaments constructed according to the so-called substitution procedure (Alon et al., 2001). In particular, recently the conjecture was proved for all five-vertex tournaments (Berger et al. 2014), but the question about the correctness of the conjecture for all six-vertex tournaments remained open. In this paper we prove that all but at most one six-vertex tournament satisfy the Erdős–Hajnal conjecture. That reduces the six-vertex case to a single tournament.
AB - A celebrated unresolved conjecture of Erdős and Hajnal states that for every undirected graph H there exists ϵ(H)>0 such that every undirected graph on n vertices that does not contain H as an induced subgraph contains a clique or stable set of size at least nϵ(H). The conjecture has a directed equivalent version stating that for every tournament H there exists ϵ(H)>0 such that every H-free n-vertex tournament T contains a transitive subtournament of order at least nϵ(H). We say that a tournament is prime if it does not have nontrivial homogeneous sets. So far the conjecture was proved only for some specific families of prime tournaments (Berger et al., 2014; Choromanski, 2015 [3]) and tournaments constructed according to the so-called substitution procedure (Alon et al., 2001). In particular, recently the conjecture was proved for all five-vertex tournaments (Berger et al. 2014), but the question about the correctness of the conjecture for all six-vertex tournaments remained open. In this paper we prove that all but at most one six-vertex tournament satisfy the Erdős–Hajnal conjecture. That reduces the six-vertex case to a single tournament.
UR - http://www.scopus.com/inward/record.url?scp=85052937305&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85052937305&partnerID=8YFLogxK
U2 - 10.1016/j.ejc.2018.08.007
DO - 10.1016/j.ejc.2018.08.007
M3 - Article
AN - SCOPUS:85052937305
SN - 0195-6698
VL - 75
SP - 113
EP - 122
JO - European Journal of Combinatorics
JF - European Journal of Combinatorics
ER -