Fact-checked by Grok 2 weeks ago

Extremal graph theory

Extremal graph theory is a branch of combinatorics and graph theory that investigates the extremal values of graph parameters, such as the maximum number of edges in an n-vertex graph that avoids a specified forbidden subgraph or minor, thereby determining how global properties like edge density influence local substructures.^[1] The field originated with Pál Turán's seminal work in 1941, which addressed the maximum edges in a graph without a complete subgraph K_r, leading to Turán's theorem: the extremal graph is the complete (r-1)-partite Turán graph T(n, r-1) with approximately \frac{r-2}{2(r-1)} n^2 edges, and any graph exceeding this edge count must contain a K_r.^[1] This theorem not only founded the discipline but also inspired generalizations, including the Erdős–Stone theorem (1946), which extends Turán's result to arbitrary forbidden subgraphs by relating the extremal function to the chromatic number of the forbidden graph.^[1] Key problems in extremal graph theory also encompass minors and connectivity, exemplified by Hadwiger's conjecture (1943), which posits that every graph without a K_r-minor is (r-1)-colorable—a statement proven for r \leq 6 but remaining open for larger r.^[1] Tools like Szemerédi's regularity lemma (1975) have become essential for proving results in dense graphs, partitioning vertices into equitable sets where edges between parts behave randomly, facilitating applications to subgraph containment and stability versions of extremal theorems.^[1] Beyond pure mathematics, extremal graph theory informs applications in computer science (e.g., algorithm design for dense networks) and optimization, while ongoing research explores hypergraphs, directed graphs, and infinite structures to broaden its scope.^[1]^[2]

Introduction

Definition and Scope

Extremal graph theory is a branch of combinatorics focused on determining the maximum or minimum values of graph invariants, such as the number of edges or vertex degrees, in graphs with n vertices that avoid specified forbidden substructures like subgraphs, minors, or other structural properties.^[1]^[3] This involves analyzing how global parameters constrain local configurations, often seeking extremal graphs that achieve these bounds while satisfying the avoidance conditions.^[4] The study extends beyond simple edge maximization to include invariants like matching sizes or degree sequences, providing insights into the structural limits imposed by prohibitions.^[5]^[6] Central to the field are questions about the extremal values under such constraints, exemplified by determining the maximum number of edges in an H-free graph on n vertices, where H is a fixed forbidden subgraph; this maximum is denoted by the extremal function \ex(n, H).^[7]^[8] Generalizations address families of forbidden structures F, yielding \ex(n, F) as the largest number of edges in an n-vertex graph avoiding any member of F as a subgraph.^[9] These inquiries extend to other parameters, such as the maximum matching size or minimum degree thresholds in graphs evading certain minors, broadening the scope to diverse graph properties.^[10]^[5] The scope of extremal graph theory emphasizes asymptotic behavior for large n, characterizing the growth rates of extremal functions rather than exact counts for fixed sizes.^[11] This asymptotic orientation contrasts with enumerative combinatorics, which prioritizes precise enumeration of all structures satisfying given criteria, whereas extremal approaches seek bounding thresholds under avoidance.^[12] A canonical example is Turán's theorem, which asymptotically resolves \ex(n, K_r) for complete graphs K_r.

Motivations and Applications

Extremal graph theory is motivated by fundamental questions in combinatorics concerning how the prohibition of local substructures, such as specific subgraphs, imposes constraints on global graph properties like the maximum number of edges.^[13] This perspective highlights the tension between maximizing structural complexity while avoiding forbidden configurations, providing insights into the boundaries of graph construction.^[11] A key theoretical drive stems from its interplay with Ramsey theory, where extremal graph theory emphasizes avoidance—determining the largest graphs free of certain subgraphs—contrasting with Ramsey theory's focus on inevitability, where certain structures emerge unavoidably in sufficiently large systems.^[11] In combinatorics, extremal graph theory has profoundly influenced additive combinatorics by offering graph-theoretic analogs to problems involving arithmetic progressions. For instance, proofs of Roth's theorem, which states that any subset of the integers without a 3-term arithmetic progression has density approaching zero, often rely on tools like the graph regularity lemma and triangle removal lemma to model progressions as graph triangles.^[14] These methods partition graphs into dense subgraphs and bound the size of progression-free sets, demonstrating how extremal avoidance principles translate to additive structures.^[14] Beyond pure mathematics, extremal graph theory informs network design by identifying maximum edge configurations that avoid dense subnetworks, thereby enhancing resilience and efficiency in communication topologies.^[15] In computer science, it provides algorithmic bounds for optimization problems, such as using greedy heuristics to approximate solutions for triangle-free graphs with high accuracy and low runtime.^[15] Turán graphs serve as extremal constructions in these applications, offering balanced complete multipartite structures that maximize edges without forbidden cliques.^[13] Interdisciplinary applications extend to chemistry, where extremal principles help analyze molecular graph stability by modeling compounds as graphs and determining configurations that avoid unstable substructures.^[16] In extremal set theory, connections arise through problems maximizing set families without certain intersections, mirroring subgraph avoidance and yielding dual extremal functions.^[17] Similarly, in coding theory, extremal graph constructions with large girth produce error-correcting codes that avoid short cycles, improving decoding efficiency in Tanner codes.^[18]

Historical Development

Early Foundations

