Tournaments and the strong Erdős–Hajnal Property. (February 2022)

• Record Type: Journal Article
• Authors: Berger, Eli; Choromanski, Krzysztof; Chudnovsky, Maria; Zerbib, Shira
• Is Part Of: European journal of combinatorics. Volume 100(2022)
• Publication Date: 2022-02
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2021.103440
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: 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 C 5 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 = C 5 . Here we prove a strengthening of this result, showing that in every tournament T with no subtorunament isomorphic to C 5 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 .