Abstract
The Erdős-Hajnal Conjecture states that for every $H$ there exists a constant $ε(H)>0$ such that every graph $G$ that does not contain $H$ as an induced subgraph contains a clique or a stable set of size at least $|V(G)|^{ε(H)}$. While the conjecture remains open, its directed version—where graphs are replaced by tournaments and cliques by transitive subtournaments—has seen significant progress. If the conjecture is false, the smallest counterexample must be a prime tournament. This paper introduces the strong EH-property, a theoretical framework that enables the construction of new infinite families of prime tournaments satisfying the conjecture. By moving beyond the traditional "substitution procedure," this work provides a mechanism to combine tournaments into larger, potentially prime structures, nearly completing the classification for all 6-vertex tournaments.
Introduction
The Erdős-Hajnal (EH) Conjecture is a major open question in combinatorics. It suggests that excluding a specific sub-pattern ($H$) forces a graph to contain a much larger "ordered" structure than one would expect in a random graph. In the directed setting, we focus on tournaments (complete directed graphs) and search for transitive subtournaments (where edges follow a linear order).
A critical bottleneck in this research is the role of prime tournaments—structures that cannot be decomposed into smaller components. Because any non-prime counterexample would imply the existence of a smaller prime counterexample, the study of prime tournaments is the "holy grail" of the field. Previously, the only way to build larger tournaments satisfying the conjecture was the "substitution procedure," which unfortunately only produces non-prime results. This paper introduces a new constructive method to bridge this gap.
The Strong EH-Property and m-Sequences
The author develops a framework based on m-sequences: sequences of vertex subsets with specific density requirements. These sequences act as a structured environment to search for specific patterns.
A tournament $H$ is defined as having the strong EH-property if any well-behaved m-sequence in a larger tournament $T$ either contains an embedding of $H$ or a "strong pair" (two large sets where almost all edges point in one direction). The paper proves that this property is equivalent to a "super-strong" version, which simplifies the process of combining different tournament families mathematically.
The Product Operation ($\oplus$)
The core innovation of this work is the product operation ($\oplus$). This method allows for the combination of two families of tournaments while preserving the strong EH-property. Unlike the old substitution method, this product can generate prime tournaments.
This methodological shift allows for the generalization of "galaxies"—a family for which the conjecture was recently proven. The paper demonstrates that galaxies are a specific, simple case of this new, broader framework. By leveraging a directed version of the Szemerédi Regularity Lemma, the author provides the first robust method to produce infinite families of prime tournaments that satisfy the EH-property.
Key Results and the 6-Vertex Milestone
The application of the strong EH-property has led to several breakthroughs:
- New Infinite Families: The paper proves the EH-property for new classes of tournaments, specifically right pseudogalaxies and $\alpha$-galaxies.
- 6-Vertex Classification: The author evaluates the set of all possible tournaments on 6 vertices. Using these new tools, the conjecture is proven for all 6-vertex tournaments except for one specific case, denoted as $H_D$.
- Structural Construction: The work establishes a mechanism to build complex tournaments from simpler ones without losing the structural properties required by the EH conjecture.
Limitations and Future Work
Despite these advances, the tournament $H_D$ remains a holdout, representing the current boundary of the technique. Furthermore, while the paper provides a way to build tournaments with the strong EH-property, it does not yet offer a compact set of rules to identify every tournament that might possess it.
Finally, the paper highlights the persistent gap between directed and undirected graph theory. While the tournament version of the conjecture is yielding to these new structural methods, the undirected version remains significantly more difficult; it has not yet been proven for any prime undirected graph with more than 5 vertices.
Summary updated