The foundations of extremal graph theory were laid in the early 20th century, emerging from classical graph theory as mathematicians began exploring the maximum sizes of graphs avoiding specific substructures, amid a growing interest in combinatorial optimization problems.^[19] This period saw initial efforts to quantify structural constraints in graphs, setting the stage for systematic studies of edge maximization under forbidden configurations. A pivotal early result was Mantel's theorem from 1907, which determines the maximum number of edges in an n-vertex graph without a triangle (K_3 subgraph) as \lfloor n^2/4 \rfloor, achieved by the balanced complete bipartite graph K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}. Mantel's proof, posed as a problem in a Dutch mathematical journal, relied on basic degree arguments and remains a cornerstone, illustrating how bipartite graphs can extremize edge counts without forming odd cycles.^[19] In the 1930s, Pál Turán contributed to early extremal questions through work on combinatorial structures, including investigations into sequences of out-degrees realizable by directed complete graphs (tournaments) and their implications for balanced structures.^[20] This built on combinatorial traditions and anticipated broader avoidance problems in directed graphs. Complementing these efforts, Frank Ramsey's 1928 theorem on unavoidable monochromatic cliques in edge-colored complete graphs introduced key ideas of subgraph inevitability, focusing attention on avoidance thresholds that would shape extremal theory. Pre-World War II developments by figures like Mantel established extremal graph theory as a distinct pursuit, emphasizing precise bounds on graph parameters to avoid small forbidden subgraphs, distinct from but influential on later probabilistic and density-based approaches.^[19]

Major Advances and Contributors

The publication of Paul Turán's theorem in 1941 marked a foundational advance in extremal graph theory, providing the exact maximum number of edges in an n-vertex graph without a complete subgraph K_r for r ≥ 3, thereby initiating systematic study of forbidden subgraph problems.^[21] In 1946, Paul Erdős and Arthur Stone established an asymptotic result generalizing Turán's theorem to arbitrary forbidden graphs H with chromatic number at least 3, where the extremal density is that of the complete (χ(H)-2)-partite Turán graph, thereby bridging extremal problems with density considerations determined by the chromatic number.^[22] These developments in the 1940s and 1950s shifted focus toward precise bounds and structural insights, influencing subsequent research on graph densities and stability. Key contributors during this era included Turán, whose work on clique avoidance laid the groundwork for balanced incomplete graphs, and Erdős, who posed numerous influential problems, such as determining the extremal number for even cycles, sparking decades of investigation into bipartite forbidden subgraphs.^[23] In the 1960s and 1970s, András Hajnal, Vera Sós, and Miklós Simonovits advanced the field through stability theorems, showing that graphs nearly achieving Turán's extremal function are structurally close to Turán graphs, thus providing qualitative refinements to quantitative bounds.^[24] Their collaborative efforts, often with Erdős, emphasized perturbation analyses and applications to broader combinatorial structures. Milestones in the 1970s extended extremal theory to hypergraphs, with Erdős introducing problems on uniform hypergraph Turán numbers and Brown, Erdős, and Sós proving the existence of triangulated spheres in certain 3-uniform hypergraphs, adapting graph-theoretic tools to higher uniformity.^[19] A major methodological breakthrough came in 2007 with Alexander Razborov's introduction of flag algebras, a semidefinite programming framework that enabled computer-assisted proofs of asymptotic densities for forbidden subgraphs, resolving longstanding conjectures like the C_4 problem.^[25] Recent trends up to 2025 have emphasized spectral variants of extremal problems, such as Nikiforov's 2007 conjecture on spectral Turán numbers, with 2024 results establishing new bounds for weighted graphs via eigenvalue optimizations and 2025 advances on spectral extrema for F_6-free graphs with even size.^[26] Progress in generalized Turán problems, counting copies of one graph while avoiding another, includes 2023 advances on ex(n, H, F) for non-bipartite H. Additionally, 2023-2024 work on edge-ordered graphs has determined linear extremal functions for ordered forbidden subgraphs, extending classical Turán theory to labeled edge settings.^[27]

Fundamental Theorems

Turán's Theorem

Turán's theorem provides the exact value of the extremal function ex(n, K_r), which is the maximum number of edges in an n-vertex graph without a complete subgraph K_r for integers n ≥ 1 and r ≥ 2. The theorem asserts that ex(n, K_r) equals the number of edges in the Turán graph T(n, r-1), the unique graph achieving this maximum among K_r-free graphs on n vertices.^[28] The Turán graph T(n, k) is the complete k-partite graph on n vertices in which the sizes of the partite sets differ by at most one; specifically, if n = qk + b with 0 ≤ b < k and q = \lfloor n/k \rfloor, then b parts have size q+1 and k-b parts have size q. The number of edges in T(n, k) is given by

e(T(n, k)) = \frac{1}{2} \left( n^2 - \sum_{i=1}^k s_i^2 \right),

where s_i are the part sizes, yielding the asymptotic formula

e(T(n, k)) = \left(1 - \frac{1}{k}\right) \frac{n^2}{2} + O(1).

Thus, ex(n, K_r) = \left(1 - \frac{1}{r-1}\right) \frac{n^2}{2} + O(1).^[29] A standard proof of Turán's theorem employs Zykov symmetrization: starting from a K_r-free graph G on n vertices, select two non-adjacent vertices u and v where deg(u) ≤ deg(v), and replace u's neighborhood with v's (adding edges from u to N(v) and removing edges from u to non-neighbors of v, while handling mutual neighbors appropriately); this preserves the number of edges and K_r-freeness. Repeating this process yields a complete (r-1)-partite graph with at least as many edges as G, implying T(n, r-1) is extremal. Alternatively, a proof via double counting considers the maximum degree and inducts on the structure to show the extremal graph must be balanced complete multipartite.^[28] The Erdős–Simonovits stability theorem strengthens Turán's result by showing that any K_r-free n-vertex graph with e(G) > e(T(n, r-1)) - \epsilon n^2 edges (for fixed \epsilon > 0 and large n) differs from T(n, r-1) in at most \delta(\epsilon) n^2 edges or vertices, where \delta(\epsilon) \to 0 as \epsilon \to 0; this implies such graphs are close to (r-1)-partite.^[30] A prominent special case is Mantel's theorem for r=3: the maximum number of edges in an n-vertex triangle-free graph is \lfloor n^2/4 \rfloor, achieved precisely by the complete bipartite graph T(n, 2) = K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}.^[3] Turán's theorem generalizes Mantel's result and forms the basis for the asymptotic Erdős–Stone theorem on forbidden subgraphs.

