WorksMathematics
The graph -Turán theorem
Abstract
We prove analogues of Turán's theorem and the Erdős–Stone theorem for graph -numbers. The th -number equals the th rational Betti number of the real toric manifold associated with the graph associahedron of . We show that the Turán graph maximizes every -number among -free graphs on vertices. We also show that for any fixed graph with at least one edge and each fixed , the limiting extremal density of the th -number among -free graphs depends only on the chromatic number of . Since is the number of edges of , these results recover the two classical theorems in degree one and extend them to higher -numbers.
Introduction
All graphs in this paper are finite and simple. For a graph , we write for its vertex set, for its number of edges, and for the subgraph induced by . The graph with no vertices is denoted by . We write for the complete graph on vertices and for its complement, the graph on vertices with no edges. A graph is -free if it has no clique of size .
Let . The Turán graph is the complete -partite graph on vertices whose part sizes differ by at most one. Empty parts are allowed, and when . The case is Mantel’s theorem [9]. Turán proved the general result [16]. Every -free graph on vertices satisfies
with equality if and only if . Zykov later strengthened this result by showing that maximizes the number of cliques of each fixed order among -free graphs on vertices [18]. The Erdős–Stone theorem [8] showed that Turán graphs also govern the asymptotic edge-extremal problem for arbitrary forbidden graphs, with the chromatic number determining the leading term. For a historical account of the theory developed from Turán’s theorem, see [13].
We study analogous extremal problems for graph -numbers. The signed -number was introduced in [3] and is defined recursively as follows.
.
If has a connected component of odd order, then .
If is nonempty and every connected component of has even order, then
The -number of is , and for the th -number of is
In particular,
Let be the real toric manifold associated with the graph associahedron of . See [12, 7, 10, 11, 4, 6, 17, 5] for topological and combinatorial studies of these manifolds and related structures. Let denote its th rational Betti number. It was proved in [3] that
for every graph .
Our first result is a Turán theorem for graph -numbers.
Theorem 1.1. Let , and let be a -free graph on vertices. Then
for every .
If , then equality holds if and only if .
For , Theorem 1.1 is Turán’s theorem. When , we have , and the inequality also follows from [5], where it was proved that for every whenever is a subgraph of .
In fact, for , we prove the stronger inequality
as stated in Remark 4.4.
By (1.1), Theorem 1.1 gives
for every -free graph on vertices and every . Thus, among the real toric manifolds associated with these graphs, maximizes all rational Betti numbers simultaneously. Equality in any one degree already forces .
Our second result is an Erdős–Stone theorem for graph -numbers. Let be a fixed graph with at least one edge. A graph is -free if it has no subgraph, not necessarily induced, isomorphic to . For , put
Theorem 1.2. Let be a fixed graph with at least one edge, let , and fix . Then, as ,
For , Theorem 1.2 recovers the classical Erdős–Stone asymptotic formula [8]. We also give explicit formulas for the -numbers of Turán graphs in Lemma 5.3.
The paper is organized as follows. Section 2 introduces a homological upper bound for graph -numbers and establishes its basic properties. Section 3 develops the Zykov symmetrization needed for the extremal problem. Section 4 compares complete multipartite graphs and proves Theorem 1.1. Section 5 derives explicit formulas for the -numbers of complete multipartite and Turán graphs, and proves Theorem 1.2 together with the density formula.
A homological upper bound for graph a-numbers
Let be a finite poset, and let be its order complex. If has a least element and a greatest element , write for its proper part and for its Möbius function. All reduced homology groups have coefficients in , with .
A graded poset is called locally semimodular if, in every interval of , any two distinct elements covering a common element have a common cover. If is a bounded locally semimodular graded poset of rank , then is pure of dimension and has reduced homology only in that degree [2]. Moreover, it is known [15] that
Throughout this paper, all graphs are finite and simple. For a graph , let denote its vertex set and its number of edges. For , let denote the subgraph induced by . The graph with no vertices is denoted by . Let be the poset of subsets such that every component of has even order, ordered by inclusion.
Let be a graph with vertices such that every component of has even order. Then is graded of rank , with least element and greatest element . In addition,
Equation (4) was proved for connected graphs [3], but it remains valid without the connectedness assumption.
We now replace the even-component condition by the weaker requirement that an even set contain an edge. Assume that is a graph with vertices and at least one edge. We define
ordered by inclusion. Note that the vertices of the order complex are the nonempty proper subsets of even size such that has an edge, and the faces are the chains of such sets.
Proposition 2.1. A poset is graded of rank and locally semimodular. Consequently, has reduced homology only in degree .
Proof. The least element of is , and since has an edge, is the greatest element. Let be nonempty. If and is even, then , because contains an edge of . So the elements covering are the sets with . The elements covering are the edges of , and every nonempty element of contains one of them. Hence is graded, with rank function .
Now let both cover , and let with . Then , so is or . If , let . If , then is odd while is even, so there is ; let . In both cases , , and contains an edge, because does. So , and covers and . The homology statement follows from (3).
Definition 2.2. For a graph on vertices, let
For a graph and , let
Clearly, for each . In particular, and for . Since and pairs of nonadjacent vertices contribute zero, we also have .
We write for the path graph on vertices.
Example 2.3. Let be a graph on four vertices with at least one edge. The poset is a rank-zero poset whose elements are precisely the edges of . Hence, its order complex consists of points, and therefore
For instance, , while .
A graph is complete multipartite if its vertex set can be partitioned into parts such that two vertices are adjacent exactly when they lie in different parts.
Proposition 2.4. For every , we have
with equality for all whenever is complete multipartite.
Proof. Induced subgraphs of complete multipartite graphs are complete multipartite. Then, it is enough to show that for every graph with an even number of vertices, with equality when is complete multipartite.
For convenience, write
If , then . If has a component of odd order, then . Suppose now that and every component of has even order. Then has an edge. Moreover, every nonempty contains an edge, because each component of is connected and has at least two vertices. It follows that , and hence is a subcomplex of . Put . Neither complex has a face of dimension , so for each of them, is the space of -cycles. A -cycle of is also a -cycle of . Hence, by (4),
Now let be complete multipartite with even. If is nonempty and has no edges, then all components of are single vertices, so . Suppose that has an edge. If meets at least two parts, then is connected: two vertices of in different parts are adjacent, and two vertices of in the same part have a common neighbor in . In particular, is connected. For a nonempty set of even size, this gives
Thus, and . Therefore, (4) gives .
The invariant admits a formula in terms of independent sets. Let be the number of independent sets of size in with . Let denote the Euler secant numbers [14 A000364].
Theorem 2.5. Let be a graph on vertices and let . Then
Proof. First let have vertices. For each even set , put
If has an edge, Proposition 2.1 and (3) identify with the Möbius number of . Its defining recurrence, together with the definition for edgeless graphs, gives
In the poset of all even subsets of , the Möbius function is
This follows by induction from the coefficient identity . Möbius inversion therefore gives
This also holds when is empty. Now sum (5) over all -subsets of . Each independent set of size is contained in exactly such subsets, which proves the formula.
Zykov symmetrization
Zykov’s symmetrization method [18] is a classical tool in extremal graph theory for reducing problems to complete multipartite graphs. In this section, we show that satisfies a natural inequality under Zykov symmetrization.
For a vertex of a graph , let denote its neighborhood. For distinct nonadjacent vertices , let denote the graph obtained from by adding the edge . For a finite set , let denote the complete graph on . For graphs and on disjoint vertex sets, their join is obtained from by adding all edges between and .
To begin with, we describe how changes when an edge is added. Let and be distinct nonadjacent vertices of , and set
Let be the graph on obtained from by joining every vertex of to every other vertex of . Equivalently,
For instance, Figure 1 illustrates the construction.
Figure 1.
Proposition 3.1. Let be a graph with vertices.
(1) For any distinct nonadjacent vertices and of ,
(2) If has a universal vertex, then .
Proof. We first prove (1), and then use it to prove (2). (1) Let and be defined as above, and let . Adding removes exactly the independent sets of the form , where is independent in . Thus Theorem 2.5, applied to and with , gives
Every vertex of is adjacent to all other vertices of . Hence the independent sets of even size in are exactly those in , including the empty set. Applying Theorem 2.5 to with shows that the sum is .
(2) Let be a universal vertex of . We use induction on . If , then and .
Suppose . Choose a vertex , and let be obtained from by deleting the edge . The vertex is adjacent to every vertex of . Hence and have no common non-neighbor in , which implies that . Combining (1) with the induction hypothesis applied to , we obtain
as desired. □
If contains and , then the common non-neighbors of and in are the vertices of . Hence
Lemma 3.2. Let be nonadjacent vertices of a graph . Then
Proof. Let with . If does not contain both and , then . If , then , and Proposition 3.1(1) and (3.1) give
As runs over the -subsets of that contain and , the set runs over the -subsets of . Summing proves the identity. The last statement follows because and .
Consequently, is monotone with respect to edge inclusion.
Definition 3.3. Let be nonadjacent vertices of . The graph is obtained from by deleting all edges at and then joining to every vertex of .
The vertices and are nonadjacent in and both have neighborhood . All edges not incident to are unchanged. Moreover,
Proposition 3.4. If is -free, then so is .
Proof. Let be a clique of . If , then is a clique of . If , then and . Therefore, is a clique of of the same size.
Lemma 3.5. If and are nonadjacent vertices of , then
Proof. If , then the desired identity is immediate, since all three terms are zero. Thus, we may assume that . By Theorem 2.5, it is enough to show that
for every .
Since is an edge, no independent set in these graphs contains both and . Independent sets containing neither vertex are the same in all three graphs. For the sets containing exactly one of them, put . Let and be the numbers of independent -sets in and , respectively. The contributions of these independent sets to
are , , and , respectively. This proves the identity for , while is immediate.
Zykov symmetrization is particularly useful when one of the two symmetrizations can be chosen without decreasing the graph parameter. We have the following stronger inequality for .
Theorem 3.6. Let , be nonadjacent vertices of . For every ,
Proof. For , both sides equal 2. Suppose , and write and . By Lemma 3.2, for ,
Hence, using Lemma 3.5,
To finish the proof, it is sufficient to show that
Let . Since only edges incident to or are changed,
Therefore,
Since is monotone with respect to edge inclusion,
Thus (7) holds, completing the proof.
We write for the cycle graph on vertices.
Remark 3.7. For the graph -numbers, the inequality in Theorem 3.6 does not hold in general. For example, let be the path on four vertices labeled in this order. Then
Since
we have
Proof of Theorem 1.1
To prove Theorem 1.1, we compare complete multipartite graphs by moving one vertex from a larger part to a smaller one. For integers , let
where is the discrete graph on vertices and is the complete graph on vertices. This is the complete multipartite graph on vertices with one part of size and parts of size one. For disjoint sets , we write for the complete multipartite graph with parts , allowing empty parts.
Lemma 4.1. For the complete multipartite graph with , the following hold.
(1) .
(2) For each ,
(3) Assume that . For ,
where for a fixed .
Proof. The edges between and the other parts do not change. The number of edges within changes from to . Hence
which proves (1).
Let be the complete multipartite graph with parts . Then is obtained from by deleting all edges between and , and is obtained from by deleting all edges between and .
Let be a part of other than . For , let be obtained from by deleting the edges . Then . The common non-neighbors of and in are , which are pairwise nonadjacent. Hence
Applying Lemma 3.2 at each step and summing gives
Applying this identity to and , and subtracting the resulting identities, gives
which proves (2).
Suppose that . Since all terms in the sum in (2) are nonnegative, it suffices to show that . If , then . Assume that , and then . Since and , we have
Thus has a singleton part , and is adjacent to every other vertex. Since , there is a set of $2i-2$ vertices of containing $s. By the definition of and Proposition 3.1(2),
which proves (3).
For and , define
Lemma 4.2. Let , , and , and fix a set of vertices. Among all -free graphs on , the function attains its maximum at a complete multipartite graph with at most nonempty parts.
Proof. For a graph on and a vertex , let , and put
There are finitely many graphs on . Among the -free graphs on that maximize , choose one, say , for which
is largest. Let be distinct nonadjacent vertices of . Since
Theorem 3.6 gives
By Proposition 3.4, the graphs and are -free. The maximality of therefore gives
Together with (8), this shows that both and maximize .
We compute . In , both and have degree , while in , both have degree . Thus and contribute
Let and . If , then has degree in one of and degree in the other. Thus, it contributes
Otherwise, has the same degree in , , and . Hence
Since and also maximize , the choice of gives
Therefore .
Thus any two distinct nonadjacent vertices of have the same neighborhood. It follows that nonadjacency is transitive. Indeed, if and are nonadjacent, and are nonadjacent, and , then
Thus and are nonadjacent. Hence the relation in which two vertices are equal or nonadjacent is an equivalence relation. Its equivalence classes are independent sets, and any two vertices in different classes are adjacent. Thus is complete multipartite. Choosing one vertex from each part gives a clique. Since is -free, it follows that has at most nonempty parts.
We now prove the quantitative bound and complete the proof of Theorem 1.1.
Lemma 4.3. Let and , and let be a -free graph on vertices. Then
Proof. Since , we have . Let . By Lemma 4.2, there is a complete multipartite graph on with at most nonempty parts such that
Write , allowing empty parts.
Suppose that two parts, say and , satisfy . Move one vertex from to . By Lemma 4.1(1) and (3), this move increases by at least 1 and increases the number of edges by
Hence does not decrease. Moreover, the move decreases
by . Since this sum is a nonnegative integer, the process terminates after finitely many moves.
At termination, all part sizes differ by at most one, and the resulting graph is a copy of . Therefore
Equivalently,
We now prove Theorem 1.1.
Proof of Theorem 1.1. If , both sides equal 1. If , both sides equal 0. Let . By Turán’s theorem, . Since is complete multipartite, Proposition 2.4 and Lemma 4.3 give
If , then all these inequalities are equalities. In particular, , so by the equality case of Turán’s theorem. The converse is clear.
Remark 4.4. Let and , and let be a -free graph on vertices. Proposition 2.4 and Lemma 4.3 give
Indeed, and .
Proof of Theorem 1.2
When only the part sizes matter, we write for the complete multipartite graph with part sizes .
Example 5.1. The graph is . Its first three -numbers are
To compute , note that a four vertex subset meets the two parts in sizes , or . Since and , we obtain
The defining recurrence then gives
Thus every triangle-free graph on six vertices satisfies
and equality in any one of these inequalities holds if and only if . Equivalently, the rational Poincaré polynomial of is
| 5 | 9 | 5 | |
| 6 | 15 | 10 | |
| 5 | 20 | 16 | |
| 9 | 39 | 31 |
Table 1. Graph -numbers
and it bounds the rational Poincaré polynomials of coefficientwise for these graphs.
Table 5 compares with three other triangle-free graphs on six vertices. The values can be computed directly from the defining rules. The formulas for paths, cycles and stars in [3] give the same values. Although has fewer edges than , its second and third -numbers are larger. Thus the number of edges alone does not determine the ordering of the higher -numbers.
We now compute the -numbers of complete multipartite graphs. For , put and
We use the convention for integers .
Lemma 5.2. If , then
In particular, .
Proof. Every nonempty independent set in a complete multipartite graph lies in a unique part. Hence for . Apply Theorem 2.5 and the equality from Proposition 2.4.
The complete multipartite case of this formula can also be obtained from the generating function stated in [12]
Thus Lemma 5.2 is also a finite coefficient form of that known generating function.
For the first three degrees,
The identity for is valid for .
| 4 | 2 | 4 | 3 | 0 | 0 | 0 |
| 4 | 3 | 5 | 4 | 0 | 0 | 0 |
| 4 | 4 | 6 | 5 | 0 | 0 | 0 |
| 5 | 2 | 6 | 13 | 0 | 0 | 0 |
| 5 | 3 | 8 | 19 | 0 | 0 | 0 |
| 5 | 4 | 9 | 22 | 0 | 0 | 0 |
| 5 | 5 | 10 | 25 | 0 | 0 | 0 |
| 6 | 2 | 9 | 39 | 31 | 0 | 0 |
| 6 | 3 | 12 | 57 | 46 | 0 | 0 |
| 6 | 4 | 13 | 63 | 51 | 0 | 0 |
| 6 | 6 | 15 | 75 | 61 | 0 | 0 |
| 8 | 2 | 16 | 172 | 820 | 663 | 0 |
| 8 | 3 | 21 | 245 | 1183 | 958 | 0 |
| 8 | 4 | 24 | 290 | 1408 | 1141 | 0 |
| 8 | 8 | 28 | 350 | 1708 | 1385 | 0 |
| 10 | 2 | 25 | 500 | 5960 | 28915 | 23431 |
| 10 | 3 | 33 | 715 | 8625 | 41904 | 33962 |
| 10 | 4 | 37 | 826 | 10010 | 48661 | 39441 |
| 10 | 10 | 45 | 1050 | 12810 | 62325 | 50521 |
Table 2. Values of .
Lemma 5.3. Write , where , and put
For , we have
Proof. The graph has parts of size and parts of size . Applying Lemma 5.2 gives the formula.
Table 5 lists values of (5.2).
Throughout this section, the degree is fixed as the number of vertices tends to infinity. For a graph on vertices, define
By Theorem 1.1, . For , this is the usual edge density.
Let be a fixed graph with at least one edge. If and is a uniformly chosen -subset of , then
Indeed, each -subset of is contained in the same number of -subsets. Since every induced subgraph of an -free graph is -free, the sequence
is nonincreasing and bounded below by zero. We therefore define the th -Turán density of by
For , put
The following proposition shows that is the limiting density of the Turán graphs.
Lemma 5.4. For fixed ,
In particular,
Proof. Each part of has size . Hence, for fixed ,
It follows that
By (5.2),
Multiplying by proves the lemma. □
We use a standard consequence of the clique blow-up argument. If is fixed and , then every -free graph on vertices has copies of , uniformly over all such graphs. Indeed, is a subgraph of a fixed blow-up of , so this is a special case of [1 Proposition 2.1]. Isolated vertices of do not affect this statement, since they can be added to any copy of the remaining graph once .
Proof of Theorem 1.2. Put . The graph is -partite and hence -free, which gives the lower bound.
For the upper bound, fix an integer . Let be any -free graph on vertices, and choose an -subset uniformly at random. By the preceding clique bound, has copies of . Each fixed copy is contained in with probability
Thus the probability that contains a is , uniformly over all -free graphs . On the complementary event, Theorem 1.1 gives
On the exceptional event, we use . By (11),
First let , keeping fixed. Then let and apply Lemma 5.4. This gives . The lower bound gives the reverse inequality, and Lemma 5.4 yields the theorem.
For every bipartite with an edge, and hence for each fixed . By (2), the theorem also determines the leading asymptotic maximum of over all -free graphs on vertices.
The first three densities are
Setting , we can also write (13) as
For example, , and . tbl:5 gives further values, rounded to six decimal places.
| 2 | 0.500000 | 0.425000 | 0.415471 | 0.414356 |
| 3 | 0.666667 | 0.607407 | 0.599204 | 0.598206 |
| 4 | 0.750000 | 0.703125 | 0.696449 | 0.695626 |
| 5 | 0.800000 | 0.761600 | 0.756060 | 0.755373 |
| 10 | 0.900000 | 0.880200 | 0.877295 | 0.876931 |
Table 3. Normalized -Turán densities .
Remark 5.5. For fixed , the simple poles at and in the preceding generating function give as , which explains the rapid stabilization in Table 5.
References
Department of mathematics, Ajou University, 206, World cup-ro, Yeongtong-gu, Suwon 16499, Republic of Korea
Email address: [email protected]
Research Institute of Basic Sciences, Ajou University, 206, World cup-ro, Yeongtong-gu, Suwon 16499, Republic of Korea
Email address: [email protected]
References
- [1]N. Alon and C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016), 146–172.
- [2]Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159–183. MR 570784DOI
- [3]Suyoung Choi and Hanchul Park, A new graph invariant arises in toric topology, J. Math. Soc. Japan 67 (2015), no. 2, 699–720. MR 3340192arxiv.org/abs/1210.3776
- [4]Suyoung Choi and Younghan Yoon, The cohomology rings of real permutohedral varieties, 2023.arxiv.org/abs/2308.12693
- [5]——, A decomposition of graph a-numbers, Preprint, arXiv:2508.06855, 2025.arxiv.org/abs/2508.06855
- [6]——, Real toric manifolds associated with chordal nestohedra, Journal of Combinatorial Theory, Series A 217 (2026), 106102.DOI
- [7]Vladimir Dotsenko, Sergey Shadrin, and Bruno Vallette, Toric varieties of Loday’s associahedra and noncommutative cohomological field theories, J. Topol. 12 (2019), no. 2, 463–535. MR 4072173DOI
- [8]P. Erdős and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091.
- [9]W. M. Marle, Problem 28, Wiskundige Opgaven 10 (1907), 60–61.
- [10]Boram Park, Hanchul Park, and Seonjeong Park, Graph invariants and Betti numbers of real toric manifolds, Osaka J. Math. 57 (2020), no. 2, 333–356. MR 4081735
- [11]Boram Park and Seonjeong Park, Cohomology of a real toric variety and shellability of posets arising from a graph, Proceedings of the Edinburgh Mathematical Society 66 (2023), no. 4, 1044–1084.DOI
- [12]Seunghyun Seo and Heesung Shin, Signed a-polynomials of graphs and Poincaré polynomials of real toric manifolds, Bull. Korean Math. Soc. 52 (2015), no. 2, 467–481. MR 3338206DOI
- [13]M. Simonovits, On Paul Turán’s influence on graph theory, J. Graph Theory 1 (1977), no. 2, 102–116.DOI
- [14]Neil JA Sloane, The on-line encyclopedia of integer sequences, http://oeis.org.
- [15]Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997, With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986 original. MR 1442260 (98a:05001)
- [16]P. Turán, Eine extremalaufgabe aus der graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452.
- [17]Younghan Yoon, Cohomology of type B real permutohedral varieties, Bulletin of the London Mathematical Society 57 (2025), no. 9, 2770–2788.DOI
- [18]A. A. Zykov, On some properties of linear complexes, Mat. Sb. (N.S.) 24(66) (1949), no. 2, 163–188.
