This paper, titled "Excluding pairs of tournaments," by Krzysztof Choromanski, provides a significant breakthrough in the field of structural graph theory, specifically regarding the long-standing Erdős-Hajnal conjecture.
TL;DR
The paper proves that forbidding certain pairs of tournament structures (called "nebulae") in a larger tournament guarantees the existence of a polynomial-sized transitive subtournament. This represents the first non-trivial result showing that the Erdős-Hajnal property holds for pairs of tournaments even when it hasn't been proven for the individual tournaments themselves.
What Problem Does This Paper Address?
The Erdős-Hajnal conjecture is one of the most famous open problems in Ramsey theory. In its undirected form, it suggests that if you forbid any fixed graph $H$ as an induced subgraph, the remaining graph must contain a very large "structured" part (either a clique or a stable set).
In the directed version, we look at tournaments—directed graphs where every pair of vertices has exactly one directed edge between them. Here, the "structured part" is a transitive subtournament, which is essentially a ranking where no cycles exist (i.e., if A beats B and B beats C, then A must beat C).
While the conjecture has been proven for some small or specific tournament structures (like "galaxies"), it remains unsolved for most. This paper shifts the focus: instead of forbidding just one tournament $H$, what happens if we forbid a pair of tournaments $\{H_1, H_2\}$? The author investigates whether this combined restriction is enough to force a large transitive subtournament.
Methods
The author introduces and utilizes several sophisticated combinatorial tools:
- Nebulae: The paper defines a new class of tournaments called "nebulae." These are defined by an ordering of vertices where "backward edges" (edges going against the grain of the ordering) form simple star-shaped components. The author distinguishes between left, right, and central nebulae based on where the center of these stars sits in the ordering.
- Product Tournaments & $(c, \lambda, w)$-structures: These are technical frameworks used to decompose large tournaments into manageable pieces with specific density properties.
- Tournament Regularity Lemma: A directed version of Szemerédi’s Regularity Lemma is used to partition the tournament into "regular" pairs, allowing the author to treat large-scale structures almost like random graphs.
- Hypergraph Ramsey Theory: The core proof involves modeling the tournament's structure as a 3-regular hypergraph. By applying Ramsey’s Theorem to this hypergraph, the author proves that one can always find either the forbidden tournaments or the desired transitive subset.
Datasets
Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs and logical derivation rather than empirical datasets.
Key Insights and Ideas
- The Power of Complementarity: The most striking insight is that while we don't know if a single nebula $H$ satisfies the Erdős-Hajnal conjecture, forbidding both a nebula and its complement ($H^c$)—or two different types of nebulae—provides enough structural constraint to prove the property.
- Beyond Galaxies: Previous work proved the conjecture for "galaxies" (a more restrictive type of ordering). "Nebulae" are a broader and more complex class. This paper shows that the "no center between leaves" restriction required for galaxies can be bypassed if we exclude pairs of structures.
- Prime Tournaments: The results are particularly meaningful because they apply to "prime" tournaments—those that cannot be decomposed into smaller tournaments. Prime tournaments are the "atoms" of this conjecture; if it holds for them, it generally holds for all.
Key Results
- Theorem 1.10: If $H_1$ and $H_2$ are a pair consisting of a left nebula and a right nebula (or a left and central, or a right and central), then any tournament excluding both contains a transitive subtournament of size $|V(T)|^c$ for some constant $c > 0$.
- Corollary 1.11: For any tournament $H$ that is a left or right nebula, the pair $\{H, H^c\}$ satisfies the Erdős-Hajnal property.
- Nontriviality: The author demonstrates that these families of nebulae contain infinitely many prime tournaments that are neither galaxies nor "constellations," meaning these results cannot be derived from previous known cases.
Limitations and Future Work
- The Single Nebula Problem: The paper leaves open the question of whether a single nebula satisfies the conjecture (Conjecture 1.6). The proof strictly requires the exclusion of a pair.
- Small Constants: Like many proofs involving the Regularity Lemma, the constant $c$ (the exponent) is likely very small. While the paper notes that bounds for galaxies have been improved in subsequent literature, the bounds here remain theoretical.
- Complexity of Stars: The current proof focuses on nebulae where components are three-vertex stars. Extending this to nebulae with larger, more complex star components or different backward-edge structures is a suggested path for future research.
Summary updated