Erdős–Stone Theorem

The Erdős–Stone theorem, a cornerstone of extremal graph theory, generalizes Turán's theorem by providing an asymptotic bound on the maximum number of edges in an n-vertex graph that avoids any fixed forbidden subgraph H with chromatic number χ(H) = r ≥ 2. Specifically, the theorem asserts that the extremal function satisfies ex(n, H) ∼ ex(n, K_r), where ex(n, K_r) denotes the Turán number for the complete graph K_r, given by the number of edges in the balanced complete (r-1)-partite graph on n vertices, which is \left(1 - \frac{1}{r-1}\right) \frac{n^2}{2}. Equivalently, \frac{\ex(n, H)}{\binom{n}{2}} \to 1 - \frac{1}{\chi(H)-1} as n → ∞. This result was established by Paul Erdős and Arthur Stone in their 1946 paper, marking a fundamental advance in understanding the structure of dense H-free graphs.^[31] The proof of the theorem relies on analyzing the density of edges between subsets of vertices in large graphs. In the original argument, Erdős and Stone demonstrated that for any ε > 0, sufficiently large H-free graphs must contain a nearly complete (r-1)-partite subgraph with parts of comparable size, ensuring the edge count approaches that of the Turán graph T(n, r-1). Modern expositions often employ the Szemerédi regularity lemma to partition the vertex set into a bounded number of parts where the induced bipartite graphs between most pairs of parts are nearly regular, allowing the application of averaging arguments to identify dense bipartite subgraphs that approximate the extremal construction; deviations from this structure force the presence of H. The extremal graphs are thus asymptotically the blow-ups of the Turán graph T(n, r-1), confirming the leading term.^[31]^[32] A key implication of the theorem is that it determines the asymptotic density for the extremal function of any non-bipartite forbidden graph H, reducing the problem to the clique case resolved by Turán's theorem. For bipartite H (where r = 2), the bound simplifies to ex(n, H) = o(n^2), highlighting that such graphs admit subquadratic extremal numbers, though achieving precise constants requires additional techniques beyond the theorem's scope. The result underscores the pivotal role of chromatic number in controlling edge densities in forbidden-subgraph problems.^[31] Extensions of the theorem include stability versions due to Miklós Simonovits, which strengthen the asymptotic result by showing that if an n-vertex H-free graph G has e(G) > ex(n, H) - ε n^2 edges for small ε > 0, then G is structurally close to the Turán graph T(n, r-1), differing by at most δ n^2 edges where δ → 0 as ε → 0; moreover, when H is color-critical (meaning χ(H - e) = r-1 for some edge e), the extremal number is exactly ex(n, H) = ex(n, K_r) for sufficiently large n. These stability results, originally developed in the late 1960s, facilitate exact determinations and have broad applications in refining extremal problems.^[32]

Extremal Functions and Problems

Forbidden Subgraph Extremal Function

The forbidden subgraph extremal function, commonly denoted \ex(n, H), represents the maximum number of edges in an n-vertex graph that does not contain H as a subgraph.^[33] For a family \mathcal{F} of forbidden subgraphs, \ex(n, \mathcal{F}) is defined analogously as the largest number of edges in an n-vertex graph avoiding every member of \mathcal{F} as a subgraph.^[34] Results for specific forbidden subgraphs H reveal diverse behaviors of \ex(n, H). For trees T with k vertices, the extremal number satisfies \ex(n, T) = \Theta(n), with the upper bound following from the Erdős–Sós conjecture that any graph with average degree exceeding k-2 contains every such tree as a subgraph; this conjecture implies \ex(n, T) \leq (k-2)n/2, achieved asymptotically by the disjoint union of K_{k-1}'s.^[35] The conjecture holds for trees of bounded maximum degree in sufficiently dense host graphs and for all trees when k is large enough.^[36] For cycles, even lengths yield bipartite Turán-type bounds: since C_{2\ell} is bipartite, \ex(n, C_{2\ell}) = O(n^{1 + 1/(\ell-1)}), with exact bipartite Turán numbers known for large even cycles.^[37] For odd cycles C_{2\ell+1}, finer exact values are available, with extremal graphs consisting of nearly balanced complete bipartite graphs augmented by specific attachments, and \ex(n, C_{2\ell+1}) uniquely determined except in a few residue classes modulo the cycle length.^[38] Complete bipartite graphs K_{s,t} (assuming s \leq t) admit the classical bound from the Kővári–Sós–Turán theorem:

\ex(n, K_{s,t}) \leq (s-1)^{1/t} n^{1 - 1/t} + (t-1)n.

This upper bound is tight up to constants for fixed s,t and captures the correct order

\Theta(n^{2 - 1/\min(s,t)}})

.^[39] Prominent open challenges include determining the exact constant in \ex(n, C_4) = \Theta(n^{3/2}), where the Kővári–Sós–Turán bound gives the order but the precise leading coefficient remains unknown despite constructions like projective planes achieving near-optimality.^[40] Similarly, while the Erdős–Gallai theorem provides an exact formula for \ex(n, P_k) involving cases based on n relative to k, finer asymptotic refinements or variants for path families persist as active problems. For minor-closed families of graphs, the Lagarias–Odlyzko approach yields polynomial-time computable asymptotics for \ex(n, \mathcal{F}) when \mathcal{F} is defined by finitely many forbidden minors, leveraging structural decompositions to bound the growth rate.^[10] Supersaturation phenomena address the abundance of forbidden subgraphs beyond the extremal threshold: the Erdős–Lovász–Simonovits theorem establishes that any n-vertex graph with \ex(n, H) + m edges contains at least \Omega(m^{c}) copies of H for some c > 0 depending on H, with explicit constants for certain families like cycles and complete graphs.^[41] For graphs H with chromatic number greater than 2, the asymptotic form of \ex(n, H) follows from the Erdős–Stone theorem.

