Classical extremal graph theory begins with a simple question: how many edges can a graph contain before it is guaranteed to include a specific forbidden subgraph $H$? This threshold, known as the Turán number $ex(n, H)$, has been a cornerstone of combinatorics since the mid-20th century. However, edges only capture pairwise connectivity. Real-world networks and complex mathematical structures are defined by higher-order motifs—such as triangles, cliques, paths, and cycles.
To understand these dense configurations, researchers have shifted toward the generalized Turán problem. Instead of maximizing edges (which are simply copies of a single edge, $K_2$), the goal is to maximize the number of copies of a target subgraph $T$ within a graph that remains completely free of a forbidden subgraph $H$. Formally denoted as $ex(n, T, H)$, this framework uncovers how local structural constraints dictate the global density of complex networks.
As Clara Shikhelman demonstrates in Many T copies in H-free graphs, moving from counting edges to counting complex subgraphs introduces significantly richer and more volatile combinatorial behavior. The growth rates are no longer straightforwardly dictated by the chromatic number of $H$; instead, they depend intimately on the structural alignment between $T$ and $H$.
The Geometry of Extremal Graphs: When is the Turán Graph Optimal?
In classical theory, the definitive answer to avoiding a complete graph $K_k$ is the Turán graph $T_{k-1}(n)$—a complete, balanced $(k-1)$-partite graph. By distributing vertices as evenly as possible across independent sets, the Turán graph maximizes edges while ensuring that no $K_k$ can form, as any $K_k$ would require at least two vertices to share a part.
Does this elegant multipartite structure still maximize other subgraphs? Graphs $T$ for which the Turán graph remains the absolute maximizer are called Turán-good. Chengfei Xie et al. explore this property in Some results on k-Turán-good graphs, proving that paths like $P_4$ and $P_5$ are $k$-Turán-good for $k \ge 4$.
The intuition behind why Turán graphs excel at packing paths lies in their cross-part connectivity. Because every vertex in one part is connected to every vertex in all other parts, a path can freely weave back and forth across the partitions. The balanced nature of the Turán graph ensures that the path does not get "trapped" in an exhausted partition prematurely, thereby maximizing the total number of valid paths.
This structural optimality extends beyond pure graph theory into topology. In topological data analysis, graphs are often used to build simplicial complexes. Lies Beers shows in Extremal Betti Numbers and Persistence in Flag Complexes that the $k$-th Betti number (which counts $k$-dimensional holes) of a flag complex is maximized precisely when the underlying graph is a Turán graph. The absence of a larger clique prevents higher-dimensional holes from filling in and closing, preserving the complex's lower-dimensional topological features.
Packing Constraints and Structural Phase Transitions
When the target structure $T$ or the forbidden structure $H$ deviates from simple cliques or paths, the optimal graph topologies shift dramatically. For instance, if we forbid disconnected or disjoint structures, the problem becomes a balancing act between localized packing and global constraints.
Consider the challenge of maximizing cliques while avoiding vertex-disjoint paths. Zhipeng Gao et al. analyze this in The maximum number of cliques in graphs that avoid vertex-disjoint copies of path of length two, determining exact bounds for avoiding $kP_3$. Similarly, Changhong Lu et al. investigate the density of complete bipartite subgraphs ($K_{r,s}$) when long paths or cycles are banned in The Maximum Number of Copies of $K_{r, s}$ in Graphs Without Long Cycles or Paths.
When constraints are placed on multipartite hosts themselves, as explored by Junxue Zhang in Extremal numbers of disjoint triangles in r-partite graphs, or when maximizing specific independent structures like dissociation sets (vertex subsets inducing subgraphs of maximum degree 1), as shown by Bo-Jun Yuan et al. in The number of dissociation sets in connected graphs, the extremal configurations often transition from symmetric multipartite graphs to highly asymmetric, tree-like, or core-periphery structures.
This behavior can be formalized by altering how we measure a graph's density. Instead of counting total edges, we can evaluate the $p$-norm of its vertex degrees (the sum of degrees raised to the $p$-th power). Oleg Pikhurko et al. demonstrate in Phase Transition of Degenerate Turán Problems in ({p})-Norms that optimizing this norm triggers a sharp phase transition. As the parameter $p$ varies, the optimal topology abruptly snaps from a uniform distribution of edges to a highly skewed configuration dominated by localized, high-degree hubs.
[Low p-norm: Uniform Density] ---> [Critical Threshold] ---> [High p-norm: Concentrated Hubs]
(Edges spread evenly, e.g., (Abrupt structural (Star-like or core-periphery
balanced multipartite graphs) phase transition) topologies dominate)
Host-Constrained and Relative Extremal Problems
The classical Turán framework assumes an idealized environment: we are free to select our subgraph from a complete host graph $K_n$. A more realistic and mathematically demanding variation restricts our choices to the subgraphs of a pre-existing, non-complete host graph $G$. This is known as the relative or host-constrained extremal problem.
In this setting, you cannot simply construct a global Turán graph; you must strategically prune the edges of $G$ to eliminate forbidden structures while preserving as many target motifs as possible. Florent Foucaud et al. tackle this in Large Subgraphs without Short Cycles, providing tight bounds on how large a subgraph can be carved out of an arbitrary host graph if we wish to eliminate short even cycles. When the host graph is a random graph, the problem becomes probabilistic. Michael Krivelevich et al. establish in Largest subgraph from a hereditary property in a random graph how the size of the largest subgraph satisfying a hereditary property scales relative to the density of its random host environment.
From a computational standpoint, finding the exact maximum $H$-free subgraph of an arbitrary graph $G$ is often NP-hard. To bypass this intractability, Clara Shikhelman introduces an algorithmic framework in Additive Approximation of Generalized Turán Questions. The author provides a polynomial-time additive approximation algorithm that estimates the maximum number of copies of $T$ within an $H$-free subgraph of $G$, mapping out the boundary where efficient approximation remains theoretically possible.
The Hypergraph Frontier
When moving from graphs to hypergraphs—where edges can connect three or more vertices—our standard geometric intuitions break down. In graphs, the Erdős-Stone theorem provides a clean asymptotic link between a forbidden graph's chromatic number and its extremal density. In hypergraphs, no such universal theorem exists, making hypergraph Turán problems notoriously difficult.
A central concept here is uniform Turán density, which measures the minimum edge density required to force the appearance of a forbidden hypergraph $F$ within an infinitely large, uniformly dense hypergraph. August Y. Chen et al. advance this frontier in Beyond the broken tetrahedron by successfully computing the uniform Turán density for a novel 3-uniform hypergraph configuration ($F_*$), expanding the small catalog of known exact densities.
The structural complexity of hypergraphs also manifests when avoiding cycles. In graphs, avoiding a cycle limits the number of edges to a linear or near-linear function of vertices. In hypergraphs, the definition of a cycle splits into multiple variants, such as tight cycles. Hao Huang disproved a long-standing conjecture in On Tight Cycles in Hypergraphs, demonstrating that $k$-uniform hypergraphs avoiding tight cycles can accommodate significantly more edges than the previously suspected $O(n^{k-1})$ limit.
Graph Cycles: Edge density is strictly bounded (e.g., O(n) for trees/forests).
Hypergraph Tight Cycles: Combinatorial freedom allows dense, complex overlapping structures,
shattering the O(n^{k-1}) bound.
Furthermore, counting cliques in hypergraphs requires managing constraints on various subset degrees ($i$-degrees). Rachel Kirsch et al. address this in Many Cliques in Bounded-Degree Hypergraphs, deriving asymptotically tight upper bounds linked to Steiner systems. As Alan C. H. Ling demonstrates in On Extremal k-Graphs Without Repeated Copies of 2-Intersecting Edges, finding exact solutions for these hypergraph packing problems frequently requires resolving a finite number of exceptional parameter values where the standard asymptotic behavior breaks down due to small-scale combinatorial anomalies.
Real-World Equivalences: Coding Theory
While substructure enumeration under avoidance constraints appears abstract, it shares an exact mathematical equivalence with the fundamental limits of error-correcting codes. A code can be viewed as a collection of vectors (or graphs) where no two elements are "too close" or share a forbidden relationship, ensuring that errors can be detected and repaired.
Noga Alon exposes this connection in Erasure list-decodable codes and Turán hypercube problems, proving that determining the maximum capacity of an erasure list-decodable code is logically identical to a vertex Turán problem on a hypercube. In this formulation, the goal is to find the maximum number of vertices a subset of a hypercube can contain while avoiding a specific configuration of subcubes.
Similarly, Yuze Wu et al. study "F-codes" in Phase Transitions of Structured Codes of Graphs. These are families of graphs where the symmetric difference between any two members must avoid a forbidden family $F$. The authors reveal that the maximum size of these codes undergoes sharp phase transitions governed directly by the chromatic numbers and structural properties of the forbidden graphs.
By framing coding constraints as graph and hypergraph avoidance problems, researchers can deploy the heavy machinery of extremal combinatorics to calculate the absolute physical limits of data transmission and storage.
Key Foundational Work
On Extremal k-Graphs Without Repeated Copies of 2-Intersecting Edges (2007) — contributed 5 concept elements to this direction.
Large Subgraphs without Short Cycles (2015) — contributed 1 concept elements to this direction.