Tournaments and the strong Erdős–Hajnal Property

Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Shira Zerbib

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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

Original languageEnglish (US)
Article number103440
JournalEuropean Journal of Combinatorics
Volume100
DOIs
StatePublished - Feb 2022

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Tournaments and the strong Erdős–Hajnal Property'. Together they form a unique fingerprint.

Cite this