Zarankiewicz Problem

The Zarankiewicz problem seeks to determine the maximum number of edges in a bipartite graph with given part sizes that avoids a complete bipartite subgraph K_{s,t}. Formally, the Zarankiewicz number z(m,n;s,t) is the largest number of edges in an m \times n bipartite graph containing no K_{s,t} as a subgraph, where the s vertices of the forbidden subgraph lie in the part of size m and the t vertices in the part of size n.^[42] In the balanced case, z(n;s,t) denotes z(n,n;s,t). This problem is a prototypical instance of the extremal function \mathrm{ex}(n,H) for bipartite forbidden graphs H = K_{s,t}, focusing exclusively on complete bipartite obstructions in bipartite host graphs.^[43] A cornerstone upper bound is provided by the Kővári–Sós–Turán theorem, which states that

z(m,n;s,t) \le (s-1)^{1/t} m n^{1-1/t} + (t-1)m.

^[42] For the symmetric balanced case, this yields z(n;s,t) \le (s-1)^{1/t} n^{2 - 1/t} + (t-1) n = O(n^{2 - 1/t}), or symmetrically O(n^{2 - 1/s}) by swapping roles.^[43] This bound is asymptotically tight when t=2 or t=3, but remains suboptimal for larger fixed t \ge 4, where the exact exponent is unknown. Lower bounds arise from explicit constructions, such as incidence graphs of points and lines in finite projective planes of order q, which yield \Omega(n^{3/2}) edges for certain parameters when s=t=2. More generally, algebraic constructions like polarity graphs from projective geometries or random algebraic methods provide lower bounds matching the KST exponent up to constant factors in many cases.^[42] Special cases highlight the problem's structure. For z(n;2,2), which forbids K_{2,2} (equivalently, C_4-free bipartite graphs), the extremal number is \Theta(n^{3/2}), with the upper bound from KST matched by projective plane incidence graphs achieving (1+o(1)) \frac{1}{2} n^{3/2}.^[43] The case z(n;2,s) forbids K_{2,s}, limiting common neighborhoods to at most s-1; here, the KST bound gives O(n^{3/2}), and constructions from finite geometries or random methods attain \Omega(n^{3/2}), establishing the asymptotic order, though related to bounding multiple stars in the neighborhood structure.^[42] Recent progress in 2023–2024 has refined these bounds for fixed s,t using algebraic techniques, including linear programming optimizations that improve the constant factors and occasionally the exponents in the KST framework for general bipartite graphs. For instance, new constraints in linear programs yield tighter upper bounds, such as reducing z(17,10;3,3) from 112 to 111 edges, with asymptotic implications for small fixed parameters via algebraic optimization.^[44] These advances, building on semi-algebraic methods, narrow the gap between constructions and upper bounds, though the core exponents remain governed by KST for most fixed s,t.^[43]

Advanced Concepts and Methods

Homomorphism Densities

Homomorphism densities offer a quantitative measure for capturing the local structure of graphs in extremal graph theory, particularly in the study of dense graphs and their limits. For graphs G and H, the homomorphism density \hom(G, H) is defined as the probability that a uniformly random mapping from V(G) to V(H) preserves edges, formally \hom(G, H) = \frac{|\{f: V(G) \to V(H) \mid f \text{ is a homomorphism}\}|}{|V(H)|^{|V(G)|}}.^[45] This concept extends naturally to subgraph densities: for a fixed graph F and large graph G, the homomorphism density t(F, G) is given by

t(F, G) = \frac{1}{|V(G)|^{|V(F)|}} \times \left| \{ f: V(F) \to V(G) \mid f \text{ is a homomorphism} \} \right|,

which represents the expected density of homomorphic images of F in G. To obtain the density of unlabeled subgraphs isomorphic to F, one divides by the size of the automorphism group |\Aut(F)|, yielding the number of distinct copies as approximately t(F, G) \cdot |V(G)|^{|V(F)|} / |\Aut(F)|.^[45]^[46] In the theory of graph limits, sequences of graphs \{G_n\} with |V(G_n)| = n \to \infty are said to converge if their subgraph densities t(F, G_n) converge for every fixed simple graph F; such limits are compactly represented by graphons, which are symmetric measurable functions W: [0,1]^2 \to [0,1] serving as kernel objects that encode all homomorphism densities via integrals t(F, W) = \int_{[0,1]^{V(F)}} \prod_{e \in E(F)} W(x_e) \, dx. Convergence in this sense is metrized by the cut norm, introduced by Frieze and Kannan and refined by Lovász and Szegedy, where the cut distance \delta_\square(G, W) measures the supremum over subsets of the L^1 difference in edge distributions between G and W. This framework unifies discrete extremal problems with continuous optimization, enabling the analysis of asymptotic densities in large graphs. Homomorphism densities play a central role in extremal applications, notably through Sidorenko's conjecture, which posits that for any bipartite graph H and graphon W with edge density p = t(K_2, W), the density satisfies t(H, W) \geq p^{|E(H)|}, implying that random-like graphs minimize the density of bipartite subgraphs among those with fixed edge density.^[45] This convexity property highlights the extremal behavior of balanced incomplete graphs. Further, flag algebras provide a semidefinite programming method to bound and optimize t(F, G) under constraints like forbidden subgraphs, by decomposing densities into positive semidefinite combinations of flag types, leading to tight asymptotic extremal functions for various problems. Key results include the foundational work of Lovász and Szegedy establishing that right-convergent sequences admit graphon limits in the cut norm, facilitating the transfer of discrete inequalities to the continuous setting. In the 2020s, advances have focused on correlated densities, such as joint homomorphism counts t(F_1, F_2; G) for pairs of graphs, with progress on their inequalities via analytic methods. These developments extend Sidorenko-type results and enhance computational approaches in flag algebras, including computer-assisted proofs using search heuristics.^[47] AI techniques, such as reinforcement learning, are also being applied to extremal problems as of 2024.^[48] This continuous perspective connects to quasi-random graphs, where uniform subgraph densities matching the random model imply global randomness properties.^[45]

