TL;DR
This paper tackles a directed version of the Erdős-Hajnal conjecture, which posits that tournaments avoiding certain substructures must contain large transitive subtournaments. The authors prove this conjecture for tournaments that avoid specific pairs of substructures, including cases where one substructure is the complement of the other. This is a significant step, as it provides the first non-trivial results for several tournaments where the conjecture was previously open.
What Problem Does This Paper Address?
The Erdős-Hajnal conjecture, in its undirected form, states that if a graph G doesn't contain a specific induced subgraph H, then G must have a large clique or independent set. A directed version of this conjecture applies to tournaments (directed graphs where every pair of vertices has exactly one edge between them). It states that if a tournament T avoids a specific tournament H as an induced subtournament, then T must contain a large transitive subtournament (a tournament with no directed cycles). This conjecture is still open for many tournaments.
This paper focuses on a variation of the directed conjecture: what if we forbid two tournaments, H₁ and H₂, instead of just one? Specifically, the authors investigate whether forbidding a pair of tournaments {H₁, H₂} implies the existence of large transitive subtournaments. This is particularly interesting when H₂ is the complement of H₁ (denoted Hᶜ), as the original conjecture for H might be open, but forbidding both H and Hᶜ might lead to a positive result.
Methods
The paper introduces and utilizes a concept called "nebulae," which are tournaments with specific structures in their "backward edge graphs" under certain orderings. These nebulae are then categorized into left, right, and central nebulae. The core of the proof relies on a technical theorem (Theorem 4.6) that establishes a connection between avoiding certain pairs of nebulae and the existence of large complete bipartite subgraphs. This theorem is then used to prove the main result. The proof involves constructing specific substructures within the tournament and leveraging existing results like Ramsey theory and embedding lemmas for tournaments. The authors also introduce a "product tournament" construction, which is a standard tool in this area, to build larger tournaments from smaller ones.
Datasets
Not discussed in the paper. The paper deals with theoretical graph properties and does not involve empirical evaluation on datasets.
Key Insights and Ideas
- The power of forbidding pairs: The paper demonstrates that forbidding a pair of tournaments can be sufficient to prove the Erdős-Hajnal conjecture for certain cases where forbidding a single tournament is not enough. This is a crucial insight, suggesting that the interplay between a tournament and its complement is important.
- Nebulae as building blocks: The introduction and classification of "nebulae" (left, right, central) provide a structured way to analyze tournaments and their substructures. These categories are instrumental in formulating and proving the main theorems.
- Bridging undirected and directed graph theory: The paper draws parallels and utilizes techniques from both undirected and directed graph theory, highlighting the interconnectedness of these fields. For instance, it references the undirected Erdős-Hajnal conjecture and uses concepts like Ramsey numbers and embedding lemmas.
- The significance of complements: The result that forbidding {H, Hᶜ} implies polynomial-size transitive subtournaments for several H where the original conjecture is open is a major breakthrough. It suggests that the structure of a tournament and its complement together impose strong constraints.
Key Results
The paper's main result (Theorem 1.10) states that if a tournament T is {H₁, H₂}-free, where (H₁, H₂) is one of the following pairs: (left nebula, right nebula), (left nebula, central nebula), or (right nebula, central nebula), then T contains a transitive subtournament of size at least |V(T)|<sup>c(H₁, H₂)</sup> for some constant c > 0.
A direct consequence (Theorem 1.11) is that if H is a left/right nebula, then {H, Hᶜ}-free tournaments satisfy the Erdős-Hajnal property. This means that for these specific tournaments H, the conjecture holds even when forbidding H and its complement. The authors emphasize that these are the first non-trivial results of this type.
Limitations and Future Work
The paper acknowledges that several conjectures related to nebulae (left, right, and central nebulae satisfying the Erdős-Hajnal conjecture individually) remain open. The authors' results are conditional on avoiding pairs of these structures. Future work could focus on proving the conjecture for individual types of nebulae or exploring other pairs of forbidden tournaments. The technical nature of the proofs, particularly the reliance on specific substructure definitions and combinatorial lemmas, suggests that further simplification or generalization of these techniques could be valuable. The paper also hints at the difficulty of proving the conjecture for "prime" tournaments (those not formed by substitution procedures), and their results provide a way to tackle some of these challenging cases.
Summary updated