In a purely random graph, local structures appear with predictable statistical regularity. But what happens when we break this randomness by imposing strict local constraints? A major direction in extremal graph theory explores a profound duality: forbidding a specific local pattern forces the emergence of massive, highly organized global structures. Conversely, preventing large organized structures forces the graph to exhibit an incredibly diverse, well-mixed distribution of local densities.
The Erdős-Hajnal Phenomenon: From Forbidden Patterns to Global Order
The most prominent manifestation of this duality is the Erdős-Hajnal conjecture. In a typical graph of size $n$, the largest clique (a set of mutually connected vertices) or independent set (a set of mutually disconnected vertices) might only grow logarithmically with the number of vertices. However, the conjecture states that if a graph avoids even a single fixed induced subgraph, it is forced to contain a much larger clique or independent set—one that grows polynomially ($n^c$ for some constant $c$). Forbidding a local configuration strips away the graph's ability to remain disordered.
This phenomenon extends naturally to directed graphs, specifically tournaments, where every pair of vertices is connected by exactly one directed edge. In tournaments, the equivalent of a clique or independent set is a transitive subtournament—a perfectly ordered hierarchy where if there are directed edges $A \to B$ and $B \to C$, there must be a direct edge $A \to C$.
In Forcing large transitive subtournaments, Eli Berger et al. proved the directed Erdős-Hajnal conjecture for an infinite class of tournaments known as "galaxies." By showing that avoiding a specific subtournament structure guarantees a large transitive subtournament, the authors demonstrated how local structural prohibitions cascade into global acyclic order. To map out the boundaries of this phenomenon, Eli Berger et al. later verified the conjecture for nearly all six-vertex tournaments in On the Erdős-Hajnal conjecture for six-vertex tournaments, narrowing down the minimal configurations that could resist this structural forcing.
Sometimes, the forced order is even stronger than a single transitive set. The "strong Erdős-Hajnal property" requires the existence of two large, completely separated vertex subsets with complete connectivity between them. In Tournaments and the strong Erdős-Hajnal Property, Eli Berger et al. showed that avoiding a 5-cycle ($C_5$) in a tournament forces this powerful bipartite-like alignment, illustrating how specific small forbidden patterns dictate large-scale geometric order.
The Ramsey Flip Side: Density Diversity
What happens if we look at the inverse scenario? Suppose we explicitly construct a graph that lacks large cliques or independent sets—a so-called Ramsey graph. Because it cannot contain large homogeneous regions, the graph must be thoroughly "well-mixed."
This lack of global homogeneity forces a different kind of structure: an explosion of local diversity. The Erdős-McKay conjecture posits that any graph with a small trivial subgraph size (bounded cliques and independent sets) must contain induced subgraphs representing every possible edge count up to a quadratic fraction of the total edges.
To understand why this works, imagine trying to build a graph without any large clusters of all-edges or no-edges. You are forced to constantly vary the local edge density across different neighborhoods. In Induced subgraphs of prescribed size, Michael Krivelevich et al. made significant progress on this front, proving that graphs with small trivial subgraphs are guaranteed to contain induced subgraphs spanning a massive range of exact edge counts. Rather than finding perfectly ordered subsets, the absence of large cliques forces the graph to be so structurally granular that you can find an induced subgraph tailored to almost any precise size or density you desire.
Similarly, Alexandr Kostochka et al. explored this in Induced subgraphs with distinct sizes, demonstrating that balanced graphs must exhibit a high number of distinct pairs of vertex and edge counts among their induced subgraphs. The global constraint against homogeneity directly drives local polymorphic variety.
Bridging Turán Density and Ramsey Structure
Ultimately, these two perspectives—how density constraints force specific subgraphs, and how avoiding subgraphs forces specific densities—are deeply intertwined. This is the bridge between Turán numbers (the maximum edges allowed before a specific subgraph is forced to appear) and Ramsey numbers (the minimum size needed to guarantee monochromatic structures).
In A Ramsey-type problem and the Turán numbers, P. Erdös et al. established precise asymptotic formulas bridging these concepts, showing how graph coloring constraints map directly onto edge-density thresholds. Expanding on this interplay, Michael Krivelevich et al. in Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions adapted bounding techniques from Turán density problems to solve long-standing Ramsey problems.
By viewing Turán density bounds as a tool to control local structure, and Ramsey theory as a guarantee of global order, this unified research direction reveals that a graph's local constraints and global architecture are tightly wound. Whether you are forbidding a 5-vertex tournament or capping the size of a clique, you are pulling on a thread that inevitably forces the rest of the graph into a highly predictable structural state.
Key Foundational Work
Induced subgraphs of prescribed size (2003) — contributed 3 concept elements to this direction.
A Ramsey-type problem and the Turán numbers (2002) — contributed 1 concept elements to this direction.
Tura'n Numbers of Bipartite Graphs and Related Ramsey-Type Questions (2003) — contributed 1 concept elements to this direction.