Graph Regularity and Quasi-Randomness

The Szemerédi regularity lemma provides a fundamental partitioning tool in extremal graph theory, asserting that every sufficiently large graph admits an equitable partition of its vertex set into a bounded number of clusters such that the edges between most pairs of clusters are uniformly distributed.^[49] Specifically, for every \epsilon > 0, there exists an integer M = M(\epsilon) such that any graph G = (V, E) on |V| = n vertices has a partition V = V_1 \cup \cdots \cup V_k with k \leq M, where each |V_i| \geq \epsilon n / k, the sizes |V_i| differ by at most 1, and all but at most \epsilon k^2 pairs (V_i, V_j) with i \neq j are \epsilon-regular.^[49] A pair of sets (U, V) is \epsilon-regular if for every X \subseteq U and Y \subseteq V with |X| \geq \epsilon |U| and |Y| \geq \epsilon |V|, the density satisfies

\left| \frac{e(X, Y)}{|X| |Y|} - \frac{e(U, V)}{|U| |V|} \right| < \epsilon,

where e(\cdot, \cdot) denotes the number of edges between the sets; this ensures that the bipartite subgraph between U and V behaves like a random bipartite graph with the given density.^[49] The original proof yields a tower-type upper bound on M(\epsilon), specifically a tower of exponentials of height polynomial in $1/\epsilon, and Gowers and others established that such tower-type bounds are necessary, with a tight lower bound on the tower height of \Theta(\epsilon^{-2}).^[50]^[49] Quasi-random graphs extend this notion by characterizing dense graphs that mimic the global edge distribution of random graphs G(n, p), particularly for p = 1/2, where edges are nearly uniformly present.^[51] A sequence of graphs (G_n) with n vertices and (p + o(1))\binom{n}{2} edges is quasi-random if the edges are asymptotically uniformly distributed, meaning that for any subsets S, T \subseteq V(G_n), |e(S, T) - p |S| |T|| = o(n^2).^[51] Chung, Graham, and Wilson proved that this uniform distribution is equivalent to several other properties typical of random graphs, including bounded discrepancy in the number of edges across subsets, asymptotic counts of small subgraphs (such as the number of C_4 cycles being (1 + o(1)) n^4 p^3 (1-p)), and spectral conditions where the second-largest eigenvalue of the adjacency matrix is o(np) while the largest is asymptotically np.^[51] One such equivalent criterion involves the total number of length-2 paths, which aligns closely with random expectations; for p=1/2, this implies \sum_v \binom{d_v}{2} + e(G_n) \sim n^3 / 8, reflecting the uniformity.^[51] In extremal graph theory, the regularity lemma and quasi-randomness facilitate proofs by approximating arbitrary dense graphs with simpler random-like structures, reducing complex counting problems to those solvable via probabilistic methods or averaging arguments.^[49] For instance, after obtaining an \epsilon-regular partition, one constructs a reduced graph on the clusters, where edges represent significant densities, and applies counting lemmas to embed forbidden subgraphs or bound homomorphism counts in the original graph.^[49] This approach is pivotal in dense extremal problems, such as those involving Turán numbers for non-bipartite graphs, where regularity partitions quasi-randomize bipartite sections to yield asymptotic densities.^[49] The lemma's role in the proof of the Erdős–Stone theorem exemplifies this, by leveraging regular partitions to control cross-edge densities between color classes in multipartite graphs.^[49]

Hypergraph Extremal Theory

Hypergraph extremal theory generalizes the principles of extremal graph theory to hypergraphs, where edges consist of r-tuples of vertices for r ≥ 2. An r-uniform hypergraph H = (V, E) has vertex set V and edge set E ⊆ \binom{V}{r}. For a fixed r-uniform hypergraph F and integer n, the Turán number ex(n, F) is defined as the maximum number of edges in an r-uniform hypergraph on n vertices that contains no subgraph isomorphic to F.^[19] This quantity measures the extremal size while avoiding F, analogous to the graph case when r=2. The hypergraph Turán density is then given by

\pi(F) = \lim_{n \to \infty} \frac{\ex(n, F)}{\binom{n}{r}},

which exists for any fixed F by the supersaturation theorem of Erdős.^[19] A central problem is determining ex(n, K_s^{(r)}), where K_s^{(r)} denotes the complete r-uniform hypergraph on s vertices (every r-subset is an edge). In 1964, Erdős conjectured that the extremal hypergraphs are the balanced complete (s-1)-partite r-uniform hypergraphs, yielding the asymptotic

\ex(n, K_s^{(r)}) \sim \left(1 - \frac{1}{s-1}\right) \binom{n}{r}

