betaFeedback

WorksMathematics

The graph aa-Turán theorem

Abstract

We prove analogues of Turán's theorem and the Erdős–Stone theorem for graph aa-numbers. The iith aa-number ai(G)a_i(G) equals the iith rational Betti number of the real toric manifold associated with the graph associahedron of GG. We show that the Turán graph Tr(n)T_r(n) maximizes every aa-number among Kr+1K_{r+1}-free graphs on nn vertices. We also show that for any fixed graph HH with at least one edge and each fixed i≥1i\geq1, the limiting extremal density of the iith aa-number among HH-free graphs depends only on the chromatic number of HH. Since a1(G)a_1(G) is the number of edges of GG, these results recover the two classical theorems in degree one and extend them to higher aa-numbers.

Introduction

All graphs in this paper are finite and simple. For a graph GG, we write V(G)V(G) for its vertex set, e(G)e(G) for its number of edges, and G[S]G[S] for the subgraph induced by S⊆V(G)S \subseteq V(G). The graph with no vertices is denoted by ∅\emptyset. We write KnK_n for the complete graph on nn vertices and Kn‾\overline{K_n} for its complement, the graph on nn vertices with no edges. A graph is Kr+1K_{r+1}-free if it has no clique of size r+1r+1.

Let n,r≥1n, r \ge1. The Turán graph Tr(n)T_r(n) is the complete rr-partite graph on nn vertices whose rr part sizes differ by at most one. Empty parts are allowed, and Tr(n)=KnT_r(n) = K_n when r≥nr \ge n. The case r=2r = 2 is Mantel’s theorem [9]. Turán proved the general result [16]. Every Kr+1K_{r+1}-free graph GG on nn vertices satisfies

e(G)≤e(Tr(n)),(1)e(G) \le e(T_r(n)), \tag*{(1)}

with equality if and only if G≅Tr(n)G \cong T_r(n). Zykov later strengthened this result by showing that Tr(n)T_r(n) maximizes the number of cliques of each fixed order among Kr+1K_{r+1}-free graphs on nn 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 aa-numbers. The signed aa-number sa⁡(G)\operatorname{sa}(G) was introduced in [3] and is defined recursively as follows.

  1. sa⁡(∅)=1\operatorname{sa}(\emptyset)=1.

  2. If GG has a connected component of odd order, then sa⁡(G)=0\operatorname{sa}(G)=0.

  3. If GG is nonempty and every connected component of GG has even order, then

sa⁡(G)=−∑S⊆V(G)sa⁡(G[S]).\operatorname{sa}(G)=-\sum_{S\subseteq V(G)}\operatorname{sa}(G[S]).

The aa-number of GG is a(G)=∣sa⁡(G)∣a(G)=|\operatorname{sa}(G)|, and for i≥0i\geq0 the iith aa-number of GG is

ai(G)=∑S⊆V(G)∣S∣=2ia(G[S]).a_i(G)=\sum_{\substack{S\subseteq V(G)\\|S|=2i}}a(G[S]).

In particular,

a0(G)=1,a1(G)=e(G),andai(G)=0 if 2i>∣V(G)∣.a_0(G)=1,\qquad a_1(G)=e(G),\qquad\text{and}\qquad a_i(G)=0\text{ if }2i>|V(G)|.

Let M(G)M(G) be the real toric manifold associated with the graph associahedron of GG. See [12, 7, 10, 11, 4, 6, 17, 5] for topological and combinatorial studies of these manifolds and related structures. Let βi(M(G))\beta_i(M(G)) denote its iith rational Betti number. It was proved in [3] that

βi(M(G))=ai(G)(2)\beta_i(M(G))=a_i(G) \tag*{(2)}

for every graph GG.

Our first result is a Turán theorem for graph aa-numbers.

Theorem 1.1. Let n,r≥1n,r\geq1, and let GG be a Kr+1K_{r+1}-free graph on nn vertices. Then

ai(G)≤ai(Tr(n))a_i(G)\leq a_i(T_r(n))

for every i≥0i\geq0.

If 1≤i≤n/21\leq i\leq n/2, then equality holds if and only if G≅Tr(n)G\cong T_r(n).

For i=1i=1, Theorem 1.1 is Turán’s theorem. When r≥nr\geq n, we have Tr(n)=KnT_r(n)=K_n, and the inequality also follows from [5], where it was proved that ai(G)≥ai(H)a_i(G)\geq a_i(H) for every ii whenever HH is a subgraph of GG.

In fact, for 1≤i≤n/21\leq i\leq n/2, we prove the stronger inequality

ai(Tr(n))−ai(G)≥e(Tr(n))−e(G)n−1,a_i(T_r(n))-a_i(G)\geq\frac{e(T_r(n))-e(G)}{n-1},

as stated in Remark 4.4.

By (1.1), Theorem 1.1 gives

βi(M(G))≤βi(M(Tr(n)))\beta_i(M(G))\leq\beta_i(M(T_r(n)))

for every Kr+1K_{r+1}-free graph GG on nn vertices and every i≥0i\geq0. Thus, among the real toric manifolds associated with these graphs, M(Tr(n))M(T_r(n)) maximizes all rational Betti numbers simultaneously. Equality in any one degree 1≤i≤n/21\leq i\leq n/2 already forces G≅Tr(n)G\cong T_r(n).

Our second result is an Erdős–Stone theorem for graph aa-numbers. Let HH be a fixed graph with at least one edge. A graph is HH-free if it has no subgraph, not necessarily induced, isomorphic to HH. For i≥1i \ge1, put

ex⁡i(n,F):=max⁡{ai(G)∣∣V(G)∣=n, G is H-free}.\operatorname{ex}_i(n,\mathcal{F}) := \max\{a_i(G) \mid|V(G)| = n,\ G\text{ is }H\text{-free}\}.

Theorem 1.2. Let HH be a fixed graph with at least one edge, let r=χ(H)−1r=\chi(H)-1, and fix i≥1i \ge1. Then, as n→∞n \to\infty,

ex⁡i(n,F)=ai(Tr(n))+o(n2i).\operatorname{ex}_i(n,\mathcal{F})=a_i(T_r(n))+o(n^{2i}).

For i=1i=1, Theorem 1.2 recovers the classical Erdős–Stone asymptotic formula [8]. We also give explicit formulas for the aa-numbers of Turán graphs in Lemma 5.3.

The paper is organized as follows. Section 2 introduces a homological upper bound for graph aa-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 aa-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 P\mathcal{P} be a finite poset, and let Δ(P)\Delta(\mathcal{P}) be its order complex. If P\mathcal{P} has a least element 0^\hat{0} and a greatest element 1^\hat{1}, write P‾=P∖{0^,1^}\overline{\mathcal{P}}=\mathcal{P}\setminus\{\hat{0},\hat{1}\} for its proper part and μP\mu_{\mathcal{P}} for its Möbius function. All reduced homology groups have coefficients in Q\mathbb{Q}, with H~−1({∅})=Q\widetilde{H}_{-1}(\{\emptyset\})=\mathbb{Q}.

A graded poset P\mathcal{P} is called locally semimodular if, in every interval of P\mathcal{P}, any two distinct elements covering a common element have a common cover. If P\mathcal{P} is a bounded locally semimodular graded poset of rank m≥1m\ge1, then Δ(P‾)\Delta(\overline{\mathcal{P}}) is pure of dimension m−2m-2 and has reduced homology only in that degree [2]. Moreover, it is known [15] that

μP(0^,1^)=(−1)mdim⁡H~m−2(Δ(P‾)).(3)\mu_{\mathcal{P}}(\hat{0},\hat{1})=(-1)^m\dim\widetilde{H}_{m-2}(\Delta(\overline{\mathcal{P}})). \tag*{(3)}

Throughout this paper, all graphs are finite and simple. For a graph GG, let V(G)V(G) denote its vertex set and e(G)e(G) its number of edges. For S⊆V(G)S\subseteq V(G), let G[S]G[S] denote the subgraph induced by SS. The graph with no vertices is denoted by ∅\emptyset. Let E(G)\mathcal{E}(G) be the poset of subsets S⊆V(G)S\subseteq V(G) such that every component of G[S]G[S] has even order, ordered by inclusion.

