2021/01/26 by Salman Ghazal, Ghazal, Salman, Soukaina Zayat +1
Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2101.10754
openalex publication_date 2021/01/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 size at least nε(H) . Recently the conjecture was proved for all six-vertex tournaments, except K6. In this paper we construct two infinite families of tournaments for which the conjecture is still open for infinitely many tournaments in these two families - the family of so-called super nebulas and the family of so-called super triangular galaxies. We prove that for every super nebula H1 and every Δgalaxy H2 there exist ε(H1,H2) such that every \lbrace H1,H2\rbrace-free tournament T contains a transitive subtournament of size at least \midT|^ε(H1,H2). We also prove that for every central triangular galaxy H there exist ε(K6,H) such that every \lbrace K6,H\rbrace-free tournament T contains a transitive subtournament of size at least \midT|^ε(K6,H). And we give an extension of our results.