for s > r ≥ 3, with the Turán density π(K_s^{(r)}) = 1 - 1/(s-1).^[52] This remains open in general, though Erdős offered $1000 for its resolution. Partial progress includes stability results showing that near-extremal hypergraphs resemble the conjectured Turán construction. For instance, Pikhurko established exact extremal results for expanded complete 2-graphs and refined bounds using stability methods for certain forbidden subhypergraphs like the tetrahedron in 4-uniform hypergraphs.^[19] In the bipartite setting, analogs of the Zarankiewicz problem seek ex(n, K_{s,t}^{(r)}), the maximum edges avoiding the complete r-uniform bipartite hypergraph with parts of size s and t. Upper bounds of O(n^{r - 1/(s-1)}) have been obtained via analytic methods, while lower bounds from probabilistic constructions reach Ω(n^{r - 2/(r+1)} (\log n)^{1/(r^2-1)}).^[19] For forbidden loose cycles—where consecutive edges intersect in exactly one vertex—extremal results generalize bipartite cycle avoidance in graphs. Key challenges include the lack of explicit constructions matching upper bounds, with many results relying on non-constructive techniques like flag algebras or the container method. For 3-uniform cliques, the case of K_4^{(3)} remains unresolved, but recent progress includes exact densities for K_4^{(3)} minus an edge (2024)^[53] and quasirandom conditions ensuring K_5^{(3)}-freeness when link densities exceed 1/3 (2022).^[54] Recent 2025 advances further explore the algebraic degrees of Turán densities and methods to separate densities without explicit bounds.^[55]^[56]

Spectral Extremal Graph Theory

Spectral extremal graph theory leverages eigenvalues of the adjacency matrix to derive bounds on the presence of forbidden subgraphs, providing an analytic alternative to purely combinatorial approaches in extremal problems. The spectrum of a graph G consists of the eigenvalues \lambda_1(G) \geq \lambda_2(G) \geq \cdots \geq \lambda_n(G) of its adjacency matrix A(G), where \lambda_1(G), known as the spectral radius \rho(G), is particularly useful for bounding extremal functions. The Laplacian spectrum, derived from the Laplacian matrix L(G) = D(G) - A(G) where D(G) is the degree matrix, also finds applications but is less central to Turán-type results. These spectral tools enable precise inequalities relating graph structure to eigenvalue magnitudes, often yielding stability versions of classical theorems. A foundational result is Nosal's theorem from 1970, which states that if \rho(G)^2 > m(G) for a graph G with m(G) edges, then G contains a triangle K_3. Consequently, every triangle-free graph on n vertices satisfies \rho(G) \leq \sqrt{m(G)} \leq \sqrt{\lfloor n^2/4 \rfloor} \approx n/2, achieved by the balanced complete bipartite graph T(n,2). This bound marked the beginning of spectral analogs to extremal theorems.^[57]^[58] Nikiforov extended these ideas in a series of works, culminating in the spectral Turán theorem: For r \geq 2 and a graph G on n vertices, if \rho(G) > \rho(T(n,r)), then G contains a copy of K_{r+1}, where T(n,r) is the complete r-partite Turán graph on n vertices that maximizes edges without K_{r+1}. More generally, for an arbitrary forbidden graph H, the spectral extremal function \operatorname{spex}(n,H) = \max \{ \rho(G) : G is H-free on n vertices \} satisfies \operatorname{spex}(n,H) = \rho(\mathcal{T}), where \mathcal{T} is an extremal graph achieving \operatorname{ex}(n,H). For H = K_3, this yields \rho(G) \leq \rho(T(n,2)) \approx n/2 for K_3-free G. These results provide sharp thresholds via the equation

\rho(G) \leq \max \{ \rho(T) : T \text{ is } H\text{-free extremal on } n \text{ vertices} \}

for H-free graphs G. Key applications include Hoffman's bound, which upper-bounds the independence number \alpha(G) of a d-regular graph G by \alpha(G) \leq n \frac{-\lambda_n(G)}{d - \lambda_n(G)}, where \lambda_n(G) is the smallest eigenvalue; extensions handle non-regular cases and connect to chromatic number bounds. In the context of the Zarankiewicz problem, which seeks the maximum edges in bipartite graphs without K_{s,t}, spectral versions bound \operatorname{spex}(n, K_{s,t}) for bipartite H-free graphs. Recent advances, such as those determining the spectral extremum for linear forests (paths and even cycles as forbidden subgraphs) in bipartite graphs, confirm that the extremal spectral radius aligns with incidence graphs of projective planes or similar constructions for specific s,t, with bounds like \operatorname{spex}(n, K_{s,t}) \leq (t-1)^{1/s} n^{1 - 1/s} + o(n^{1 - 1/s}).^[59]^[60]^[61] The advantages of spectral methods lie in their provision of analytic proofs that circumvent combinatorial regularity lemmas, relying instead on linear algebra and trace methods. They also forge connections to random graphs, where spectral properties characterize quasi-randomness in one sentence: graphs with eigenvalues concentrated around the trivial ones behave like random models in extremal settings.

References

[1]
[PDF] Extremal Graph Theory
In this chapter we study how global parameters of a graph, such as its edge density or chromatic number, can influence its local substructures.
[2]
[PDF] Chapter 10 Extremal Theory
A graph E of order n with ex(n; G) edges and not containing G as a subgraph is called an extremal graph for this problem. The complete solution of any such ...
[3]
Extremal Graph Theory - University of Warwick
Mar 3, 2010 · The basic aim of extremal graph theory is to show that a graph with sufficiently many edges must contain as a subgraph some desired structure.
[4]
[PDF] Extremal Graph Theory for Degree Sequences - arXiv
Oct 7, 2015 · In this survey, we just focus on some extremal properties of graphs with given degree sequences. Graph invariants such as the spectral radius, ...
[5]
[PDF] Extremal Theory for Cliques in Graphs - Emory University
Mar 22, 1996 · tempts to determine the relation between graph invariants (such as order, size or ... and Hanson, D., Degrees and Matchings, J. Combin. Theory, ...
[6]
[PDF] Extremal Graph Theory Contents - UCSD Math
Jan 4, 2020 · Definition. Given a positive integer n and graph H, define the extremal number of H. (on graphs with n vertices), denoted ex(n, H), to be the ...
[7]
[PDF] extremal graph theory 1 - classical results
Given a natural number n and a graph H, the extremal number ex(n, H) is the largest number of edges in an n-vertex graph that does not contain H as a subgraph.<|control11|><|separator|>
[8]
[PDF] Chapter 9 Introduction to Extremal Graph Theory - UCSD Math
An F-free graph with n vertices and ex(n,F) edges is called an extremal graph. Let F = P2 = K1,2.
[9]
Extremal functions for sparse minors - Advances in Combinatorics
Jul 25, 2022 · The notion of a graph minor, which generalizes graph subgraphs, is a central notion of modern graph theory. Classical results concerning ...
[10]
[PDF] Extremal graph theory and Ramsey theory
Jul 7, 2025 · To summarize, the statement of ESS is an explicit asymptotic formula for the extremal number of any H. The lower bound was pretty easy ...
[11]
[PDF] Note on Combinatorics and its Subfields - Research and Reviews
Mar 7, 2022 · The most traditional branch of combinatorics is enumerative combinatorics, which focuses on counting the number ... Extremal combinatorics ...
[12]
[PDF] Extremal Graph Theory and Its Applications Benny Sudakov
In this talk, we survey several classical problems and results in this area and present some interesting applications of Extremal Graph Theory to other.Missing: motivations | Show results with:motivations
[13]
[PDF] Graph Theory and Additive Combinatorics - Yufei Zhao
Jun 18, 2024 · This is the first introductory graduate level textbook to focus on a unifying set of topics connecting graph theory and additive combinatorics.
[14]
[PDF] EXTREMAL PROBLEMS IN GRAPH THEORY: A COMBINATORIAL ...
Nov 1, 2025 · The extremal theory of graphs considers the study of how large or small a graph invariant may be, according to certain constraints. The field ...
[15]
[PDF] A Unified Approach for Extremal General Exponential Multiplicative ...
Jul 9, 2023 · In chemistry: Extremal graph theory is used to comprehend the structure of molecules. Molecular graphs can be modeled as graphs. A graph's ...
[16]
An extremal problem for sets with applications to graph theory
An extremal problem for sets with applications to graph theory. Author links open overlay panelNoga Alon.
[17]
On the applications of Extremal Graph Theory to Coding Theory and ...
Explicit constructions in Extremal graph theory give appropriate lower bound for Turan type problems. In the case of prohibited cycles explicit ...
[18]
[PDF] Hypergraph Turán Problems - People
As for Turán problems, there are few known results for codegree problems, even asymptotically. The tetrahedron K3. 4 is again one of the first interesting ...Missing: 1925 | Show results with:1925
[19]
(PDF) Ramsey-Turán theory - ResearchGate
Aug 8, 2025 · Ramsey- and Turán-type problems were always strongly related to each other. Motivated by an observation of Paul Erdős, it was Turán who ...
[20]
(PDF) Turán's graph theorem - ResearchGate
PDF | One of the fundamental results in graph theory is the theorem of Turán from 1941, which initiated extremal graph theory. Turán's theorem was.Missing: original | Show results with:original
[21]
[PDF] Introduction. If the numbers of vertices and edges of a (linear)
It has been conjectured that every graph with 2n vertices and n2+k edges must contain at least kn triangles if k < n, and this has been proved for k <_3 (Erdös; ...
[22]
[PDF] Paul Erd˝os' Influence on Extremal Graph Theory
Graphs described in (ii) do not exist for all n, but we get asymptotically extremal graphs for all n, by taking those graphs in which one 2-connected component ...
[23]
[PDF] Extremal Graph Theory
Let us fix a function f, and denote by ex(n, L,f) the maximum number of edges in a graph G" containing no Le and at most f(n) independent vertices. Our interest ...
[24]
[PDF] Flag Algebras - Full-Time Faculty
Flag algebras are related to graph algebras (introduced in the context of ... σ0-flag. Page 26. 26. ALEXANDER A. RAZBOROV. A sequence {Pn} of probability ...
[25]
[PDF] On edge-ordered graphs with linear extremal functions
Turán-type extremal graph theory asks how many edges an n-vertex simple graph can have if it does not contain a subgraph isomorphic to a forbidden graph.Missing: 2024 spectral variants
[26]
[PDF] Section 12.2. Turán's Theorem
Jun 5, 2022 · The proof of Turán's Theorem we give here is due to A. A. Zykov in “On Some Properties of Linear Complexes”. [in Russian] Matematicheskii ...<|control11|><|separator|>
[27]
[PDF] EXTREMAL GRAPH THEORY 1 Turán's theorem
A complete k-partite graph is a graph whose vertex-set can be split into k pair- wise disjoint parts (not necessarily all of them empty) so that two ...Missing: tournament 1920s
[28]
[2004.10685] Exact stability for Turán's Theorem - arXiv
Apr 22, 2020 · The Stability Theorem of Erdős and Simonovits shows that if a K_{r+1}-free graph with n vertices has close to the maximal t_r(n) edges, then it ...
[29]
On the structure of linear graphs - Project Euclid
December 1946 On the structure of linear graphs. P. Erdös, A. H. Stone. Bull. Amer. Math. Soc. 52(12): 1087-1091 (December 1946). ABOUT; FIRST PAGE; CITED BY.
[30]
A proof of the stability of extremal graphs, Simonovits' stability from ...
The Turán number ex ( n , L ) is defined as the largest size of an n-vertex, -free graph. Erdős and Simonovits [12] gave the following general asymptotic for ...
[31]
[PDF] Spectral extrema of graphs: Forbidden star-path forests - arXiv
Feb 24, 2023 · A graph is H-free if it does not contain a copy of H as a subgraph. The Turán number ex(n, H) is the maximum number of edges in a graph of order ...<|control11|><|separator|>
[32]
[PDF] Forbidden subgraphs and complete partitions - arXiv
Aug 12, 2025 · ... graph that does not contain any graph in H as a subgraph. When H = {H}, we write ex(n, H) instead of ex(n,H). ... in extremal graph theory is ...
[33]
A conjecture on trees (proposed by Erdös and Sós, 1962)
One of the most tantalizing problems in extremal graph theory is the following classic problem: A conjecture on trees (proposed by Erdös and Sós, 1962).
[34]
On the Erdős-Sós conjecture for trees with bounded degree - arXiv
Jun 24, 2019 · We prove the Erd\H os--Sós conjecture for trees with bounded maximum degree and large dense host graphs. As a corollary, we obtain an upper ...
[35]
[1901.06137] Exact bipartite Turán numbers of large even cycles
Jan 18, 2019 · The bipartite Turán number ex(m,n,H) is the maximum edges in an H-free bipartite graph with parts of sizes m and n. The paper proves ex(m,n,C_{ ...
[36]
[1310.6766] Extremal numbers for odd cycles - arXiv
Oct 24, 2013 · We describe the C_{2k+1}-free graphs on n vertices with maximum number of edges. The extremal graphs are unique except for n = 3k-1, 3k, 4k-2, or 4k-1.Missing: finer results
[37]
[2401.10853] Kővári-Sós-Turán theorem for hereditary families - arXiv
Jan 19, 2024 · The celebrated Kővári-Sós-Turán theorem states that any n-vertex graph containing no copy of the complete bipartite graph K_{s,s} has at most O_s(n^{2-1/s}) ...Missing: original URL
[38]
[PDF] COMPACTNESS RESULTS IN EXTREMAL GRAPH THEORY
A typical extremal graph problem is to determine ex (n, L), or at least ... ex (n, C 4) =2 +o(n. 312) . These two results show that the exclusion of the ...Missing: C_4) open
[39]
[PDF] SUPERSATURATED GRAPHS AND HYPERGRAPHS
Theorem 2 and the Lovász-Simonovits theorem we deduce the Erdős-Simonovits sharpening of the Erdős-Stone theorem, (see below). One of our most general ...
[40]
[PDF] The history of degenerate (bipartite) extremal graph problems
Degenerate extremal graph problems, often called Turán type, involve maximizing a graph's edge count under a property P, rooted in Turán's theorem.
[41]
None
### Summary of Recent Improvements on Asymptotic Exponents for Zarankiewicz Problem z(n;s,t) Using Algebraic Methods (2023-2024)
[42]
None
**Summary of Improvements on Zarankiewicz Numbers (z(m,n;s,t))**
[43]
[PDF] Large networks and graph limits László Lovász
... cut distance. 127. 8.1. The cut distance of graphs. 127. 8.2. Cut norm and cut distance of kernels. 131. 8.3. Weak and L1-topologies. 138. Chapter 9. Szemerédi ...
[44]
[PDF] Limits of randomly grown graph sequences - arXiv
May 23, 2009 · The cut-norm introduced in [6] is defined for W ∈ W by. kWk = sup. S ... Szegedy: Limits of dense graph sequences, J. Comb. Theory B 96 ...
[45]
[PDF] arXiv:2308.07422v1 [math.CO] 14 Aug 2023
Aug 14, 2023 · Many important problems and results in extremal graph theory can be framed as certifying the validity of polynomial inequalities in homomorphism ...
[46]
[PDF] The Regularity Lemma and Its Applications in Graph Theory
Szemerédi's Regularity Lemma is an important tool in di- screte mathematics. It says that, in some sense, all graphs can be ap- proximated by random-looking ...
[47]
Quasi-random graphs | Combinatorica
Mar 5, 1988 · Chung, F.R.K., Graham, R.L. & Wilson, R.M. Quasi-random graphs. Combinatorica 9, 345–362 (1989). https://doi.org/10.1007/BF02125347. Download ...
[48]
[PDF] ON EXTREMAL PROBLEMS OF GRAPHS AND GENERALIZED ...
An r-graph is a graph whose basic elements are its vertices and r-tuples. It is proved that to every 1 and r there is an e(l, r) so that for n > no every r- ...
[49]
The Number of Triple Systems Without Even Cycles | Combinatorica
Feb 11, 2019 · A Hypergraph Analog of Dirac's Theorem for Long Cycles in 2-Connected Graphs. Article 15 April 2024. Orientations Making k-Cycles Cyclic.<|separator|>
[50]
[PDF] Eigenvalues of graphs - Semantic Scholar
Bounds of eigenvalues of a graph ... We prove two conjectures in spectral extremal graph theory involving the linear combinations of graph eigenvalues.Missing: triangles | Show results with:triangles
[51]
[PDF] On a theorem of Nosal arXiv:2104.12171v1 [math.CO] 25 Apr 2021
Apr 25, 2021 · Simic, An Introduction to the Theory of Graph. Spectra ... Nosal, Eigenvalues of Graphs, Master's thesis, University of Calgary, 1970.<|control11|><|separator|>
[52]
Eigenvalue bounds for independent sets - ScienceDirect.com
We derive bounds on the size of an independent set based on eigenvalues. This generalizes a result due to Delsarte and Hoffman.
[53]
Spectral Extrema for Graphs: The Zarankiewicz Problem
Sep 25, 2009 · Abstract. Let G G be a graph on n n vertices with spectral radius λ λ (this is the largest eigenvalue of the adjacency matrix of G G ).
[54]
The bipartite Turán number and spectral extremum for linear forests
Nov 1, 2023 · ... spectral Zarankiewicz problem (see [2], [30]). In 2015, Zhai, Lin, and Gong [29] obtained the maximum spectral radius of a P k -free ...