Let HH be a graph with 2m≥22m\ge2 vertices such that every component of HH has even order. Then E(H)\mathcal{E}(H) is graded of rank mm, with least element ∅\emptyset and greatest element V(H)V(H). In addition,

dim⁡H~k(Δ(E(H)‾))={a(H),k=m−2,0,k≠m−2.(4)\dim\widetilde{H}_k\bigl(\Delta(\overline{\mathcal{E}(H)})\bigr)= \begin{cases} a(H), & k=m-2,\\ 0, & k\ne m-2. \end{cases} \tag*{(4)}

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 HH is a graph with 2m≥22m\ge2 vertices and at least one edge. We define

E#(H)={∅}∪{S⊆V(H)∣∣S∣ is even and H[S] has an edge},\mathcal{E}^{\#}(H)=\{\emptyset\}\cup\{S\subseteq V(H)\mid|S|\text{ is even and }H[S]\text{ has an edge}\},

ordered by inclusion. Note that the vertices of the order complex Δ(E♯(H)‾)\Delta(\overline{\mathcal{E}^{\sharp}(H)}) are the nonempty proper subsets S⊂V(H)S \subset V(H) of even size such that H[S]H[S] has an edge, and the faces are the chains of such sets.

Proposition 2.1. A poset E♯(H)\mathcal{E}^{\sharp}(H) is graded of rank mm and locally semimodular. Consequently, Δ(E♯(H)‾)\Delta(\overline{\mathcal{E}^{\sharp}(H)}) has reduced homology only in degree m−2m-2.

Proof. The least element of E♯(H)\mathcal{E}^{\sharp}(H) is ∅\varnothing, and since HH has an edge, V(H)V(H) is the greatest element. Let S∈E♯(H)S \in\mathcal{E}^{\sharp}(H) be nonempty. If S⊆T⊆V(H)S \subseteq T \subseteq V(H) and ∣T∣|T| is even, then T∈E♯(H)T \in\mathcal{E}^{\sharp}(H), because TT contains an edge of H[S]H[S]. So the elements covering SS are the sets S∪{x,y}S \cup\{x,y\} with x,y∉Sx,y \notin S. The elements covering ∅\varnothing are the edges of HH, and every nonempty element of E♯(H)\mathcal{E}^{\sharp}(H) contains one of them. Hence E♯(H)\mathcal{E}^{\sharp}(H) is graded, with rank function S↦∣S∣/2S \mapsto|S|/2.

Now let U≠U′U \ne U' both cover TT, and let U,U′⊆BU,U' \subseteq B with B∈E♯(H)B \in\mathcal{E}^{\sharp}(H). Then ∣U∣=∣U′∣=∣T∣+2|U|=|U'|=|T|+2, so ∣U∪U′∣|U \cup U'| is ∣T∣+3|T|+3 or ∣T∣+4|T|+4. If ∣U∪U′∣=∣T∣+4|U \cup U'|=|T|+4, let Z=U∪U′Z=U \cup U'. If ∣U∪U′∣=∣T∣+3|U \cup U'|=|T|+3, then ∣U∪U′∣|U \cup U'| is odd while ∣B∣|B| is even, so there is q∈B∖(U∪U′)q \in B \setminus(U \cup U'); let Z=U∪U′∪{q}Z=U \cup U' \cup\{q\}. In both cases Z⊆BZ \subseteq B, ∣Z∣=∣U∣+2|Z|=|U|+2, and ZZ contains an edge, because UU does. So Z∈E♯(H)Z \in\mathcal{E}^{\sharp}(H), and ZZ covers UU and U′U'. The homology statement follows from (3).

Definition 2.2. For a graph HH on 2m2m vertices, let

a^(H)={1if H=∅,0if H≠∅ has no edges,dim⁡H~m−2(Δ(E♯(H)‾))if m≥1 and H has an edge.\widehat{a}(H)= \begin{cases} 1 & \text{if } H=\varnothing,\\ 0 & \text{if } H\ne\varnothing\text{ has no edges},\\ \dim\widetilde{H}_{m-2}\bigl(\Delta(\overline{\mathcal{E}^{\sharp}(H)})\bigr) & \text{if } m\ge1\text{ and }H\text{ has an edge.} \end{cases}

For a graph GG and i≥0i\ge0, let

a^i(G)=∑S⊆V(G)∣S∣=2ia^(G[S]).\widehat{a}_i(G)=\sum_{\substack{S\subseteq V(G)\\ |S|=2i}}\widehat{a}(G[S]).

Clearly, a^i(G)≥0\widehat{a}_i(G)\ge0 for each i≥0i\ge0. In particular, a^0(G)=1\widehat{a}_0(G)=1 and a^i(G)=0\widehat{a}_i(G)=0 for 2i>∣V(G)∣2i>|V(G)|. Since a^(K2)=1\widehat{a}(K_2)=1 and pairs of nonadjacent vertices contribute zero, we also have a^1(G)=e(G)\widehat{a}_1(G)=e(G).

We write PnP_n for the path graph on nn vertices.

Example 2.3. Let HH be a graph on four vertices with at least one edge. The poset E♯(H)\mathcal{E}^{\sharp}(H) is a rank-zero poset whose elements are precisely the edges of HH. Hence, its order complex consists of e(H)e(H) points, and therefore

a^(H)=e(H)−1.\widehat{a}(H)=e(H)-1.

For instance, a^(P3⊔K1)=1\widehat{a}(P_3\sqcup K_1)=1, while a(P3⊔K1)=0a(P_3\sqcup K_1)=0.

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 i≥0i\ge0, we have

ai(G)≤a^i(G),a_i(G)\le\widehat{a}_i(G),

with equality for all ii whenever GG is complete multipartite.

Proof. Induced subgraphs of complete multipartite graphs are complete multipartite. Then, it is enough to show that a(H)≤a^(H)a(H)\le\widehat{a}(H) for every graph HH with an even number of vertices, with equality when HH is complete multipartite.

For convenience, write

L(H)=Δ(E(H)‾)andL#(H)=Δ(E#(H)‾).L(H)=\Delta\bigl(\overline{\mathcal{E}(H)}\bigr)\qquad\text{and}\qquad L^{\#}(H)=\Delta\bigl(\overline{\mathcal{E}^{\#}(H)}\bigr).

If H=∅H=\varnothing, then a(H)=a^(H)=1a(H)=\widehat{a}(H)=1. If HH has a component of odd order, then a(H)=0≤a^(H)a(H)=0\leq\widehat{a}(H). Suppose now that ∣V(H)∣=2m≥2|V(H)|=2m\geq2 and every component of HH has even order. Then HH has an edge. Moreover, every nonempty S∈E(H)S\in\mathcal{E}(H) contains an edge, because each component of H[S]H[S] is connected and has at least two vertices. It follows that E(H)⊆E#(H)\mathcal{E}(H)\subseteq\mathcal{E}^{\#}(H), and hence L(H)L(H) is a subcomplex of L#(H)L^{\#}(H). Put d=m−2d=m-2. Neither complex has a face of dimension d+1d+1, so for each of them, H~d\widetilde{H}_d is the space of dd-cycles. A dd-cycle of L(H)L(H) is also a dd-cycle of L#(H)L^{\#}(H). Hence, by (4),

a(H)=dim⁡H~d(L(H))≤dim⁡H~d(L#(H))=a^(H).a(H)=\dim\widetilde{H}_d(L(H))\leq\dim\widetilde{H}_d(L^{\#}(H))=\widehat{a}(H).

Now let HH be complete multipartite with ∣V(H)∣|V(H)| even. If HH is nonempty and has no edges, then all components of HH are single vertices, so a(H)=0=a^(H)a(H)=0=\widehat{a}(H). Suppose that HH has an edge. If S⊆V(H)S\subseteq V(H) meets at least two parts, then H[S]H[S] is connected: two vertices of SS in different parts are adjacent, and two vertices of SS in the same part have a common neighbor in SS. In particular, HH is connected. For a nonempty set S⊆V(H)S\subseteq V(H) of even size, this gives

H[S] has an edge ⟺ S meets at least two parts ⟺ S∈E(H).H[S]\text{ has an edge}\ \Longleftrightarrow\ S\text{ meets at least two parts}\ \Longleftrightarrow\ S\in\mathcal{E}(H).

Thus, E(H)=E#(H)\mathcal{E}(H)=\mathcal{E}^{\#}(H) and L(H)=L#(H)L(H)=L^{\#}(H). Therefore, (4) gives a(H)=a^(H)a(H)=\widehat{a}(H).

The invariant a^i(G)\widehat{a}_i(G) admits a formula in terms of independent sets. Let Ik(G)I_k(G) be the number of independent sets of size kk in GG with I0(G)=1I_0(G)=1. Let E2iE_{2i} denote the Euler secant numbers [14 A000364].

Theorem 2.5. Let GG be a graph on nn vertices and let 0≤i≤⌊n2⌋0\leq i\leq\left\lfloor\frac{n}{2}\right\rfloor. Then

a^i(G)=∑j=0i(−1)jE2i−2j(n−2j2i−2j)I2j(G).\widehat{a}_i(G)=\sum_{j=0}^{i}(-1)^jE_{2i-2j}\binom{n-2j}{2i-2j}I_{2j}(G).

Proof. First let HH have 2i2i vertices. For each even set S⊆V(H)S\subseteq V(H), put

b(S)=(−1)∣S∣/2a^(H[S]).b(S)=(-1)^{\lvert S\rvert/2}\widehat{a}(H[S]).

If H[S]H[S] has an edge, Proposition 2.1 and (3) identify b(S)b(S) with the Möbius number of E#(H[S])\mathcal{E}^{\#}(H[S]). Its defining recurrence, together with the definition for edgeless graphs, gives

∑T⊆S∣T∣ evenb(T)={1if S is independent,0otherwise.\sum_{\substack{T\subseteq S\\ \lvert T\rvert\ \mathrm{even}}}b(T)= \begin{cases} 1 & \text{if } S \text{ is independent},\\ 0 & \text{otherwise}. \end{cases}

In the poset of all even subsets of V(H)V(H), the Möbius function is

μ(T,S)=(−1)(∣S∣−∣T∣)/2E∣S∣−∣T∣.\mu(T,S)=(-1)^{(\lvert S\rvert-\lvert T\rvert)/2}E_{\lvert S\rvert-\lvert T\rvert}.

This follows by induction from the coefficient identity cos⁡xsec⁡x=1\cos x\sec x=1. Möbius inversion therefore gives

a^(H)=∑T⊆V(H)T independent∣T∣ even(−1)∣T∣/2E2i−∣T∣.(5)\widehat{a}(H)=\sum_{\substack{T\subseteq V(H)\\ T\ \mathrm{independent}\\ \lvert T\rvert\ \mathrm{even}}}(-1)^{\lvert T\rvert/2}E_{2i-\lvert T\rvert}. \tag*{(5)}

This also holds when HH is empty. Now sum (5) over all 2i2i-subsets of V(G)V(G). Each independent set of size 2j2j is contained in exactly (n−2j2i−2j)\binom{n-2j}{2i-2j} 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 a^i\hat{a}_i satisfies a natural inequality under Zykov symmetrization.

For a vertex uu of a graph GG, let NG(u)N_G(u) denote its neighborhood. For distinct nonadjacent vertices u,vu,v, let G+uvG+uv denote the graph obtained from GG by adding the edge uvuv. For a finite set UU, let KUK_U denote the complete graph on UU. For graphs GG and HH on disjoint vertex sets, their join G∨HG\vee H is obtained from G⊔HG\sqcup H by adding all edges between V(G)V(G) and V(H)V(H).

To begin with, we describe how a^i(G)\hat{a}_i(G) changes when an edge is added. Let uu and vv be distinct nonadjacent vertices of GG, and set

W=V(G)∖{u,v}andC=W∖(NG(u)∪NG(v)).W=V(G)\setminus\{u,v\}\qquad\text{and}\qquad C=W\setminus\bigl(N_G(u)\cup N_G(v)\bigr).

Let Ruv(G)R_{uv}(G) be the graph on WW obtained from G[W]G[W] by joining every vertex of W∖CW\setminus C to every other vertex of WW. Equivalently,

Ruv(G)=G[C]∨KW∖C.R_{uv}(G)=G[C]\vee K_{W\setminus C}.

For instance, Figure 1 illustrates the construction.

Figure 1. Ruv(G)R_{uv}(G)

Proposition 3.1. Let HH be a graph with 2m≥22m\ge2 vertices.

(1) For any distinct nonadjacent vertices uu and vv of HH,

a^(H+uv)=a^(H)+a^(Ruv(H)).\hat{a}(H+uv)=\hat{a}(H)+\hat{a}(R_{uv}(H)).

(2) If HH has a universal vertex, then a^(H)≥1\hat{a}(H)\ge1.

Proof. We first prove (1), and then use it to prove (2). (1) Let WW and CC be defined as above, and let R:=Ruv(H)R := R_{uv}(H). Adding uvuv removes exactly the independent sets of the form {u,v}∪T\{u,v\}\cup T, where TT is independent in H[C]H[C]. Thus Theorem 2.5, applied to H+uvH+uv and HH with i=mi=m, gives

a^(H+uv)−a^(H)=∑T⊆CT independent in H[C]∣T∣ even(−1)∣T∣/2E2m−2−∣T∣.\widehat{a}(H+uv)-\widehat{a}(H)=\sum_{\substack{T\subseteq C\\ T\ \text{independent in }H[C]\\ |T|\ \text{even}}}(-1)^{|T|/2}E_{2m-2-|T|}.

Every vertex of W∖CW\setminus C is adjacent to all other vertices of RR. Hence the independent sets of even size in RR are exactly those in H[C]H[C], including the empty set. Applying Theorem 2.5 to RR with i=m−1i=m-1 shows that the sum is a^(R)\widehat{a}(R).

(2) Let ss be a universal vertex of HH. We use induction on mm. If m=1m=1, then H=K2H=K_2 and a^(H)=1\widehat{a}(H)=1.

Suppose m≥2m\ge2. Choose a vertex x≠sx\ne s, and let HxH_x be obtained from HH by deleting the edge sxsx. The vertex ss is adjacent to every vertex of W:=V(H)∖{s,x}W:=V(H)\setminus\{s,x\}. Hence ss and xx have no common non-neighbor in WW, which implies that Rsx(Hx)=KWR_{sx}(H_x)=K_W. Combining (1) with the induction hypothesis applied to KWK_W, we obtain

a^(H)=a^(Hx)+a^(KW)≥a^(KW)≥1,\widehat{a}(H)=\widehat{a}(H_x)+\widehat{a}(K_W)\ge\widehat{a}(K_W)\ge1,

as desired. □

If I⊆V(G)I\subseteq V(G) contains uu and vv, then the common non-neighbors of uu and vv in G[I]G[I] are the vertices of C∩IC\cap I. Hence

Ruv(G[I])=Ruv(G)[I∖{u,v}].(6)R_{uv}(G[I])=R_{uv}(G)[I\setminus\{u,v\}]. \tag*{(6)}

Lemma 3.2. Let u,vu,v be nonadjacent vertices of a graph GG. Then

a^i(G+uv)−a^i(G)=a^i−1(Ruv(G))for every i≥1.\widehat{a}_i(G+uv)-\widehat{a}_i(G)=\widehat{a}_{i-1}(R_{uv}(G)) \qquad\text{for every } i\ge1.

Proof. Let I⊆V(G)I\subseteq V(G) with ∣I∣=2i|I|=2i. If II does not contain both uu and vv, then (G+uv)[I]=G[I](G+uv)[I]=G[I]. If u,v∈Iu,v\in I, then (G+uv)[I]=G[I]+uv(G+uv)[I]=G[I]+uv, and Proposition 3.1(1) and (3.1) give

a^((G+uv)[I])−a^(G[I])=a^(Ruv(G)[I∖{u,v}]).\widehat{a}((G+uv)[I])-\widehat{a}(G[I])=\widehat{a}(R_{uv}(G)[I\setminus\{u,v\}]).

As II runs over the 2i2i-subsets of V(G)V(G) that contain uu and vv, the set I∖{u,v}I\setminus\{u,v\} runs over the (2i−2)(2i-2)-subsets of V(Ruv(G))V(R_{uv}(G)). Summing proves the identity. The last statement follows because a^i−1≥0\widehat{a}_{i-1}\ge0 and a^0=1\widehat{a}_0=1.

Consequently, a^i\widehat{a}_i is monotone with respect to edge inclusion.

Definition 3.3. Let u,vu,v be nonadjacent vertices of GG. The graph Gu←vG_{u\leftarrow v} is obtained from GG by deleting all edges at uu and then joining uu to every vertex of NG(v)N_G(v).

The vertices uu and vv are nonadjacent in Gu←vG_{u\leftarrow v} and both have neighborhood NG(v)N_G(v). All edges not incident to uu are unchanged. Moreover,

e(Gu←v)+e(Gv←u)=2e(G).e(G_{u\leftarrow v})+e(G_{v\leftarrow u})=2e(G).

Proposition 3.4. If GG is Kr+1K_{r+1}-free, then so is Gu←vG_{u\leftarrow v}.

Proof. Let QQ be a clique of Gu←vG_{u\leftarrow v}. If u∉Qu \notin Q, then QQ is a clique of GG. If u∈Qu \in Q, then v∉Qv \notin Q and Q∖{u}⊆NG(v)Q \setminus\{u\} \subseteq N_G(v). Therefore, (Q∖{u})∪{v}(Q \setminus\{u\}) \cup\{v\} is a clique of GG of the same size.

Lemma 3.5. If uu and vv are nonadjacent vertices of GG, then

a^i(Gu←v+uv)+a^i(Gv←u+uv)=2a^i(G+uv),for each i≥0.\widehat{a}_i(G_{u\leftarrow v}+uv)+\widehat{a}_i(G_{v\leftarrow u}+uv)=2\widehat{a}_i(G+uv), \qquad\text{for each } i\geq0.

Proof. If 2i>∣V(G)∣2i > |V(G)|, then the desired identity is immediate, since all three terms are zero. Thus, we may assume that 2i≤∣V(G)∣2i \leq|V(G)|. By Theorem 2.5, it is enough to show that

Ik(Gu←v+uv)+Ik(Gv←u+uv)=2Ik(G+uv)I_k(G_{u\leftarrow v}+uv)+I_k(G_{v\leftarrow u}+uv)=2I_k(G+uv)

for every k≥0k \geq0.

Since uvuv is an edge, no independent set in these graphs contains both uu and vv. Independent sets containing neither vertex are the same in all three graphs. For the sets containing exactly one of them, put W=V(G)∖{u,v}W=V(G)\setminus\{u,v\}. Let pp and qq be the numbers of independent (k−1)(k-1)-sets in G[W∖NG(u)]G[W\setminus N_G(u)] and G[W∖NG(v)]G[W\setminus N_G(v)], respectively. The contributions of these independent sets to

Ik(Gu←v+uv),Ik(Gv←u+uv),Ik(G+uv)I_k(G_{u\leftarrow v}+uv), \qquad I_k(G_{v\leftarrow u}+uv), \qquad I_k(G+uv)

are 2q2q, 2p2p, and p+qp+q, respectively. This proves the identity for k≥1k\geq1, while k=0k=0 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 a^i\widehat{a}_i.

Theorem 3.6. Let uu, vv be nonadjacent vertices of GG. For every i≥0i\geq0,

a^i(Gu←v)+a^i(Gv←u)≥2a^i(G).\widehat{a}_i(G_{u\leftarrow v})+\widehat{a}_i(G_{v\leftarrow u})\geq2\widehat{a}_i(G).

Proof. For i=0i=0, both sides equal 2. Suppose i≥1i\geq1, and write G1=Gu←vG_1=G_{u\leftarrow v} and G2=Gv←uG_2=G_{v\leftarrow u}. By Lemma 3.2, for G∈{G,G1,G2}G\in\{G,G_1,G_2\},

a^i(G)=a^i(G+uv)−a^i−1(Ruv(G)).\widehat{a}_i(G)=\widehat{a}_i(G+uv)-\widehat{a}_{i-1}(R_{uv}(G)).

Hence, using Lemma 3.5,

a^i(G1)+a^i(G2)−2a^i(G)=a^i(G1+uv)+a^i(G2+uv)−2a^i(G+uv)−a^i−1(Ruv(G1))−a^i−1(Ruv(G2))+2a^i−1(Ruv(G))=2a^i−1(Ruv(G))−a^i−1(Ruv(G1))−a^i−1(Ruv(G2)).\begin{aligned} \widehat{a}_i(G_1)+\widehat{a}_i(G_2)-2\widehat{a}_i(G) &=\widehat{a}_i(G_1+uv)+\widehat{a}_i(G_2+uv)-2\widehat{a}_i(G+uv) \\ &\quad-\widehat{a}_{i-1}(R_{uv}(G_1))-\widehat{a}_{i-1}(R_{uv}(G_2))+2\widehat{a}_{i-1}(R_{uv}(G)) \\ &=2\widehat{a}_{i-1}(R_{uv}(G))-\widehat{a}_{i-1}(R_{uv}(G_1))-\widehat{a}_{i-1}(R_{uv}(G_2)). \end{aligned}

To finish the proof, it is sufficient to show that

a^i−1(Ruv(G))−a^i−1(Ruv(Gj))≥0for j=1,2.(7)\widehat{a}_{i-1}(R_{uv}(G))-\widehat{a}_{i-1}(R_{uv}(G_j))\geq0 \qquad\text{for } j=1,2. \tag*{(7)}

Let W=V(G)∖{u,v}W=V(G)\setminus\{u,v\}. Since only edges incident to uu or vv are changed,

G[W]=G1[W]=G2[W].G[W]=G_1[W]=G_2[W].

Therefore,

Ruv(G1)=G[W∖NG(v)]∨KNG(v)⊆G[W∖(NG(u)∪NG(v))]∨KNG(u)∪NG(v)=Ruv(G),Ruv(G2)=G[W∖NG(u)]∨KNG(u)⊆G[W∖(NG(u)∪NG(v))]∨KNG(u)∪NG(v)=Ruv(G).\begin{aligned} R_{uv}(G_1)&=G[W\setminus N_G(v)]\vee K_{N_G(v)} \\ &\subseteq G[W\setminus(N_G(u)\cup N_G(v))]\vee K_{N_G(u)\cup N_G(v)}=R_{uv}(G),\\ R_{uv}(G_2)&=G[W\setminus N_G(u)]\vee K_{N_G(u)} \\ &\subseteq G[W\setminus(N_G(u)\cup N_G(v))]\vee K_{N_G(u)\cup N_G(v)}=R_{uv}(G). \end{aligned}

Since a^i−1\widehat{a}_{i-1} is monotone with respect to edge inclusion,

a^i−1(Ruv(Gj))≤a^i−1(Ruv(G))for j=1,2.\widehat{a}_{i-1}(R_{uv}(G_j)) \le\widehat{a}_{i-1}(R_{uv}(G)) \qquad\text{for } j=1,2.

Thus (7) holds, completing the proof.

We write CnC_n for the cycle graph on nn vertices.

Remark 3.7. For the graph aa-numbers, the inequality in Theorem 3.6 does not hold in general. For example, let G=P4G=P_4 be the path on four vertices labeled 1,2,3,41,2,3,4 in this order. Then

G1←3≅C4andG3←1≅P3⊔K1.G_{1\leftarrow3} \cong C_4 \qquad\text{and} \qquad G_{3\leftarrow1} \cong P_3 \sqcup K_1.

Since

a2(P4)=2,a2(C4)=3,a2(P3⊔K1)=0,a_2(P_4)=2,\qquad a_2(C_4)=3,\qquad a_2(P_3\sqcup K_1)=0,

we have

a2(G1←3)+a2(G3←1)=3<4=2a2(G).a_2(G_{1\leftarrow3})+a_2(G_{3\leftarrow1})=3<4=2a_2(G).

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 0≤z≤N0\le z\le N, let

SN,z=K‾z∨KN−z.S_{N,z}=\overline{K}_z\vee K_{N-z}.

where K‾z\overline{K}_z is the discrete graph on zz vertices and KN−zK_{N-z} is the complete graph on N−zN-z vertices. This is the complete multipartite graph on NN vertices with one part of size zz and N−zN-z parts of size one. For disjoint sets V1,…,VrV_1,\ldots,V_r, we write K(V1,…,Vr)K(V_1,\ldots,V_r) for the complete multipartite graph with parts V1,…,VrV_1,\ldots,V_r, allowing empty parts.

Lemma 4.1. For the complete multipartite graph K=K(V1,…,Vr)K=K(V_1,\ldots,V_r) with r≥2r\ge2, the following hold.

(1) e(K~)−e(K)=∣V1∣−∣V2∣−1e(\widetilde{K})-e(K)=|V_1|-|V_2|-1.

(2) For each i≥1i\ge1,

a^i(K~)−a^i(K)=∑ℓ=∣V2∣∣V1∣−2a^i−1(Sn−2,ℓ).\widehat{a}_i(\widetilde{K})-\widehat{a}_i(K)=\sum_{\ell=|V_2|}^{|V_1|-2}\widehat{a}_{i-1}(S_{n-2,\ell}).

(3) Assume that ∣V1∣≥∣V2∣+2|V_1|\ge|V_2|+2. For 1≤i≤n/21\le i\le n/2,

a^i(K~)−a^i(K)≥1,\widehat{a}_i(\widetilde{K})-\widehat{a}_i(K)\ge1,

where K~=K(V1∖{w},V2∪{w},V3,…,Vr)\widetilde{K}=K(V_1\setminus\{w\},V_2\cup\{w\},V_3,\ldots,V_r) for a fixed w∈V1w\in V_1.

Proof. The edges between V1∪V2V_1\cup V_2 and the other parts do not change. The number of edges within V1∪V2V_1\cup V_2 changes from ∣V1∣∣V2∣|V_1||V_2| to (∣V1∣−1)(∣V2∣+1)(|V_1|-1)(|V_2|+1). Hence

e(K~)−e(K)=(∣V1∣−1)(∣V2∣+1)−∣V1∣∣V2∣=∣V1∣−∣V2∣−1,e(\widetilde{K})-e(K)=(|V_1|-1)(|V_2|+1)-|V_1||V_2|=|V_1|-|V_2|-1,

which proves (1).

Let G0G_0 be the complete multipartite graph with parts {w},V1∖{w},V2,…,Vr\{w\},V_1\setminus\{w\},V_2,\ldots,V_r. Then KK is obtained from G0G_0 by deleting all edges between ww and V1∖{w}V_1\setminus\{w\}, and K~\widetilde{K} is obtained from G0G_0 by deleting all edges between ww and V2V_2.

Let U={u1,…,uk}U=\{u_1,\ldots,u_k\} be a part of G0G_0 other than {w}\{w\}. For 1≤t≤k1\le t\le k, let GtG_t be obtained from G0G_0 by deleting the edges wu1,…,wutwu_1,\ldots,wu_t. Then Gt−1=Gt+wutG_{t-1}=G_t+wu_t. The common non-neighbors of ww and utu_t in GtG_t are u1,…,ut−1u_1,\ldots,u_{t-1}, which are pairwise nonadjacent. Hence

Rwut(Gt)≅K‾t−1∨Kn−t−1=Sn−2,t−1.R_{wu_t}(G_t) \cong\overline{K}_{t-1}\vee K_{n-t-1}=S_{n-2,t-1}.

Applying Lemma 3.2 at each step and summing gives

a^i(G)−a^i(Gk)=∑ℓ=0k−1a^i−1(Sn−2,ℓ).\widehat{a}_i(G)-\widehat{a}_i(G_k)=\sum_{\ell=0}^{k-1}\widehat{a}_{i-1}(S_{n-2,\ell}).

Applying this identity to U=V1∖{w}U=V_1\setminus\{w\} and U=V2U=V_2, and subtracting the resulting identities, gives

a^i(K~)−a^i(K)=∑ℓ=∣V2∣∣V1∣−2a^i−1(Sn−2,ℓ),\widehat{a}_i(\widetilde{K})-\widehat{a}_i(K)=\sum_{\ell=|V_2|}^{|V_1|-2}\widehat{a}_{i-1}(S_{n-2,\ell}),

which proves (2).

Suppose that 1≤i≤n/21\le i\le n/2. Since all terms in the sum in (2) are nonnegative, it suffices to show that a^i−1(Sn−2,∣V2∣)≥1\widehat{a}_{i-1}(S_{n-2,|V_2|})\ge1. If i=1i=1, then a^0(Sn−2,∣V2∣)=1\widehat{a}_0(S_{n-2,|V_2|})=1. Assume that i≥2i\ge2, and then n≥4n\ge4. Since ∣V1∣≥∣V2∣+2|V_1|\ge|V_2|+2 and ∣V1∣+∣V2∣≤n|V_1|+|V_2|\le n, we have

∣V2∣≤n2−1≤n−3.|V_2|\le\frac{n}{2}-1\le n-3.

Thus Sn−2,∣V2∣S_{n-2,|V_2|} has a singleton part {s}\{s\}, and ss is adjacent to every other vertex. Since n≥2in\ge2i, there is a set TT of $2i-2$ vertices of Sn−2,∣V2∣S_{n-2,|V_2|} containing $s. By the definition of a^i−1\widehat{a}_{i-1} and Proposition 3.1(2),

a^i−1(Sn−2,∣V2∣)≥a^(Sn−2,∣V2∣[T])≥1,\widehat{a}_{i-1}(S_{n-2,|V_2|})\ge\widehat{a}(S_{n-2,|V_2|}[T])\ge1,

which proves (3).

For i≥0i\ge0 and λ>0\lambda>0, define

Φi,λ(G)=a^i(G)−e(G)λ.\Phi_{i,\lambda}(G)=\widehat{a}_i(G)-\frac{e(G)}{\lambda}.

Lemma 4.2. Let n,r≥1n,r\ge1, i≥0i\ge0, and λ>0\lambda>0, and fix a set VV of nn vertices. Among all Kr+1K_{r+1}-free graphs on VV, the function Φi,λ\Phi_{i,\lambda} attains its maximum at a complete multipartite graph with at most rr nonempty parts.

Proof. For a graph HH on VV and a vertex w∈Vw\in V, let dH(w)=∣NH(w)∣d_H(w)=|N_H(w)|, and put

D(H)=∑w∈VdH(w)2.D(H)=\sum_{w\in V}d_H(w)^2.

There are finitely many graphs on VV. Among the Kr+1K_{r+1}-free graphs on VV that maximize Φi,λ\Phi_{i,\lambda}, choose one, say GG, for which

D(G)=∑w∈VdG(w)2D(G)=\sum_{w\in V}d_G(w)^2

is largest. Let u,vu,v be distinct nonadjacent vertices of GG. Since

e(Gu←v)+e(Gv←u)=2e(G),e(G_{u\leftarrow v})+e(G_{v\leftarrow u})=2e(G),

Theorem 3.6 gives

Φi,λ(Gu←v)+Φi,λ(Gv←u)≥2Φi,λ(G).(8)\Phi_{i,\lambda}(G_{u\leftarrow v})+\Phi_{i,\lambda}(G_{v\leftarrow u})\ge2\Phi_{i,\lambda}(G). \tag*{(8)}

By Proposition 3.4, the graphs Gu←vG_{u\leftarrow v} and Gv←uG_{v\leftarrow u} are Kr+1K_{r+1}-free. The maximality of Φi,λ(G)\Phi_{i,\lambda}(G) therefore gives

Φi,λ(Gu←v)≤Φi,λ(G)andΦi,λ(Gv←u)≤Φi,λ(G).\Phi_{i,\lambda}(G_{u\leftarrow v}) \le\Phi_{i,\lambda}(G) \quad\text{and}\quad\Phi_{i,\lambda}(G_{v\leftarrow u}) \le\Phi_{i,\lambda}(G).

Together with (8), this shows that both Gu←vG_{u\leftarrow v} and Gv←uG_{v\leftarrow u} maximize Φi,λ\Phi_{i,\lambda}.

We compute D(Gu←v)+D(Gv←u)−2D(G)D(G_{u\leftarrow v}) + D(G_{v\leftarrow u}) - 2D(G). In Gu←vG_{u\leftarrow v}, both uu and vv have degree dG(v)d_G(v), while in Gv←uG_{v\leftarrow u}, both have degree dG(u)d_G(u). Thus uu and vv contribute

2dG(v)2+2dG(u)2−2(dG(u)2+dG(v)2)=0.2d_G(v)^2 + 2d_G(u)^2 - 2\left(d_G(u)^2 + d_G(v)^2\right) = 0.

Let w∈V∖{u,v}w \in V \setminus\{u,v\} and d=dG(w)d=d_G(w). If w∈NG(u)△NG(v)w \in N_G(u)\mathbin{\triangle}N_G(v), then ww has degree d+1d+1 in one of Gu←v,Gv←uG_{u\leftarrow v},G_{v\leftarrow u} and degree d−1d-1 in the other. Thus, it contributes

(d+1)2+(d−1)2−2d2=2.(d+1)^2 + (d-1)^2 - 2d^2 = 2.

Otherwise, ww has the same degree in GG, Gu←vG_{u\leftarrow v}, and Gv←uG_{v\leftarrow u}. Hence

D(Gu←v)+D(Gv←u)−2D(G)=2∣NG(u)△NG(v)∣.D(G_{u\leftarrow v}) + D(G_{v\leftarrow u}) - 2D(G) = 2\lvert N_G(u)\mathbin{\triangle}N_G(v)\rvert.

Since Gu←vG_{u\leftarrow v} and Gv←uG_{v\leftarrow u} also maximize Φi,λ\Phi_{i,\lambda}, the choice of GG gives

D(Gu←v)≤D(G)andD(Gv←u)≤D(G).D(G_{u\leftarrow v}) \le D(G) \quad\text{and}\quad D(G_{v\leftarrow u}) \le D(G).

Therefore NG(u)=NG(v)N_G(u)=N_G(v).

Thus any two distinct nonadjacent vertices of GG have the same neighborhood. It follows that nonadjacency is transitive. Indeed, if uu and vv are nonadjacent, vv and ww are nonadjacent, and u≠wu\ne w, then

w∉NG(v)=NG(u).w \notin N_G(v)=N_G(u).

Thus uu and ww 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 GG is complete multipartite. Choosing one vertex from each part gives a clique. Since GG is Kr+1K_{r+1}-free, it follows that GG has at most rr nonempty parts.

We now prove the quantitative bound and complete the proof of Theorem 1.1.

Lemma 4.3. Let n,r≥1n,r\ge1 and 1≤i≤n/21\le i\le n/2, and let GG be a Kr+1K_{r+1}-free graph on nn vertices. Then

a^i(Tr(n))−a^i(G)≥e(Tr(n))−e(G)n−1.\hat a_i(T_r(n))-\hat a_i(G)\ge\frac{e(T_r(n))-e(G)}{n-1}.

Proof. Since 1≤i<n/21\le i<n/2, we have n>2n>2. Let V=V(G)V=V(G). By Lemma 4.2, there is a complete multipartite graph KK on VV with at most rr nonempty parts such that

Φi,n−1(G)≤Φi,n−1(K).\Phi_{i,n-1}(G)\le\Phi_{i,n-1}(K).

Write K=K(V1,…,Vr)K=K(V_1,\ldots,V_r), allowing empty parts.

Suppose that two parts, say VpV_p and VqV_q, satisfy ∣Vp∣≥∣Vq∣+2\lvert V_p\rvert\ge\lvert V_q\rvert+2. Move one vertex from VpV_p to VqV_q. By Lemma 4.1(1) and (3), this move increases a^i\hat a_i by at least 1 and increases the number of edges by

∣Vp∣−∣Vq∣−1≤n−1.\lvert V_p\rvert-\lvert V_q\rvert-1\le n-1.

Hence Φi,n−1\Phi_{i,n-1} does not decrease. Moreover, the move decreases

∑j=1r∣Vj∣2\sum_{j=1}^{r}\lvert V_j\rvert^2

by 2(∣Vp∣−∣Vq∣−1)>02(|V_p|-|V_q|-1)>0. 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 Tr(n)T_r(n). Therefore

Φi,n−1(G)≤Φi,n−1(K)≤Φi,n−1(Tr(n)).\Phi_{i,n-1}(G)\le\Phi_{i,n-1}(K)\le\Phi_{i,n-1}(T_r(n)).

Equivalently,

a^i(Tr(n))−a^i(G)≥e(Tr(n))−e(G)n−1.\widehat{a}_i(T_r(n))-\widehat{a}_i(G)\ge\frac{e(T_r(n))-e(G)}{n-1}.

We now prove Theorem 1.1.

Proof of Theorem 1.1. If i=0i=0, both sides equal 1. If 2i>n2i>n, both sides equal 0. Let 1≤i≤n/21\le i\le n/2. By Turán’s theorem, e(G)≤e(Tr(n))e(G)\le e(T_r(n)). Since Tr(n)T_r(n) is complete multipartite, Proposition 2.4 and Lemma 4.3 give

ai(G)≤a^i(G)≤a^i(Tr(n))−e(Tr(n))−e(G)n−1≤a^i(Tr(n))=ai(Tr(n)).a_i(G)\le\widehat{a}_i(G)\le\widehat{a}_i(T_r(n))-\frac{e(T_r(n))-e(G)}{n-1}\le\widehat{a}_i(T_r(n))=a_i(T_r(n)).

If ai(G)=ai(Tr(n))a_i(G)=a_i(T_r(n)), then all these inequalities are equalities. In particular, e(G)=e(Tr(n))e(G)=e(T_r(n)), so G≅Tr(n)G\cong T_r(n) by the equality case of Turán’s theorem. The converse is clear.

Remark 4.4. Let n,r≥1n,r\ge1 and 1≤i≤n/21\le i\le n/2, and let GG be a Kr+1K_{r+1}-free graph on nn vertices. Proposition 2.4 and Lemma 4.3 give

ai(Tr(n))−ai(G)≥e(Tr(n))−e(G)n−1.a_i(T_r(n))-a_i(G)\ge\frac{e(T_r(n))-e(G)}{n-1}.

Indeed, ai(G)≤a^i(G)a_i(G)\le\widehat{a}_i(G) and ai(Tr(n))=a^i(Tr(n))a_i(T_r(n))=\widehat{a}_i(T_r(n)).

Proof of Theorem 1.2

When only the part sizes matter, we write Kn1,…,nrK_{n_1,\ldots,n_r} for the complete multipartite graph with part sizes n1,…,nrn_1,\ldots,n_r.

Example 5.1. The graph T2(6)T_2(6) is K3,3K_{3,3}. Its first three aa-numbers are

a1(K3,3)=9,a2(K3,3)=39,a3(K3,3)=31.a_1(K_{3,3})=9,\qquad a_2(K_{3,3})=39,\qquad a_3(K_{3,3})=31.

To compute a2a_2, note that a four vertex subset meets the two parts in sizes (1,3)(1,3), (2,2)(2,2) or (3,1)(3,1). Since a(K1,3)=2a(K_{1,3})=2 and a(K2,2)=3a(K_{2,2})=3, we obtain

a2(K3,3)=3⋅2+9⋅3+3⋅2=39.a_2(K_{3,3})=3\cdot2+9\cdot3+3\cdot2=39.

The defining recurrence then gives

sa⁡(K3,3)=−(1−9+39)=−31.\operatorname{sa}(K_{3,3})=-(1-9+39)=-31.

Thus every triangle-free graph GG on six vertices satisfies

a1(G)≤9,a2(G)≤39,a3(G)≤31,a_1(G)\le9,\qquad a_2(G)\le39,\qquad a_3(G)\le31,

and equality in any one of these inequalities holds if and only if G≅K3,3G\cong K_{3,3}. Equivalently, the rational Poincaré polynomial of M(T2(6))M(T_2(6)) is

∑i≥0βi(M(T2(6)))ti=1+9t+39t2+31t3,\sum_{i\ge0}\beta_i(M(T_2(6)))t^i=1+9t+39t^2+31t^3,
GGa1(G)a_1(G)a2(G)a_2(G)a3(G)a_3(G)
P6P_6595
C6C_661510
K1,5K_{1,5}52016
T2(6)=K3,3T_2(6)=K_{3,3}93931

Table 1. Graph aa-numbers

and it bounds the rational Poincaré polynomials of M(G)M(G) coefficientwise for these graphs.

Table 5 compares K3,3K_{3,3} 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 K1,5K_{1,5} has fewer edges than C6C_6, its second and third aa-numbers are larger. Thus the number of edges alone does not determine the ordering of the higher aa-numbers.

We now compute the aa-numbers of complete multipartite graphs. For K=Kn1,…,nrK=K_{n_1,\ldots,n_r}, put n=n1+⋯+nrn=n_1+\cdots+n_r and

B2j=∑ℓ=1r(nℓ2j)(j≥1).B_{2j}=\sum_{\ell=1}^{r}\binom{n_\ell}{2j}\qquad(j\ge1).

We use the convention (vu)=0\binom{v}{u}=0 for integers v>u≥0v>u\ge0.

Lemma 5.2. If 0≤2i≤n0\le2i\le n, then

ai(Kn1,…,nr)=E2i(n2i)+∑j=1i(−1)jE2i−2j(n−2j2i−2j)B2j.(9)a_i(K_{n_1,\ldots,n_r})=E_{2i}\binom{n}{2i}+\sum_{j=1}^{i}(-1)^jE_{2i-2j}\binom{n-2j}{2i-2j}B_{2j}. \tag*{(9)}

In particular, ai(Kn)=E2i(n2i)a_i(K_n)=E_{2i}\binom{n}{2i}.

Proof. Every nonempty independent set in a complete multipartite graph lies in a unique part. Hence I2j(K)=B2jI_{2j}(K)=B_{2j} for j≥1j\ge1. Apply Theorem 2.5 and the equality ai(K)=a^i(K)a_i(K)=\widehat{a}_i(K) from Proposition 2.4.

The complete multipartite case of this formula can also be obtained from the generating function stated in [12]

∑k1,…,kr≥0a(Kk1,…,kr)∏ℓ=1rxℓkℓkℓ!=1−r+∑ℓ=1rcos⁡xℓcos⁡(x1+⋯+xr).\sum_{k_1,\ldots,k_r\ge0}a(K_{k_1,\ldots,k_r})\prod_{\ell=1}^{r}\frac{x_\ell^{k_\ell}}{k_\ell!}=\frac{1-r+\sum_{\ell=1}^{r}\cos x_\ell}{\cos(x_1+\cdots+x_r)}.

Thus Lemma 5.2 is also a finite coefficient form of that known generating function.

For the first three degrees,

a1(K)=(n2)−B2,a_1(K)=\binom{n}{2}-B_2,
a2(K)=5(n4)−(n−22)B2+B4,a_2(K)=5\binom{n}{4}-\binom{n-2}{2}B_2+B_4,
a3(K)=61(n6)−5(n−24)B2+(n−42)B4−B6.a_3(K)=61\binom{n}{6}-5\binom{n-2}{4}B_2+\binom{n-4}{2}B_4-B_6.

The identity for ai(K)a_i(K) is valid for n≥2in\ge2i.

nnrra1a_1a2a_2a3a_3a4a_4a5a_5
4243000
4354000
4465000
52613000
53819000
54922000
551025000
629393100
6312574600
6413635100
6615756100
82161728206630
832124511839580
8424290140811410
8828350170813850
1022550059602891523431
1033371586254190433962
10437826100104866139441
1010451050128106232550521

Table 2. Values of ai(Tr(n))a_i(T_r(n)).

Lemma 5.3. Write n=qr+sn=qr+s, where 0≤s<r0\le s<r, and put

B2j(n,r)=(r−s)(q2j)+s(q+12j).B_{2j}(n,r)=(r-s)\binom{q}{2j}+s\binom{q+1}{2j}.

For 0≤2i≤n0\le2i\le n, we have

ai(Tr(n))=E2i(n2i)+∑j=1i(−1)jE2i−2j(n−2j2i−2j)B2j(n,r).(10)a_i(T_r(n))=E_{2i}\binom{n}{2i}+\sum_{j=1}^{i}(-1)^jE_{2i-2j}\binom{n-2j}{2i-2j}B_{2j}(n,r). \tag*{(10)}

Proof. The graph Tr(n)T_r(n) has r−sr-s parts of size qq and ss parts of size q+1q+1. Applying Lemma 5.2 gives the formula.

Table 5 lists values of (5.2).

Throughout this section, the degree i≥1i\ge1 is fixed as the number of vertices tends to infinity. For a graph GG on n≥2in\ge2i vertices, define

di(G)=ai(G)E2i(n2i)=ai(G)ai(Kn).d_i(G)=\frac{a_i(G)}{E_{2i}\binom{n}{2i}}=\frac{a_i(G)}{a_i(K_n)}.

By Theorem 1.1, 0≤di(G)≤10\le d_i(G)\le1. For i=1i=1, this is the usual edge density.

Let HH be a fixed graph with at least one edge. If n≥m≥2in\ge m\ge2i and SS is a uniformly chosen mm-subset of V(G)V(G), then

E[di(G[S])]=di(G).(11)\mathbb{E}\left[d_i(G[S])\right]=d_i(G). \tag*{(11)}

Indeed, each 2i2i-subset of V(G)V(G) is contained in the same number of mm-subsets. Since every induced subgraph of an HH-free graph is HH-free, the sequence

ex⁡i(n,F)(n2i)(n≥2i)\frac{\operatorname{ex}_i(n,F)}{\binom{n}{2i}} \qquad(n \ge2i)

is nonincreasing and bounded below by zero. We therefore define the iith aa-Turán density of HH by

πi(H)=lim⁡n→∞ex⁡i(n,F)(n2i).(12)\pi_i(H)=\lim_{n\to\infty}\frac{\operatorname{ex}_i(n,F)}{\binom{n}{2i}}. \tag*{(12)}

For r,i≥1r,i\ge1, put

τi(r)=1+1E2i∑j=1i(−1)j(2i2j)E2i−2jr1−2j.(13)\tau_i(r)=1+\frac{1}{E_{2i}}\sum_{j=1}^{i}(-1)^j\binom{2i}{2j}E_{2i-2j}r^{1-2j}. \tag*{(13)}

The following proposition shows that τi(r)\tau_i(r) is the limiting density of the Turán graphs.

Lemma 5.4. For fixed r,i≥1r,i\ge1,

ai(Tr(n))=E2iτi(r)(n2i)+Or,i(n2i−1).a_i(T_r(n))=E_{2i}\tau_i(r)\binom{n}{2i}+O_{r,i}(n^{2i-1}).

In particular,

lim⁡n→∞di(Tr(n))=τi(r).\lim_{n\to\infty}d_i(T_r(n))=\tau_i(r).

Proof. Each part of Tr(n)T_r(n) has size n/r+O(1)n/r+O(1). Hence, for fixed j≥1j\ge1,

B2j(n,r)=r1−2j(2j)!n2j+Or,j(n2j−1).B_{2j}(n,r)=\frac{r^{1-2j}}{(2j)!}n^{2j}+O_{r,j}(n^{2j-1}).

It follows that

(n−2j2i−2j)B2j(n,r)(n2i)=(2i2j)r1−2j+Or,i(n−1).\frac{\binom{n-2j}{2i-2j}B_{2j}(n,r)}{\binom{n}{2i}} =\binom{2i}{2j}r^{1-2j}+O_{r,i}(n^{-1}).

By (5.2),

ai(Tr(n))(n2i)=E2i+∑j=1i(−1)jE2i−2j(n−2j2i−2j)B2j(n,r)(n2i)=E2i+∑j=1i(−1)jE2i−2j(2i2j)r1−2j+Or,i(n−1)=E2iτi(r)+Or,i(n−1).\begin{aligned} \frac{a_i(T_r(n))}{\binom{n}{2i}} =E_{2i}+\sum_{j=1}^{i}(-1)^jE_{2i-2j}\frac{\binom{n-2j}{2i-2j}B_{2j}(n,r)}{\binom{n}{2i}} \\ &=E_{2i}+\sum_{j=1}^{i}(-1)^jE_{2i-2j}\binom{2i}{2j}r^{1-2j}+O_{r,i}(n^{-1}) \\ &=E_{2i}\tau_i(r)+O_{r,i}(n^{-1}). \end{aligned}

Multiplying by (n2i)\binom{n}{2i} proves the lemma. □

We use a standard consequence of the clique blow-up argument. If HH is fixed and χ(H)=q≥2\chi(H)=q\ge2, then every HH-free graph on nn vertices has o(nq)o(n^q) copies of KqK_q, uniformly over all such graphs. Indeed, HH is a subgraph of a fixed blow-up of KqK_q, so this is a special case of [1 Proposition 2.1]. Isolated vertices of HH do not affect this statement, since they can be added to any copy of the remaining graph once n≥∣V(H)∣n\ge|V(H)|.

Proof of Theorem 1.2. Put r=χ(H)−1r=\chi(H)-1. The graph Tr(n)T_r(n) is rr-partite and hence HH-free, which gives the lower bound.

For the upper bound, fix an integer m≥max⁡{2i,r+1}m\ge\max\{2i,r+1\}. Let GG be any HH-free graph on n≥mn\ge m vertices, and choose an mm-subset SS uniformly at random. By the preceding clique bound, GG has o(nr+1)o(n^{r+1}) copies of Kr+1K_{r+1}. Each fixed copy is contained in SS with probability

(n−r−1m−r−1)(nm)=Om(n−r−1).\frac{\binom{n-r-1}{m-r-1}}{\binom{n}{m}}=O_m(n^{-r-1}).

Thus the probability pnp_n that G[S]G[S] contains a Kr+1K_{r+1} is o(1)o(1), uniformly over all HH-free graphs GG. On the complementary event, Theorem 1.1 gives

di(G[S])≤di(Tr(m)).d_i(G[S])\le d_i(T_r(m)).

On the exceptional event, we use di(G[S])≤1d_i(G[S])\le1. By (11),

di(G)≤(1−pn)di(Tr(m))+pn≤di(Tr(m))+o(1).d_i(G)\le(1-p_n)d_i(T_r(m))+p_n\le d_i(T_r(m))+o(1).

First let n→∞n\to\infty, keeping mm fixed. Then let m→∞m\to\infty and apply Lemma 5.4. This gives πi(H)≤τi(r)\pi_i(H)\le\tau_i(r). The lower bound gives the reverse inequality, and Lemma 5.4 yields the theorem. □\square

For every bipartite HH with an edge, πi(H)=0\pi_i(H)=0 and hence ex⁡i(n,F)=o(n2i)\operatorname{ex}_i(n,F)=o(n^{2i}) for each fixed i≥1i\ge1. By (2), the theorem also determines the leading asymptotic maximum of βi(M(G))\beta_i(M(G)) over all HH-free graphs on nn vertices.

The first three densities are

τ1(r)=1−1r,\tau_1(r)=1-\frac{1}{r},
τ2(r)=1−65r+15r3,\tau_2(r)=1-\frac{6}{5r}+\frac{1}{5r^3},
τ3(r)=1−7561r+1561r3−161r5.\tau_3(r)=1-\frac{75}{61r}+\frac{15}{61r^3}-\frac{1}{61r^5}.

Setting τ0(r)=1\tau_0(r)=1, we can also write (13) as

∑i>0E2iτi(r)x2i(2i)!=1−r+rcos⁡(x/r)cos⁡x.\sum_{i>0}E_{2i}\tau_i(r)\frac{x^{2i}}{(2i)!}=\frac{1-r+r\cos(x/r)}{\cos x}.

For example, τ1(2)=1/2\tau_1(2)=1/2, τ2(2)=17/40\tau_2(2)=17/40 and τ3(2)=811/1952\tau_3(2)=811/1952. tbl:5 gives further values, rounded to six decimal places.

rrτ1(r)\tau_1(r)τ2(r)\tau_2(r)τ3(r)\tau_3(r)τ4(r)\tau_4(r)
20.5000000.4250000.4154710.414356
30.6666670.6074070.5992040.598206
40.7500000.7031250.6964490.695626
50.8000000.7616000.7560600.755373
100.9000000.8802000.8772950.876931

Table 3. Normalized aa-Turán densities τi(r)\tau_i(r).

Remark 5.5. For fixed r≥2r\ge2, the simple poles at x=±π/2x=\pm\pi/2 and x=±3π/2x=\pm3\pi/2 in the preceding generating function give τi(r)=1−r+rcos⁡(π/(2r))+Or(9−i)\tau_i(r)=1-r+r\cos(\pi/(2r))+O_r(9^{-i}) as i→∞i\to\infty, 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. [1]N. Alon and C. Shikhelman, Many T copies in H-free graphs, J. Combin. Theory Ser. B 121 (2016), 146–172.
  2. [2]Anders Björner, Shellable and Cohen-Macaulay partially ordered sets, Trans. Amer. Math. Soc. 260 (1980), no. 1, 159–183. MR 570784DOI
  3. [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. [4]Suyoung Choi and Younghan Yoon, The cohomology rings of real permutohedral varieties, 2023.arxiv.org/abs/2308.12693
  5. [5]——, A decomposition of graph a-numbers, Preprint, arXiv:2508.06855, 2025.arxiv.org/abs/2508.06855
  6. [6]——, Real toric manifolds associated with chordal nestohedra, Journal of Combinatorial Theory, Series A 217 (2026), 106102.DOI
  7. [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. [8]P. Erdős and A. H. Stone, On the structure of linear graphs, Bull. Amer. Math. Soc. 52 (1946), 1087–1091.
  9. [9]W. M. Marle, Problem 28, Wiskundige Opgaven 10 (1907), 60–61.
  10. [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. [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. [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. [13]M. Simonovits, On Paul Turán’s influence on graph theory, J. Graph Theory 1 (1977), no. 2, 102–116.DOI
  14. [14]Neil JA Sloane, The on-line encyclopedia of integer sequences, http://oeis.org.
  15. [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. [16]P. Turán, Eine extremalaufgabe aus der graphentheorie, Mat. Fiz. Lapok 48 (1941), 436–452.
  17. [17]Younghan Yoon, Cohomology of type B real permutohedral varieties, Bulletin of the London Mathematical Society 57 (2025), no. 9, 2770–2788.DOI
  18. [18]A. A. Zykov, On some properties of linear complexes, Mat. Sb. (N.S.) 24(66) (1949), no. 2, 163–188.

Paper details

vlnc:W_bkdavdbv
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents