Fact-checked by Grok 2 weeks ago

Turán's theorem

Turán's theorem is a cornerstone of extremal graph theory, providing the precise maximum number of edges in an undirected graph on n vertices that avoids a complete subgraph K_r for integers r \geq 2 and n \geq 1. The theorem states that this maximum, denoted \operatorname{ex}(n, K_r), is achieved uniquely by the Turán graph T(n, r-1), a complete (r-1)-partite graph whose vertex parts are as equal in size as possible (differing by at most 1). Proved by Hungarian mathematician in 1941, the theorem originated from his work on extremal problems in during , including a period of imprisonment. It generalizes earlier results, such as Mantel's theorem (1907), which corresponds to the case r=3 and bounds the edges in triangle-free graphs by \lfloor n^2/4 \rfloor. Turán's proof, originally published in Hungarian, was later translated and reproduced in English, establishing it as the foundation for the field of . The Turán graph T(n, s) for s = r-1 maximizes edges among all K_{s+1}-free s on n vertices, with the edge count given by t_s(n) = \frac{1}{2} \left(1 - \frac{1}{s}\right) n^2 - \epsilon, where \epsilon is a small error term bounded by s/2 to account for unequal part sizes when s does not divide n. Any exceeding this edge bound must contain a K_r, making the a sharp criterion for the emergence of cliques. Proofs rely on symmetrization techniques, such as Zykov's of averaging over permutations to construct the balanced complete multipartite . Beyond its core statement, Turán's theorem has profound implications in , influencing problems like the Erdős–Stone theorem, which extends it to non-complete forbidden subgraphs and reveals asymptotic densities for general graph avoidance. It also connects to stability results, such as Erdős's refinement showing that graphs near the extremal edge count are close in structure to Turán graphs. The theorem's applications span , including approximation algorithms for dense subgraph detection, and real-world modeling in where clique avoidance models stability.

Statement and Key Concepts

Formal Statement

Turán's theorem is a foundational result in extremal graph theory that determines the maximum number of edges possible in an n-vertex graph without containing a complete subgraph K_r, where r \geq 2 is an integer. The Turán number, denoted \operatorname{ex}(n, H), is defined as the maximum number of edges in any simple graph on n vertices that does not contain a subgraph isomorphic to a fixed graph H. For H = K_r, Turán's theorem asserts that \operatorname{ex}(n, K_r) = t(n, r-1), where t(n, r-1) denotes the number of edges in the Turán graph T(n, r-1). The Turán graph T(n, r-1) is the unique graph achieving this maximum. To compute t(n, r-1), write n = q(r-1) + s where q = \lfloor n/(r-1) \rfloor and $0 \leq s < r-1; then T(n, r-1) consists of s partite sets of size q+1 and (r-1) - s partite sets of size q, with all possible edges between different sets. This is asymptotically \left(1 - \frac{1}{r-1}\right) \frac{n^2}{2}. The theorem further guarantees that every n-vertex graph with more than t(n, r-1) edges must contain a K_r as a subgraph.

Turán Graph and Its Properties

The Turán graph T(n, r-1) is constructed as the complete (r-1)-partite graph on n vertices whose partite sets are as equal in size as possible. Specifically, let k = \lfloor n/(r-1) \rfloor; then there are s = n \mod (r-1) partite sets of size k+1 and (r-1) - s partite sets of size k. Edges are present between every pair of vertices in distinct partite sets, with no edges within the same set. This graph is balanced in the sense that the partite sets differ in size by at most one, making it a canonical example of a complete multipartite graph. It contains no K_r subgraph, as any clique can include at most one vertex from each partite set. The Turán graph T(n, r-1) achieves the Turán number \mathrm{ex}(n, K_r), the maximum number of edges in any K_r-free graph on n vertices, and is unique up to isomorphism as the extremal graph in this class. The number of edges in T(n, r-1), denoted t(n, r-1), is given by t(n, r-1) = \frac{1}{2} \left( n^2 - \sum_{i=1}^{r-1} s_i^2 \right), where s_1, \dots, s_{r-1} are the sizes of the partite sets. This formula arises because the total possible edges in the complete graph K_n is n^2/2, and the missing edges are precisely those within the partite sets, totaling \frac{1}{2} \sum_{i=1}^{r-1} s_i(s_i - 1), which simplifies to the expression above. The balanced partition maximizes t(n, r-1) among all complete (r-1)-partite graphs on n vertices, since the sum \sum s_i^2 (with \sum s_i = n) is minimized when the s_i differ by at most one, by the convexity of the function x \mapsto x^2.

Special Cases

Mantel's Theorem

Mantel's theorem constitutes the case r = 3 of Turán's theorem, focusing on the maximum number of edges in graphs avoiding the complete graph K_3, or equivalently, triangle-free graphs. It states that the extremal function \operatorname{ex}(n, K_3) = \left\lfloor \frac{n^2}{4} \right\rfloor, with equality attained precisely by the complete bipartite graph K_{\left\lfloor n/2 \right\rfloor, \left\lceil n/2 \right\rceil}. This balanced bipartition maximizes the edges while ensuring no odd cycles of length 3 form, as all edges lie between the two parts. Proved by Dutch mathematician in 1907, the result predates Pál Turán's generalization to arbitrary cliques by over three decades, marking it as a pioneering achievement in extremal graph theory. , presented in a technical report on graph construction problems, used a degree-based argument to show that exceeding the bound forces a triangle. Its historical significance lies in establishing the bipartite nature of maximal triangle-free graphs, influencing subsequent developments in and structural graph theory. The theorem's implications are profound: any simple graph on n vertices with more than \left\lfloor \frac{n^2}{4} \right\rfloor edges necessarily contains a triangle, providing a sharp threshold for the emergence of K_3-subgraphs. This not only characterizes the extremal triangle-free graphs but also underpins applications in areas like network design and algorithm analysis, where avoiding dense substructures is crucial. For example, when n = 2m is even, the Turán graph T(n, 2) = K_{m,m} realizes exactly m^2 = \frac{n^2}{4} edges, demonstrating the bound's tightness and the optimality of equitable bipartitions.

Degree Conditions for Forcing Triangles and Other r=3 Variants

A fundamental degree-based extension of Mantel's theorem concerns the minimum degree condition that forces the presence of a triangle in a graph. Specifically, any graph G on n vertices with minimum degree δ(G) > n/2 must contain a K_3, as this condition implies that the number of edges e(G) > n^2/4, exceeding the extremal number given by Mantel's theorem. The contrapositive states that every on n vertices has minimum degree at most n/2. This bound is sharp, achieved by the K_{floor(n/2), ceil(n/2)}, where all degrees are floor(n/2) or ceil(n/2). This minimum degree condition arises directly from averaging the degrees in the extremal configuration of Mantel's theorem, where the balanced maximizes both the number of edges and the minimum among . In non-extremal , the minimum can be much lower—for instance, approaching 0 in sparse graphs like trees—but the upper bound of n/2 holds universally for the minimum in the absence of triangles. A stronger condition for is provided by the Andrásfai–Erdős–Sós theorem, which states that if G is a on n vertices with minimum δ(G) > (2n)/5, then G is bipartite. More generally, for forbidding K_r, the theorem asserts that if δ(G) > \frac{3r-7}{3r-4} n, then G is (r-1)-colorable. For r=3, this yields δ(G) > (2n)/5 for the 2-colorability conclusion under the triangle-free assumption, offering a tighter bound than the simple n/2 threshold when the graph is not bipartite. The proof relies on showing that high minimum in a non-(r-1)-colorable K_r-free graph leads to a via potential functions or symmetrization techniques. This result refines extremal bounds by linking conditions to chromatic properties in the r=3 case (forbidding K_3). Another variant involves degree sums for adjacent vertices, analogous to Ore's condition in graph theory. If G has an edge uv with deg(u) + deg(v) > n, then u and v share a common neighbor, forming a uvw. The contrapositive implies that in a , every edge uv satisfies deg(u) + deg(v) ≤ n. This condition generalizes the edge-count bound by focusing on local degree sums rather than global averages, and it is sharp in the balanced , where adjacent vertices have degrees summing to n. Such local conditions are useful for algorithmic detection of s or analyzing sparse subgraphs. These degree variants have implications for stability and degeneracy in the triangle-free setting. The Erdős–Simonovits stability for Mantel's ensures that triangle-free s with edge count close to the extremal value have structure close to the balanced , implying that s are nearly uniform around n/2, with deviations controlled by the edge deficit. Regarding degeneracy, triangle-free s are (n/2)-degenerate in the sense that every has a of at most n/2, following from the minimum bound applied inductively. This property aids in bounding arboricity and coloring, as triangle-free s admit equitable 2-colorings in the extremal case and have degeneracy at most n/2 overall. Note that the case r=2 in Turán's theorem is trivial: ex(n, K_2) = 0, as any edge forms a K_2.

Proof Methods

Induction on Vertices

The inductive proof of Turán's theorem, originally presented by , proceeds by induction on the number of vertices n to establish that the maximum number of edges in a K_{r+1}-free graph on n vertices is e(T(n,r)), achieved uniquely by the Turán graph T(n,r). For the base case, when n \leq r, any graph on n vertices is K_{r+1}-free, and the complete graph K_n maximizes the edges with \binom{n}{2} edges, which coincides with e(T(n,r)) = \binom{n}{2} since T(n,r) = K_n in this range. More generally, the induction anchors on small n where the bound holds trivially as no K_{r+1} can form. In the inductive step, assume the theorem holds for all K_{r+1}-free graphs on fewer than n vertices, where n > r. Let G be a K_{r+1}-free graph on n vertices with the maximum number of edges, so e(G) = \ex(n, K_{r+1}). The minimum degree in T(n,r) is \delta(T(n,r)) = n - \lceil n/r \rceil, the complement of the largest part size. Suppose \delta(G) < \delta(T(n,r)); let v be a vertex of minimum degree d(v) = \delta(G). Then G - v is K_{r+1}-free on n-1 vertices with e(G - v) = e(G) - d(v) \leq \ex(n-1, K_{r+1}) = e(T(n-1,r)) by the inductive hypothesis. Thus, e(G) \leq e(T(n-1,r)) + \delta(T(n,r)) - 1 < e(T(n,r)), contradicting the maximality of G. Therefore, \delta(G) \geq \delta(T(n,r)). Now remove a vertex v of minimum degree, so d(v) = \delta(G) \geq \delta(T(n,r)). Then e(G - v) = e(G) - d(v) \geq e(T(n,r)) - \delta(T(n,r)) = e(T(n-1,r)). By the inductive hypothesis, since G - v is K_{r+1}-free and achieves the maximum edges on n-1 vertices, G - v = T(n-1,r), the balanced complete r-partite graph with parts V_1, \dots, V_r of sizes as equal as possible. The neighbors of v cannot include vertices from all r parts, as that would form a K_{r+1} with one vertex from each part plus v. Thus, v has no edges to at least one part, say V_i. Moreover, d(v) \geq \delta(T(n,r)) = (n-1) - \lceil (n-1)/r \rceil implies v connects to all vertices outside the largest possible missed part; specifically, the non-neighbors of v form an independent set (a subset of V_i), and to meet the degree bound, v must miss exactly the smallest part and connect completely to the other r-1 parts. To establish that G is complete r-partite, suppose v fails to connect to some vertex u in a part V_j (j \neq i) to which v has some edges. Adding the edge vu does not create a K_{r+1}, because any potential clique including vu can take at most one vertex from V_j (independent set), vertices from the other r-2 parts that v connects to, and cannot include from V_i (no edges from v), yielding at most an r-clique. Thus, adding vu increases edges without forming K_{r+1}, contradicting maximality. Hence, v connects completely to V_1 \cup \cdots \cup V_{i-1} \cup V_{i+1} \cup \cdots \cup V_r and not at all to V_i, so G is the complete r-partite graph with parts V_1, \dots, V_{i-1}, V_i \cup \{v\}, V_{i+1}, \dots, V_r. The degree condition further ensures the parts are balanced, as assigning v to a non-largest part would yield d(v) < \delta(T(n,r)), a contradiction. Therefore, G = [T(n,r)](/page/Turán_graph), proving uniqueness. This inductive structure demonstrates that any K_{r+1}-free graph with fewer than e(T(n,r)) edges cannot exceed the bound, as the extremal case is uniquely achieved by the balanced complete r-partite graph.

Maximal Degree Vertex Approach

The maximal degree vertex approach provides a recursive proof of Turán's theorem by constructing an auxiliary complete multipartite graph that dominates the original graph in terms of edge count, thereby establishing the extremal bound. Consider a K_{r+1}-free graph G on n vertices. Select a vertex v of maximum degree d = \Delta(G). The induced subgraph G[N(v)] on the d neighbors of v must be K_r-free, as any clique of size r in N(v) would combine with v to form a forbidden K_{r+1}. To maximize the edges, the proof assumes by induction that G[N(v)] is edge-maximal under this constraint, so its structure approximates the Turán graph T(d, r-1), the complete (r-1)-partite graph on d vertices with parts as equal as possible. The remaining graph G - v is analyzed recursively, but the key insight lies in building a complete r-partite graph H on the vertex set of G such that the degree sequence of H majorizes that of G (i.e., when sorted decreasingly, each degree in H is at least the corresponding degree in G). This majorization implies e(H) \geq e(G). The partite sets of H are formed by taking the (r-1) parts from the recursive construction on N(v) and adding a new independent set consisting of v union the non-neighbors of v (denoted U = V(G) \setminus N), with all possible cross-edges added between this new set and the parts on N(v). Since v has maximum degree, vertices in U have degree at most d in G, and any edges within U deleted in H are compensated by the added cross-edges to N(v), ensuring the degree condition holds without creating a K_{r+1}. The recursion continues by layering these partite sets, effectively decomposing G into a balanced complete r-partite structure. As T(n,r) maximizes edges among all r-partite graphs on n vertices, it follows that e(G) \leq e(T(n,r)), with equality precisely when G \cong T(n,r). This method, originally due to Erdős, intuitively demonstrates the extremal construction by iteratively peeling away maximum-degree vertices, revealing why balanced part sizes optimize the edge count in the absence of K_{r+1}.

Zykov Symmetrization

Zykov's symmetrization provides an elegant proof of Turán's theorem by iteratively transforming a K_{r+1}-free graph into the Turán graph T(n,r), the unique complete r-partite graph on n vertices with parts as equal as possible, without decreasing the number of edges. The method relies on constructing "twin" vertices—non-adjacent vertices with identical neighborhoods—to enforce symmetry while preserving the forbidden subgraph property. This approach demonstrates that any K_{r+1}-free graph with the maximum number of edges must be T(n,r). The core operation of Zykov symmetrization proceeds as follows: Consider two non-adjacent vertices u and v in a K_{r+1}-free graph G with \deg(u) < \deg(v). Replace the neighborhood of u entirely with that of v, by deleting all edges incident to u and adding edges from u to every neighbor of v. This sets N(u) = N(v) in the resulting graph G', making u a twin of v (since u and v remain non-adjacent, as v \notin N(v)). The number of edges increases by \deg(v) - \deg(u) > 0, and G' remains K_{r+1}-free: any in G' containing u consists of u plus a clique in N(u) = N(v), which together with v would form a larger clique in G, contradicting the assumption. If G is edge-maximal K_{r+1}-free, applying this operation would contradict maximality unless no such pair u, v exists, implying that all non-adjacent vertices in G have equal . The process can then continue with pairs of equal , where the operation preserves the edge count while creating more twins. Iterating this symmetrization leads to a where non-adjacency is an (transitive, as symmetrizing pairs enforces consistent neighborhoods across classes), partitioning the vertices into at most r independent sets. The resulting structure is a complete multipartite , and since the original G had at least as many edges as this final , maximality forces it to be T(n,r), the balanced r-partite maximizing edges among such structures. This technique was introduced by A.A. Zykov in 1949, providing an independent proof of Turán's theorem originally established in 1941, and it highlights the role of symmetry in extremal graph theory.

Lagrangian and Optimization Techniques

One approach to proving Turán's theorem employs quadratic optimization techniques, formulating the maximum number of edges in a K_{r+1}-free graph as the solution to a continuous relaxation problem. Consider a graph G on n vertices with adjacency matrix A, where A_{ij} = 1 if vertices i and j are adjacent and 0 otherwise. The quadratic form f_G(x) = x^T A x = 2 \sum_{i < j, \, \{i,j\} \in E(G)} x_i x_j is maximized over the standard simplex S = \{ x \in \mathbb{R}^n \mid x \geq 0, \, \sum_{i=1}^n x_i = 1 \}. This relaxation captures the edge count via the objective, as evaluating at the uniform vector x = (1/n, \dots, 1/n) yields f_G(x) = 2 |E(G)| / n^2, so |E(G)| = (n^2 / 2) f_G(x) \leq (n^2 / 2) \max_{y \in S} f_G(y). The Motzkin-Straus theorem establishes that \max_{x \in S} f_G(x) = 1 - 1/\omega(G), where \omega(G) is the clique number of G, achieved by setting x uniform on the vertices of a maximum clique. For a K_{r+1}-free graph, \omega(G) \leq r, so \max f_G(x) \leq 1 - 1/r. Thus, |E(G)| \leq (1 - 1/r) n^2 / 2, yielding the Turán number \mathrm{ex}(n, K_{r+1}). Equality holds for the Turán graph T(n,r), the complete r-partite graph on n vertices with parts as equal as possible. To solve this optimization, Lagrangian methods can be applied by introducing a multiplier \lambda for the equality constraint \sum x_i = 1, forming the Lagrangian \mathcal{L}(x, \lambda) = x^T A x + \lambda (1 - \sum x_i). The Karush-Kuhn-Tucker (KKT) conditions for stationarity require that for each i with x_i > 0, the partial derivative \frac{\partial \mathcal{L}}{\partial x_i} = 2 \sum_{j \neq i} A_{ij} x_j - \lambda = 0, implying all such vertices have the same weighted neighborhood sum. This condition is satisfied when the support of x induces a clique and x is uniform thereon, enforcing independence across potential larger cliques via the non-negativity constraints (i.e., x_k = 0 for vertices outside the support prevents products \prod x_v > 0 over any K_{r+1}). For the Turán graph, the optimizer partitions the vertices into r equal independent sets, with x uniform across all vertices achieving the bound. Spectral interpretations further connect this to eigenvalues: the maximum \max_{x \in S} x^T A x relates to the largest eigenvalue of A restricted to the simplex, and for K_{r+1}-free graphs, eigenvalue bounds confirm the optimal value (1 - 1/r) n^2 / 2. This optimization approach provides the Turán number as the value of the relaxed problem.

Probabilistic Method

One approach in the probabilistic method for proving Turán's theorem involves constructing a complete r-partite graph on n vertices via a random partition of the vertex set into r parts. Specifically, assign each vertex independently and uniformly at random to one of r labels (colors). The resulting graph includes an edge between two vertices if and only if they receive different labels, ensuring it is r-partite and thus contains no clique of size r+1. To bound the number of edges, consider the in this random model. For any fixed pair of vertices, the probability they receive the same label is 1/r, so the probability they receive different labels—and thus form an edge—is 1 - 1/r. The expected number of edges is therefore \binom{n}{2} \left(1 - \frac{1}{r}\right). Since this expectation is asymptotic to the number of edges in the Turán graph t(n, r) (with t(n, r) = \left(1 - \frac{1}{r}\right) \frac{n^2}{2} + ), there must exist a realization with at least t(n, r) edges that avoids K_{r+1}, establishing the lower bound on the Turán number ex(n, K_{r+1}). A variant discussed by Alon and Spencer uses the for derandomization, particularly to ensure the random partition yields parts of nearly equal size while maintaining the edge count close to the expectation. This involves defining bad events for each part deviating significantly from size n/r and applying the lemma to show a positive probability of avoiding all such events, yielding an explicit construction approximating the balanced Turán graph. This probabilistic construction offers advantages in extensibility, providing approximate lower bounds for the Turán number in hypergraphs by analogous random r-colorings of vertices, where the expected proportion of non-hyperedges aligns with 1 minus the probability of monochromatic hyperedges.

Hypergraph Extensions

Turán's Problem for Hypergraphs

Turán's problem for hypergraphs generalizes the classical setting to higher-uniform structures, seeking the maximum number of edges in a hypergraph avoiding a specified forbidden subhypergraph. Specifically, for a fixed k-uniform hypergraph F on m vertices, the extremal number \mathrm{ex}(n, F) is defined as the largest possible number of k-edges in a k-uniform hypergraph on n vertices that does not contain a copy of F as a subhypergraph, where a subhypergraph means an injection of the vertices of F such that every k-edge of F maps to a k-edge in the host . This function captures the trade-off between size and forbidden configurations in theory, analogous to the graph case where k=2 and F=K_{r+1} yields the well-known Turán number. The central problem in this area, posed by Turán, concerns the complete k-uniform hypergraph K_{r+1}^{(k)} on r+1 vertices, which consists of all possible \binom{r+1}{k} k-edges on its vertex set. A natural generalization from the graph case is the balanced complete r-partite k-uniform hypergraph T^{(k)}(n, r), where the n vertices are partitioned into r parts of sizes as equal as possible (differing by at most 1), and a k-subset forms an edge if and only if its vertices lie in distinct parts, ensuring at most one vertex per part. This partite structure avoids K_{r+1}^{(k)} by the pigeonhole principle: any r+1 vertices must place at least two in the same part, rendering any k-subset containing those two a non-edge in the construction. This provides a lower bound for \mathrm{ex}(n, K_{r+1}^{(k)}). Turán posed the problem of determining the exact value, which remains open for k>2, with specific conjectures for small cases such as \pi(K_4^{(3)}) = 5/9 (see below). The problem holds completely for k=2, reducing to Turán's theorem on graphs, where T^{(2)}(n, r) is the complete r-partite graph with balanced parts, maximizing edges without a clique K_{r+1}. However, for k>2, the problem remains unsolved in general. For the basic case r=2 of forbidding K_3^{(k)}, the construction T^{(k)}(n, 2) admits k-edges only spanning both parts with at most one vertex each, which is empty for k>2; for k=3, this correctly gives \mathrm{ex}(n, K_3^{(3)}) = 0 (no edges), while for k>3, the forbidden K_3^{(k)} has no edges, so \mathrm{ex}(n, K_3^{(k)}) = \binom{n}{k} trivially. Turán originally formulated this hypergraph extension in 1941 as part of his foundational work on extremal problems, motivated by applications in and . Subsequent progress includes partial bounds and asymptotic results by Erdős, such as phenomena and estimates for specific F with chromatic number greater than 2, though the exact values for most complete forbidden hypergraphs elude resolution.

Turán Density and Ex(n, F) for Uniform Hypergraphs

The Turán density of a k-uniform F is defined as \pi(F) = \lim_{n \to \infty} \frac{\ex(n, F)}{\binom{n}{k}}, where \ex(n, F) denotes the maximum number of edges in an n-vertex k-uniform that does not contain a copy of F as a subhypergraph. This limit exists for every F due to the , which implies that any with sufficiently many edges must contain many copies of F, allowing the extremal function to be asymptotically determined. For the complete k-uniform hypergraph K_s^{(k)} on s vertices, determining \pi(K_s^{(k)}) is a central open problem in extremal hypergraph theory, generalizing Turán's theorem from graphs. Turán posed the problem and provided constructions for lower bounds, but exact values remain unknown except in trivial or small cases (such as when s = k, where \pi(K_s^{(k)}) = 0, or when s < k, where \pi(K_s^{(k)}) = 1). In general, the conjectured density does not follow the simple $1 - 1/(s-1) form from the graph case (k=2), and the problem is notoriously difficult for k \ge 3 and s > k. Asymptotic results build on extensions of the Erdős–Stone theorem, which, via supersaturation arguments, show that if F has chromatic number r+1 (the minimum number of colors needed to color the vertices so no edge is monochromatic), then \pi(F) \ge 1 - 1/r, with equality holding in the graph case but strict inequalities often arising for hypergraphs due to the more restrictive edge structures. A prominent example is the 3-uniform case k=3, s=4, where Turán conjectured \pi(K_4^{(3)}) = 5/9, attained asymptotically by the balanced blow-up of the 3-vertex 3-uniform hypergraph with edges \{1,1,2\}, \{2,2,3\}, \{3,3,1\}, and \{1,2,3\}. This provides the lower bound of $5/9, while upper bounds have been established using the flag algebras method. Razborov applied flag algebras to obtain \pi(K_4^{(3)}) \le 0.561666 in 2008, with subsequent refinements confirming the method's power for bounding densities of small forbidden configurations on 4 vertices. Pikhurko used stability techniques to show that, for sufficiently large n, any extremal hypergraph for \ex(n, K_4^{(3)}) is close to Turán's construction, supporting the conjecture asymptotically. For other small 3-uniform complete hypergraphs, such as K_5^{(3)}, the conjectured density is $3/4 from the complete bipartite construction, but it remains open with bounds from flag algebras providing non-trivial upper estimates.

Broader Generalizations

Non-Complete Forbidden Subgraphs

The Erdős–Stone theorem provides the asymptotic solution to Turán's problem for arbitrary forbidden graphs H that are not bipartite, generalizing the exact result for complete graphs. Specifically, for a graph H with chromatic number \chi(H) = r+1 > 2, the extremal number satisfies \ex(n, H) = \left(1 - \frac{1}{r} + o(1)\right) \frac{n^2}{2}, which matches the number of edges in the balanced complete r-partite T(n, r). This result shows that the extremal graphs are asymptotically the same as those avoiding the complete graph K_{r+1}, with the structure determined by the chromatic number rather than the precise edges in H. The theorem implies that any graph with more edges than T(n, r) must contain not only H but a wide range of graphs with chromatic number r+1. When H is bipartite, so \chi(H) = 2, the Erdős–Stone theorem yields only the trivial bound \ex(n, H) = o(n^2), as the Turán graph T(n, 1) has no edges. In this case, the problem reduces to finding the maximum edges in H-free bipartite graphs, often studied via the Zarankiewicz problem, which bounds the edges in bipartite graphs avoiding complete bipartite subgraphs K_{s,t}. The Kővári–Sós–Turán theorem establishes that \ex(n, K_{s,t}) \leq (s-1)^{1/t} n^{2 - 1/t} + (t-1) n, providing an upper bound of order n^{2 - 1/\min(s,t)} assuming s \leq t. This bound is tight for certain parameters, such as when s=2, and highlights how forbidding bipartite H leads to subquadratic growth, contrasting with the constant-density extremal graphs for non-bipartite H. Representative examples illustrate these distinctions. For the 4-cycle C_4, which is isomorphic to K_{2,2}, the Kővári–Sós–Turán theorem implies \ex(n, C_4) = O(n^{3/2}), and random bipartite graphs or incidence graphs of projective geometries achieve matching lower bounds of \Omega(n^{3/2}), yielding asymptotic density n^{1/2}. For longer even cycles C_{2k} with k \geq 3, the Bondy–Simonovits theorem refines the bound to \ex(n, C_{2k}) = O_k(n^{1 + 1/(k-1)}), showing polynomial growth slower than quadratic but faster than linear, with extremal constructions based on bipartite graphs of girth exceeding $2k. Trees provide another bipartite case: the Erdős–Sós conjecture asserts that for any tree T on k vertices, \ex(n, T) \leq (k-2)n/2, implying linear growth and extremal graphs as unions of k-2 stars, though the conjecture remains open in general but proven for many tree families. These results underscore key differences from the clique case in Turán's theorem: while forbidding complete graphs yields exact thresholds with balanced complete multipartite extremal graphs and constant edge density $1 - 1/(r-1), non-complete forbidden subgraphs often produce asymptotic bounds with subquadratic densities that vary polynomially based on the structure of H, such as the minimum degree or bipartition sizes in bipartite H.

Maximizing Non-Edge Parameters

In Turán-type problems, one natural extension beyond edge maximization involves determining the maximum possible minimum degree \delta(G) in an n-vertex K_{r+1}-free graph G. The extremal value is achieved by the Turán graph T(n,r), the complete balanced r-partite graph on n vertices, where \delta(T(n,r)) = n - \lceil n/r \rceil, which is asymptotically bounded by (1 - 1/r)n + o(n). This bound follows directly from the structure of T(n,r), as each vertex connects to all vertices outside its own part, and the parts are as equal as possible to maximize connectivity while avoiding K_{r+1}. No K_{r+1}-free graph can exceed this minimum degree, as any higher connectivity would force a larger clique by Turán's theorem implications on average degree. Another variant focuses on maximizing the number of copies of smaller cliques or subgraphs, such as triangles (K_3) or K_r, in K_{r+1}-free graphs. This is captured by the generalized Turán number \mathrm{ex}(n, K_s, K_{t+1}), which denotes the maximum number of K_s-subgraphs in an n-vertex K_{t+1}-free graph, for s \leq t. For forbidden K_{r+1}, the extremal graph is again T(n,r), which maximizes the count of K_s for s \leq r. For instance, in K_4-free graphs, T(n,3) achieves the maximum number of triangles, with the count asymptotically \Theta(n^3 / 27), reflecting the balanced tripartite structure that promotes dense cross-partition triangles without forming a K_4. The Andrásfai–Erdős–Sós theorem provides a converse perspective on degree conditions for K_{r+1}-freeness, stating that any n-vertex G with \delta(G) > \frac{3r-4}{3r-1} n and no K_{r+1} must be r-partite. This threshold is sharp, as the complete r-partite with parts differing by at most one vertex meets the degree condition without containing K_{r+1}, but slightly smaller degrees allow non-partite examples. The theorem strengthens Turán-type bounds by linking high minimum directly to colorability under clique avoidance. These degree and subgraph variants find applications in random graph theory, where the Andrásfai–Erdős–Sós theorem helps identify large triangle-free s in G(n,p) models by extracting induced subgraphs with controlled degrees. In , such bounds inform constructions of block designs or finite geometries avoiding clique-like configurations, ensuring balanced incomplete block designs maximize resolution classes without forbidden substructures.

Edge-Clique Region and Stability

The edge-clique region refers to the set of all achievable pairs (e(G), c_r(G)), where e(G) is the number of edges in a K_{r+1}-free graph G on n vertices and c_r(G) is the number of copies of K_r in G. Asymptotically, this region lies below the curve defined by the corresponding quantities in the Turán graph T(n,r), which forms the upper boundary. Specifically, for any K_{r+1}-free graph G, c_r(G) \leq c_r(T(n,r)), with equality if and only if G is isomorphic to T(n,r). This maximum is established by showing that among all K_{r+1}-free graphs on n vertices, T(n,r) maximizes the number of K_r s, as part of a broader result on subgraph counts in extremal graphs. The lower boundary of the is zero for edge counts up to t(n, r-1), since K_r-free graphs (which are also K_{r+1}-free) achieve up to that many s with no K_r. Complete r-partite graphs with unequal part sizes still contain K_r, so for edge counts above t(n, r-1), the minimum c_r(G) is positive. The full is thus the area where, for a fixed e(G), c_r(G) ranges from some minimum (often zero below t(n, r-1), positive above) to the maximum attained by a suitable blow-up or modification of T(n,r) with the prescribed edge count. Stability results refine this picture by quantifying how graphs near the boundary behave structurally. The Erdős–Simonovits stability theorem states that if G is a K_{r+1}-free graph on n vertices with |E(G)| > t(n,r) - \epsilon n^2, then G can be transformed into T(n,r) by changing at most \delta(\epsilon) n^2 edges, where \delta(\epsilon) \to 0 as \epsilon \to 0. This was independently proved by Erdős and Simonovits in the 1960s, with Lovász providing an alternative proof using symmetrization methods. Consequently, such graphs not only have edge counts close to the extremal value but also c_r(G) close to c_r(T(n,r)), up to an additive error of o(n^r). These stability theorems have key implications for related areas in extremal . They yield quantitative removal lemmas tailored to : if a has slightly more than t(n,r) edges, removing O(\epsilon n^2) edges eliminates all K_{r+1} while preserving near-extremal K_r counts. Additionally, graphs in this regime exhibit pseudorandom properties with respect to distributions, meaning their subgraph densities those of T(n,r) under small perturbations, facilitating applications in theory and approximation algorithms.

References

  1. [1]
    [PDF] Extremal Graph Theory
    The following theorem tells us that Tr1(n) is indeed extremal for n and Kr, and as such unique; in particular, ex(n, Kr) = tr1. (n). Theorem 7.1.1. (Turán 1941).
  2. [2]
    [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: original | Show results with:original
  3. [3]
    [PDF] Turán's Theorem and Coding Theory - University of Toronto
    May 16, 2012 · Turán's theorem, a fundamental result in extremal graph theory, provides an exact formula for. T(n, k), and a characterization of the extremal ...
  4. [4]
    [PDF] Turan's Theorem - CSA – IISc Bangalore
    Nov 18, 2014 · Theorem 1 Among n-vextex simple graphs with no Kr+1,Tn,r has the maximum number of edges. Here, Kr+1 refers to the (r + 1)-clique and Tn,r ...
  5. [5]
    Turán Graph -- from Wolfram MathWorld
    A Turán graph is an extremal graph with n vertices that contains no (k+1)-clique, and has the maximum possible number of edges for such a graph.
  6. [6]
    [PDF] Exact stability for Turán's Theorem - People
    Turán's classical theorem [25] from 1941 says that a Kr+1-free n-vertex graph maximizing the number of edges (an extremal graph) is r-partite; the r = 2 ...
  7. [7]
    [PDF] Complete k-partite graphs Turán's Theorem Turán-type problems ...
    The Turán graph Tn,r is the complete r-partite graph on n vertices whose partite sets differ in size by at most 1. (All partite sets have size dn/re or bn ...
  8. [8]
    [PDF] Extremal graph theory
    The basic statement of extremal graph theory is Mantel's theorem, proved in 1907, which states that any graph on n vertices with no triangle contains at ...Missing: paper | Show results with:paper
  9. [9]
    [PDF] on the connection between chromatic number, maximal clique and ...
    ANDRÁSFAI, P. ERDOS and V.T. SÓS. Hungarian Academy of Sciences, Budapest, Hungary. Received 9 July 1973. Abstract. Let G n be a graph of n vertices, having ...
  10. [10]
    Turán's Theorem -- from Wolfram MathWorld
    "On an Extremal Problem in Graph Theory." Mat. Fiz. Lapok 48, 436-452, 1941. Turán, P. "On the Theorem of Graphs." Colloq. Math. 3 ...Missing: original paper Paul<|control11|><|separator|>
  11. [11]
    [PDF] 2 - Turán's Theorem - UCSD Math
    Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941),. 436–452 [In Hungarian]; On the theory of graphs, Coll. Math. 3 (1954), pp. 19–30 ...
  12. [12]
    [PDF] Extremal and Probabilistic Graph Theory
    Feb 24, 2020 · Let ∆(G) := max{d(v)|v ∈. V } be the maximum degree of G and δ(G) := min{d(v)|v ∈ V } be the minimum degree. ... By induction, we know G0 = Tr ...
  13. [13]
    [PDF] Lecture 3: Turán's theorem 1 Turán Graphs
    Oct 10, 2016 · In summary, whenever ni −nj > 1, we can do this operation and increase the number of edges. Thus in the graph with maximized number of edges, ...
  14. [14]
    [PDF] Turan's Graph Theorem - Martin Aigner - ResearchGate
    Jun 19, 2005 · Second proof (Erdös 1970). This proof makes use of the structure of the Turán graphs. Let me V with d maxisjsnd. We denote by S the neighbors ...
  15. [15]
    [PDF] Section 12.2. Turán's Theorem
    Jun 5, 2022 · Note. In the proof of Turán's Theorem, we saw that if graph G has n vertices and more than e(Tk,n) edges and if v is a vertex of maximum degree ...
  16. [16]
    A. A. Zykov, “On some properties of linear complexes”, Sb. Math., 66 ...
    Matematicheskii Sbornik. Novaya Seriya, 1949, Volume 24(66), Number 2, Pages ... Full-text PDF (2753 kB) Citations (7). Received: 24.04.1947.
  17. [17]
    [PDF] Graph Theory and Additive Combinatorics - Yufei Zhao
    Jun 18, 2024 · There have been many exciting developments in graph theory and additive combinatorics in recent decades. ... Zykov symmetrization proof of Turán's ...
  18. [18]
    Refinement on Spectral Turán's Theorem - SIAM.org
    In 1941, Turán [49] studied the question of extending Mantel's theorem to K r + 1 -free graphs. Let T r ( n ) denote the complete -partite graph on vertices ...Missing: original | Show results with:original<|control11|><|separator|>
  19. [19]
    [PDF] The Probabilistic Method (Third edition)
    The full result of Turan is given in The Probabilistic Lens: Turán's Theorem. (following Chapter 6). 3.3 COMBINATORIA!. GEOMETRY. For a set S of n points in ...
  20. [20]
    [PDF] Hypergraph Turán Problems - People
    We return now to the original question of Turán, concerning the Turán numbers for the complete hypergraphs Kr t . None of the Turán densities π(Kr t ) with ...
  21. [21]
    HypergraphTuran - UCSD Math
    We let K(r)k denote a complete r-graph on k vertices and we write tr(n,K(r)k)=tr(n,k). Turán's conjecture for r-graphs, $1000 (proposed by Turán, 1941).Missing: ex( K_r^ history
  22. [22]
    [PDF] On 3-Hypergraphs with Forbidden 4-Vertex Configurations
    The Tura'n Density of the Hypergraph {abc, ade, bde, cde} · Z. FürediO. PikhurkoM. Simonovits. Mathematics. Electron. J. Comb. 2003. TLDR. It is shown that the ...
  23. [23]
    [PDF] ON A PROBLEM OF K. ZARANKIEWICZ
    ON A PROBLEM OF K. ZARANKIEWICZ. BY. T. KOVARI, V. T. SÓS AND P. TURÁN (BUDAPEST). 1. K. Zarankiewicz¹) has raised the following interesting question. Let A be ...
  24. [24]
    [PDF] Cycles of Even Length in Graphs (1)
    In this paper we solve a conjecture of P. Erdos by showing that if a graph. G'” has n vertices and at least IOOkn 1+1/k edges, then G contains a cycle CzL ...
  25. [25]
    A conjecture on trees (proposed by Erdös and Sós, 1962)
    A conjecture on trees (proposed by Erdös and Sós, 1962). Every graph on n vertices having at least n(k−1)/2+1 edges must contain as a subgraph every tree of ...
  26. [26]
    On the maximal number of certain subgraphs inK r -free graphs
    Dec 22, 1989 · Cite this article. Györi, E., Pach, J. & Simonovits, M. On the maximal number of certain subgraphs inK r -free graphs. Graphs and Combinatorics ...
  27. [27]
    [PDF] Exact Stability for Turán's Theorem - arXiv
    Dec 29, 2021 · Let G be a graph on n vertices with maximum degree ∆ and let k ≥ 1 be an integer. ... Turán's theorem, Math. Centr. report. ZW152, Amsterdam ...
  28. [28]
    [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 ...