All known prime Erdős-Hajnal tournaments satisfy $ε(H) = Ω(\frac{1}{|H|^{5}\log(|H|)})$

Krzysztof Choromański

TL;DR

This paper provides a major breakthrough in Ramsey theory by establishing the first polynomial lower bounds for the Erdős-Hajnal (EH) coefficient in all known prime tournaments. By moving away from astronomically small bounds derived from the Szemerédi Regularity Lemma, the author demonstrates that for these tournaments, the EH coefficient $\epsilon(H)$ is at least $\Omega(\frac{1}{|H|^5 \log |H|})$.

What Problem Does This Paper Address?

The paper tackles a specific version of the Erdős-Hajnal Conjecture in graph theory. The conjecture suggests that if a graph (or in this case, a directed graph called a "tournament") avoids a specific forbidden sub-structure $H$, it must contain a much larger "ordered" part (a transitive subtournament) than a random graph would.

Specifically, for any tournament $H$, there should exist a constant $\epsilon(H) > 0$ such that every $n$-vertex tournament that does not contain $H$ has a transitive subtournament of size at least $n^{\epsilon(H)}$.

While the conjecture is widely believed, proving it is notoriously difficult. For many years, the only known lower bounds for $\epsilon(H)$ were "tower-type" functions—numbers so incredibly small they are essentially useless for practical computation or deep theoretical insight. The challenge addressed here is to find a polynomial bound—one where $\epsilon(H)$ is bounded by a simple power of the size of $H$.

Methods

The author focuses on prime tournaments, which are the "atomic" building blocks of the conjecture. If the conjecture holds for prime tournaments (those without non-trivial internal symmetries called homogeneous sets), it holds for all tournaments.

Key techniques include:

  • Structural Analysis of Galaxies and Stars: The paper provides detailed proofs for specific families of tournaments known as "stars" and "galaxies," which are the only infinite families of prime tournaments for which the EH conjecture has been proven.
  • Substitution Procedure: A method to build complex tournaments from simpler ones while tracking how the EH coefficient evolves.
  • Density Arguments: The author uses "smooth sequences" and "$m$-sequences" to identify dense transitive chunks within $H$-free tournaments.
  • Inductive Refinement: By using induction on the order of the tournament, the author strengthens existing existential proofs into concrete quantitative bounds.

Datasets

As a theoretical mathematics paper, this work does not use empirical datasets. Instead, it operates on mathematical objects:

  • Prime Tournaments: Tournaments that cannot be decomposed into smaller components via homogeneous sets.
  • Galaxies and Stars: Specific structural classes of tournaments defined by their "backward edge" configurations under certain vertex orderings.

Key Insights and Ideas

  • Breaking the "Regularity" Barrier: Previous proofs relied on the Szemerédi Regularity Lemma, which inherently produces tiny bounds. This paper bypasses that limitation to achieve polynomial growth.
  • Universal Polynomial Degree: A surprising finding is that the polynomial degree (the power of 5 in the denominator) is universal and does not depend on the specific internal structure of the forbidden tournament $H$, only its size.
  • Tightness for Stars: For the family of "prime stars," the author achieves an almost perfectly tight bound where $\epsilon(H) \approx 1/|H|^{1+o(1)}$, matching the best possible upper bounds.
  • Coloring Connection: The paper links the EH coefficient directly to the tournament coloring problem. It shows that if you can find large transitive subtournaments, you can efficiently partition the entire tournament into a small number of transitive sets.

Key Results

  • The Main Bound: For all known prime EH tournaments, $\epsilon(H) \geq \frac{C}{|H|^5 \log |H|}$ for some universal constant $C > 0$.
  • Closing the Gap: The result significantly narrows the gap between the best known lower and upper bounds for the EH coefficient.
  • Coloring Complexity: The author proves that any $H$-free tournament can be colored using at most $O(n^{1-\epsilon(H)} \log n)$ colors.
  • Algorithmic Contribution: The proof is constructive, leading to a quasipolynomial-time algorithm for finding these colorings, which is a significant improvement over standard Ramsey-theoretic approaches.

Limitations and Future Work

  • "Known" Tournaments: The results apply only to the classes of tournaments for which the Erdős-Hajnal conjecture has already been proven (stars, galaxies, $C_5$, etc.). It does not prove the conjecture for all possible tournaments.
  • The Constant $C$: While the paper proves $C$ exists, it does not provide a specific numerical value for this universal constant, which might be quite small.
  • General Prime Tournaments: The ultimate goal remains proving a similar polynomial bound for any prime tournament, a task that likely requires discovering new structural properties of tournaments beyond galaxies.

Summary updated

Abstract

We prove that there exists $C>0$ such that $ε(H) \geq \frac{C}{|H|^{5}\log(|H|)}$, where $ε(H)$ is the Erdős-Hajnal coefficient of the tournament $H$, for every prime tournament $H$ for which the celebrated Erdős-Hajnal Conjecture has been proven so far. This is the first polynomial bound on the EH coefficient obtained for all known prime Erdős-Hajnal tournaments, in particular for infinitely many prime tournaments. As a byproduct of our analysis, we answer affirmatively the question whether there exists an infinite family of prime tournaments $H$ with $ε(H)$ lower-bounded by $\frac{1}{\textit{poly}(|H|)}$, where $\textit{poly}$ is a polynomial function. Furthermore, we give much tighter bounds than those known so far for the EH coefficients of tournaments without large homogeneous sets. This enables us to significantly reduce the gap between best known lower and upper bounds for the EH coefficients of tournaments. As a corollary we prove that every known prime Erdős-Hajnal tournament $H$ satisfies: $-5 + o(1) \leq \frac{\log(ε(H))}{\log(|H|)} \leq -1 + o(1)$. No lower bound on that expression was known before. We also show the applications of those results to the tournament coloring problem. In particular, we prove that for every known prime Erdős-Hajnal tournament $H$ every $H$-free tournament has \textit{chromatic number} at most $O(n^{1-\frac{C}{|H|^{5}\log(|H|)}}\log(n))$, where $C>0$ is some universal constant. The related coloring can be constructed algorithmically in the quasipolynomial time by following straightforwadly the proof of our main result. In comparison, the standard Ramsey theory gives only $O(\frac{n}{\log(n)})$ bounds for the tournament chromatic number.
BibTeX
@misc{choromanski2014all,
  author = {Krzysztof Choromański},
  title = {{All known prime Erdős-Hajnal tournaments satisfy $ε(H) = Ω(\textbackslash\{\}frac\{1\}\{|H|^\{5\}\textbackslash\{\}log(|H|)\})$}},
  year = {2014},
  eprint = {1410.7046},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.7046},
}

Loading related content...

Figure