Erdös-Hajnal Conjecture for New Infinite Families of Tournaments

2020/10/22 by Zayat, Soukaina, Ghazal, Salman
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2010.12329

Abstract

Erdös-Hajnal conjecture 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 a stable set of size at least n^ε(H) . This 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) . This conjecture is known to hold for a few infinite families of tournaments. In this paper we construct two new infinite families of tournaments - the family of so-called galaxies with spiders and the family of so-called asterisms, and we prove the correctness of the conjecture for these two families.

Related

• Tournaments and the Erdös-Hajnal Conjecture
• About the Erdös-Hajnal conjecture for seven-vertex tournaments
• Forbidding Couples of Tournaments and the Erdös-Hajnal Conjecture
• On the Erdős-Hajnal conjecture for six-vertex tournaments
• Excluding pairs of tournaments