betaFeedback

WorksMathematics

KrK_r-Packings in Graphs with tr−1(n)+kt_{r-1}(n)+k Edges

Abstract

Fix an integer r≥3r\ge 3. Let KrK_r denote the complete graph on rr vertices and tr−1(n)t_{r-1}(n) the Turán number for KrK_r. For each integer kk satisfying 0≤k≤(n2)−tr−1(n)0\le k \le \binom{n}{2}-t_{r-1}(n), \rev{ϕ_r(n,k)} denotes the minimum, over all nn-vertex graphs with tr−1(n)+kt_{r-1}(n)+k edges, of the maximum size of a KrK_r-packing \rev{(a family of edge-disjoint copies of KrK_r)} in the graph. The problem of characterizing the behavior of ϕr(n,k)ϕ_r(n,k) has a long history and dates back to Erdős for the case r=3r=3. \rev{Győri} proved that ϕr(n,k)=(1−o(1))kϕ_r(n,k)=(1-o(1))k whenever k=o(n2)k=o(n^2). We characterize the range of kk for which ϕr(n,k)=(1−o(1))kϕ_r(n,k)=(1-o(1))k, showing that this equality holds if and only if k=o(n2)k=o(n^2). Moreover, we obtain an \rev{asymptotic} upper bound (which falls below 11) for ϕr(n,k)/kϕ_r(n,k)/k whenever k/n2k/n^2 converges to a constant δδ satisfying 0<δ≤12(r−1)0 < δ\le \frac{1}{2(r-1)}.

Introduction

Throughout the paper, all graphs considered are finite and simple. For a graph GG, V(G)V(G) denotes its vertex set and E(G)E(G) its edge set. Let KrK_r be the complete graph on rr vertices. A KrK_r-packing of GG is a family of edge-disjoint copies of KrK_r in GG, and νr(G)\nu_r(G) denotes the maximum cardinality of such a family. Denote by tr−1(n)t_{r-1}(n) the number of edges of the Turán graph on nn vertices with r−1r-1 parts, which is the complete (r−1)(r-1)-partite graph whose partition classes have sizes differing by at most 1. Set e(G):=∣E(G)∣e(G) := |E(G)|. Define the function ϕr(n,k)=min⁡Gνr(G)\phi_r(n,k) = \min_G \nu_r(G), where the minimum is taken over all nn-vertex graphs GG satisfying e(G)=tr−1(n)+ke(G) = t_{r-1}(n) + k. By Turán’s Theorem, ϕr(n,0)=0\phi_r(n,0) = 0. The problem of characterizing the behavior of ϕr(n,k)\phi_r(n,k) for 0<k≤(n2)−tr−1(n)0 < k \le\binom{n}{2} - t_{r-1}(n) has a long history and dates back to Erdős for the case r=3r = 3 [2]. He proved that ϕ3(n,k)=k\phi_3(n,k) = k whenever 0<k<cn0 < k < cn, where c<1/2c < 1/2 is a constant. This result was subsequently refined by Győri [3, 5].

Theorem 1.1 (Győri, [3, 5]). For all sufficiently large nn, ϕ3(n,k)=k\phi_3(n,k) = k if k≤2n−10k \le2n - 10 for odd nn, or if k≤3n2−5k \le\frac{3n}{2} - 5 for even $n.

Examples in [5] show that the upper bounds for kk in Theorem 1.1 are sharp. The graph GG is KrK_r-free if it contains no copy of KrK_r. A very precise result of Győri and Keszegh [6] exhibits a much larger admissible range of kk with kk of order Θ(n2)\Theta(n^2) rather than linear in nn, for the guarantee of at least kk edge-disjoint triangles under the additional K4K_4-free constraint.

Theorem 1.2 (Győri and Keszegh, [6]). Any K4K_4-free graph on nn vertices with ⌊n2/4⌋+k\lfloor n^2/4\rfloor+k edges, where k≥0k\geq0 is an integer, contains at least kk pairwise edge-disjoint triangles.

Győri [3, 4] showed the following.

Theorem 1.3 (Győri, [3, 4]). Let r≥3r\geq3 be fixed. For all sufficiently large nn,

  • (i) If r≥4r\geq4, ϕr(n,k)=k\phi_r(n,k)=k whenever k≤3⌊n+1r−1⌋−5k\leq3\left\lfloor\frac{n+1}{r-1}\right\rfloor-5;

  • (ii) ϕr(n,k)=(1−o(1))k\phi_r(n,k)=(1-o(1))k whenever k=o(n2)k=o(n^2).

Balogh and Wigal [1] gave constructions for certain sequences k=Θ(n2)k=\Theta(n^2) for which ϕ3(n,k)≤(1−c)k\phi_3(n,k)\leq(1-c)k with a fixed c>0c>0. They also asked for the range of kk in which ϕr(n,k)=(1−o(1))k\phi_r(n,k)=(1-o(1))k. We answer this question by proving the equality holds if and only if k=o(n2)k=o(n^2).

Theorem 1.4. Fix an integer r≥3r\geq3, and let k=k(n)k=k(n) be a sequence of integers satisfying 1≤k≤(n2)−tr−1(n)1\leq k\leq\binom{n}{2}-t_{r-1}(n) for all sufficiently large nn. Then, as n→∞n\to\infty,

ϕr(n,k(n))=(1−o(1))k\phi_r(n,k(n))=(1-o(1))k if and only if k(n)=o(n2)k(n)=o(n^2).

By Wilson’s Theorem [7], applied to the complete graph KnK_n (i.e. k=(n2)−tr−1(n)k=\binom{n}{2}-t_{r-1}(n)), ϕr(n,k)=(2−o(1))kr\phi_r(n,k)=\frac{(2-o(1))k}{r}. Indeed, one may choose n′=n−Or(1)n'=n-O_r(1) satisfying Wilson’s divisibility conditions and decompose a copy of Kn′K_{n'} inside KnK_n. A result of Balogh and Wigal [1] implies that ϕr(n,k)≥(2−o(1))kr\phi_r(n,k)\geq\frac{(2-o(1))k}{r}, for all 0<k≤(n2)−tr−1(n)0<k\leq\binom{n}{2}-t_{r-1}(n). Our second result gives an explicit asymptotic upper bound for ϕr(n,k)/k\phi_r(n,k)/k, strictly smaller than 11, when kn2→δ\frac{k}{n^2}\to\delta.

Theorem 1.5. Fix an integer r≥3r\geq3, and let k=k(n)k=k(n) be a sequence of integers satisfying 1≤k≤(n2)−tr−1(n)1\leq k\leq\binom{n}{2}-t_{r-1}(n) for all sufficiently large nn. Let 0<δ≤12(r−1)0<\delta\leq\frac{1}{2(r-1)} be any real and set s:=1−1−2(r−1)δs:=1-\sqrt{1-2(r-1)\delta}. If kn2→δ\frac{k}{n^2}\to\delta, then

lim sup⁡n→∞ϕr(n,k)k≤1−s(r−2)r(2−s)<1.\limsup_{n\to\infty}\frac{\phi_r(n,k)}{k}\leq1-\frac{s(r-2)}{r(2-s)}<1.

Notation and Terminology

Throughout the paper, all asymptotic notation is understood as n→∞n\to\infty, where nn is the number of vertices and r≥3r\geq3 is a fixed integer (independent of nn). Let f(n)f(n) and g(n)g(n) be real-valued sequences with g(n)>0g(n)>0 for all sufficiently large nn. We write f(n)=o(g(n))f(n)=o(g(n)) if f(n)/g(n)→0f(n)/g(n)\to0 as n→∞n\to\infty; we write f(n)=O(g(n))f(n)=O(g(n)) if there exists a constant C>0C>0 such that ∣f(n)∣≤Cg(n)|f(n)|\leq Cg(n) for all sufficiently large nn; and we write f(n)=Θ(g(n))f(n)=\Theta(g(n)) if there exist positive constants cc and CC such that cg(n)≤f(n)≤Cg(n)cg(n)\leq f(n)\leq Cg(n) for all sufficiently large nn. All implied constants are allowed to depend on the fixed parameter rr (and on any other fixed parameters, such as ε\varepsilon), but not on nn. Whenever we wish to emphasize that the implied constant depends only on rr, we attach the subscript and write Or(⋅)O_r(\cdot), or(⋅)o_r(\cdot), or Θr(⋅)\Theta_r(\cdot); for instance, f(n)=Or(g(n))f(n)=O_r(g(n)) means that the constant CC above depends only on rr, and the bound holds uniformly for all nn sufficiently large.

For a graph GG, let V(G)V(G) be its vertex set and E(G)E(G) its edge set. For a vertex set S⊆V(G)S\subseteq V(G), G[S]G[S] denotes the subgraph of GG induced by SS. An independent set (or stable set) in a graph GG is a subset S⊆V(G)S\subseteq V(G) of vertices such that no two distinct vertices in SS are adjacent. The join G∨HG\vee H of two vertex-disjoint graphs GG and HH is the graph containing all edges of GG and $H, plus every edge between V(G)V(G) and V(H)V(H). More generally, for vertex-disjoint graphs XX and YY in a common ambient graph, we write E(X,Y)E(X,Y) for the set of edges with one endpoint in V(X)V(X) and the other in V(Y)V(Y); thus E(G∨H)=E(G)∪E(G,H)∪E(H)E(G\vee H)=E(G)\cup E(G,H)\cup E(H). A graph GG is KrK_r-free if it contains no copy of KrK_r. For positive integers rr and nn, the Turán graph Tr(n)T_r(n) is the complete rr-partite graph on nn vertices whose parts differ in size by at most one. Its size tr(n):=e(Tr(n))t_r(n):=e(T_r(n)) is the Turán number for Kr+1K_{r+1}, namely the maximum size of an nn-vertex Kr+1K_{r+1}-free graph.

A KrK_r-packing of GG is a family of edge-disjoint copies of KrK_r in GG, and νr(G)\nu_r(G) denotes the maximum cardinality of such a family. For an nn-vertex graph with tr−1(n)+kt_{r-1}(n)+k edges, the integer kk is its number of excess edges above tr−1(n)t_{r-1}(n). Note that 0≤k≤kn:=(n2)−tr−1(n)0\le k\le k_n:=\binom{n}{2}-t_{r-1}(n). Define

ϕr(n,k):=min⁡{νr(G):∣V(G)∣=n, e(G)=tr−1(n)+k}.(1)\phi_r(n,k):=\min\{\nu_r(G):|V(G)|=n,\ e(G)=t_{r-1}(n)+k\}. \tag*{(1)}

In other words, ϕr(n,k)\phi_r(n,k) is the minimum possible number of edge-disjoint copies of KrK_r in a maximum KrK_r-packing of an nn-vertex graph with exactly tr−1(n)+kt_{r-1}(n)+k edges. A graph attaining this minimum is called an extremal graph for ϕr(n,k)\phi_r(n,k). Let Kr(G)\mathcal{K}_r(G) denote the set of all copies of KrK_r in GG. The following definition is a fractional relaxation of KrK_r-packing.

Definition 2.1 (Fractional KrK_r-packing). A fractional KrK_r-packing of a graph GG is a function ω:Kr(G)→[0,1]\omega:\mathcal{K}_r(G)\to[0,1] such that for every e∈E(G)e\in E(G),

∑H∈Kr(G)e∈E(H)ω(H)≤1.\sum_{\substack{H\in\mathcal{K}_r(G)\\e\in E(H)}}\omega(H)\le1.

The weight of ω\omega is ∣ω∣=∑H∈Kr(G)ω(H)|\omega|=\sum_{H\in\mathcal{K}_r(G)}\omega(H). The fractional KrK_r-packing number of GG, denoted by νr∗(G)\nu_r^*(G), is the maximum weight of a fractional KrK_r-packing of GG.

Every KrK_r-packing can be viewed as a fractional KrK_r-packing whose weights are restricted to {0,1}\{0,1\}. Consequently,

νr(G)≤νr∗(G).\nu_r(G)\le\nu_r^*(G).

A closely related notion is that of a KrK_r-cover. A KrK_r-cover of GG is a set of edges that intersects every copy of KrK_r in GG, and τr(G)\tau_r(G) denotes the minimum cardinality of a KrK_r-cover of GG. There is also a fractional relaxation of this notion.

Definition 2.2 (Fractional KrK_r-cover). A fractional KrK_r-cover of a graph GG is a function φ:E(G)→[0,1]\varphi:E(G)\to[0,1] such that for every H∈Kr(G)H\in\mathcal{K}_r(G),

∑e∈E(H)φ(e)≥1.\sum_{e\in E(H)}\varphi(e)\ge1.

The weight of φ\varphi is defined as ∣φ∣=∑e∈E(G)φ(e)|\varphi|=\sum_{e\in E(G)}\varphi(e), and the fractional KrK_r-covering number of GG, denoted by τr∗(G)\tau_r^*(G), is the minimum weight of a fractional KrK_r-cover of GG.

A KrK_r-cover of GG can be identified with a fractional KrK_r-cover taking values in {0,1}\{0,1\}. Consequently,

τr∗(G)≤τr(G).\tau_r^*(G)\le\tau_r(G).

By strong duality in linear programming, the fractional KrK_r-packing number equals the fractional KrK_r-covering number. Therefore,

νr(G)≤νr∗(G)=τr∗(G)≤τr(G).(2)\nu_r(G)\le\nu_r^*(G)=\tau_r^*(G)\le\tau_r(G). \tag*{(2)}

A construction and its fractional cover

To prove the necessity of Theorem 1.4, we construct a family of graphs equipped with explicit fractional KrK_r-covers whose weights are substantially smaller than their numbers of excess edges over the Turán number for KrK_r. This construction also yields asymptotic upper bounds for ϕr(n,k)\phi_r(n,k) when k=Θ(n2)k=\Theta(n^2).

The Constructions

Given integers a∈{0,1,…,n}a\in\{0,1,\ldots,n\} and r≥3r\ge3, let

Ga=Ka∨Tr−1(n−a)(3)G_a=K_a\vee T_{r-1}(n-a) \tag*{(3)}

denote the join of the complete graph KaK_a and the Turán graph Tr−1(n−a)T_{r-1}(n-a). Let

ka≔e(Ga)−tr−1(n)(4)k_a\coloneqq e(G_a)-t_{r-1}(n) \tag*{(4)}

be the number of edges of GaG_a in excess of the Turán number tr−1(n)t_{r-1}(n) for KrK_r. Observe that G0=Tr−1(n)G_0=T_{r-1}(n) and Gn=KnG_n=K_n, whence k0=0k_0=0 and kn=(n2)−tr−1(n)k_n=\binom{n}{2}-t_{r-1}(n). We shall establish an exact formula for kak_a in the following subsection, which in particular shows that kak_a is monotone non-decreasing in aa. Consequently, k0=0k_0=0 and kn=(n2)−tr−1(n)k_n=\binom{n}{2}-t_{r-1}(n) are precisely the two boundary values for the range of kk.

Next, we assign weights to the edges of GaG_a to obtain a fractional cover. For an edge e∈E(Ga)e\in E(G_a), define

wa(e)≔{2r(r−1),if e∈E(Ka),1r−1,if e∈E(Ka,Tr−1(n−a)),0,if e∈E(Tr−1(n−a)).(5)w_a(e)\coloneqq \begin{cases} \frac{2}{r(r-1)}, & \text{if }e\in E(K_a),\\ \frac{1}{r-1}, & \text{if }e\in E(K_a,T_{r-1}(n-a)),\\ 0, & \text{if }e\in E(T_{r-1}(n-a)). \end{cases} \tag*{(5)}

Write Wa≔∣wa∣=∑e∈E(Ga)wa(e)W_a\coloneqq\lvert w_a\rvert=\sum_{e\in E(G_a)}w_a(e) for its total weight. We will show in the next subsection that waw_a is indeed a fractional KrK_r-cover of GaG_a; that is, every copy CC of KrK_r in GaG_a satisfies ∑e∈E(C)wa(e)≥1\sum_{e\in E(C)}w_a(e)\ge1.

Edge counts and cover weights

First we give an exact expression for kak_a showing that kak_a is monotone in aa. Thus the excess edge number kak_a satisfying 0=k0≤ka≤kn=(n2)−tr−1(n)0=k_0\le k_a\le k_n=\binom{n}{2}-t_{r-1}(n) falls exactly within our target range of kk. Before stating the lemma, we introduce notation to control rounding effects on the part sizes of Turán graphs. For each integer m≥0m\ge0, write m=(r−1)ℓ+ρmm=(r-1)\ell+\rho_m, where ℓ\ell and ρm\rho_m are integers with ℓ≥0\ell\ge0 and 0≤ρm<r−10\le\rho_m<r-1. Let

ηr−1(m)≔ρm((r−1)−ρm)2(r−1).\eta_{r-1}(m)\coloneqq\frac{\rho_m((r-1)-\rho_m)}{2(r-1)}.

Recall that the Turán graph Tr−1(m)T_{r-1}(m) has ρm\rho_m parts of size ℓ+1\ell+1 and (r−1)−ρm(r-1)-\rho_m parts of size ℓ\ell. Counting the edges between different parts yields the exact formula

tr−1(m)=r−22(r−1)m2−ηr−1(m),0≤ηr−1(m)≤r−18.(6)t_{r-1}(m)=\frac{r-2}{2(r-1)}m^2-\eta_{r-1}(m),\qquad0\le\eta_{r-1}(m)\le\frac{r-1}{8}. \tag*{(6)}

This upper bound for ηr−1(m)\eta_{r-1}(m) is a consequence of ρm((r−1)−ρm)≤(r−1)2/4\rho_m((r-1)-\rho_m)\le(r-1)^2/4.

Lemma 3.1. Let r≥3r \ge3 be a fixed integer. Then the following hold.

(i) For every integer aa with 0≤a≤n0 \le a \le n,

ka=a(2n−a)2(r−1)−a2+ηr−1(n)−ηr−1(n−a)≤anr−1+r−18.k_a = \frac{a(2n-a)}{2(r-1)}-\frac{a}{2}+\eta_{r-1}(n)-\eta_{r-1}(n-a) \le\frac{an}{r-1}+\frac{r-1}{8}.

(ii) For 0≤a<n0 \le a<n,

ka+1−ka=⌈n−ar−1⌉−1.k_{a+1}-k_a=\left\lceil\frac{n-a}{r-1}\right\rceil-1.

In particular, 0=k0≤k1≤⋯≤kn0=k_0\le k_1\le\cdots\le k_n, and ka+1−ka=Or(n)k_{a+1}-k_a=O_r(n).

Proof. By (3), the edge set of GaG_a admits the disjoint decomposition

E(Ga)=E(Ka)∪E(Ka,Tr−1(n−a))∪E(Tr−1(n−a)).E(G_a)=E(K_a)\cup E(K_a,T_{r-1}(n-a))\cup E(T_{r-1}(n-a)).

Consequently,

e(Ga)=(a2)+a(n−a)+tr−1(n−a).e(G_a)=\binom{a}{2}+a(n-a)+t_{r-1}(n-a).

Recall from (4) that ka=e(Ga)−tr−1(n)k_a=e(G_a)-t_{r-1}(n). Subtracting tr−1(n)t_{r-1}(n) from the expression for e(Ga)e(G_a) above and invoking (6), we obtain

ka=a(a−1)2+a(n−a)+r−22(r−1)((n−a)2−n2)+ηr−1(n)−ηr−1(n−a)=a(2n−a)2(r−1)−a2+ηr−1(n)−ηr−1(n−a)=anr−1−a22(r−1)−a2+ηr−1(n)−ηr−1(n−a)≤anr−1+ηr−1(n)−ηr−1(n−a)≤anr−1+r−18,by (6).\begin{aligned} k_a&=\frac{a(a-1)}{2}+a(n-a)+\frac{r-2}{2(r-1)}\left((n-a)^2-n^2\right)+\eta_{r-1}(n)-\eta_{r-1}(n-a)\\ &=\frac{a(2n-a)}{2(r-1)}-\frac{a}{2}+\eta_{r-1}(n)-\eta_{r-1}(n-a)\\ &=\frac{an}{r-1}-\frac{a^2}{2(r-1)}-\frac{a}{2}+\eta_{r-1}(n)-\eta_{r-1}(n-a)\\ &\le\frac{an}{r-1}+\eta_{r-1}(n)-\eta_{r-1}(n-a)\\ &\le\frac{an}{r-1}+\frac{r-1}{8},\qquad\text{by }(6). \end{aligned}

which establishes (i).

It remains to prove (ii). Put m:=n−a≥1m:=n-a\ge1. To pass from GaG_a to Ga+1G_{a+1}, take a vertex vv of Tr−1(m)T_{r-1}(m) lying in a part of maximum size and move it into the clique KaK_a, turning the join into Ka+1∨Tr−1(m−1)K_{a+1}\vee T_{r-1}(m-1). Removing vv from that maximum part leaves a copy of Tr−1(m−1)T_{r-1}(m-1) and affects no edge outside vv; hence only the edges incident to vv change. In GaG_a, the vertex vv is adjacent to the aa vertices of KaK_a and to the m−⌈m/(r−1)⌉m-\left\lceil m/(r-1)\right\rceil vertices of Tr−1(m)T_{r-1}(m) outside its own part; in Ga+1G_{a+1}, it is adjacent to the aa vertices of the original clique and to all m−1m-1 vertices of Tr−1(m−1)T_{r-1}(m-1). Its degree therefore changes by (m−1)−(m−⌈m/(r−1)⌉)(m-1)-(m-\lceil m/(r-1)\rceil), and since the fixed constant tr−1(n)t_{r-1}(n) is subtracted from both e(Ga)e(G_a) and e(Ga+1)e(G_{a+1}), we obtain

ka+1−ka=(m−1)−(m−⌈mr−1⌉)=⌈mr−1⌉−1,k_{a+1}-k_a=(m-1)-\left(m-\left\lceil\frac{m}{r-1}\right\rceil\right)=\left\lceil\frac{m}{r-1}\right\rceil-1,

which proves (ii). Since 1≤m≤n1\le m\le n, each increment lies in [0,⌈n/(r−1)⌉−1][0,\lceil n/(r-1)\rceil-1], so kak_a is non-decreasing in aa, and consecutive distinct values of kak_a differ by Or(n)O_r(n).

We proceed by proving that the function waw_a defined by (5) in the preceding subsection is in fact a fractional KrK_r-cover of GaG_a; its total weight is also determined simultaneously.

Lemma 3.2. The function waw_a is a fractional KrK_r-cover of GaG_a, and

Wa=2r(r−1)(a2)+a(n−a)r−1=anr−1−a2r−ar(r−1).W_a = \frac{2}{r(r-1)}\binom{a}{2}+\frac{a(n-a)}{r-1}=\frac{an}{r-1}-\frac{a^2}{r}-\frac{a}{r(r-1)}.

Proof. Let QQ be an arbitrary copy of KrK_r in GaG_a, where Ga=Ka∨Tr−1(n−a)G_a=K_a\vee T_{r-1}(n-a) by (3). Set j:=∣V(Q)∩V(Ka)∣j:=|V(Q)\cap V(K_a)|. Since the subgraph induced by V(Ga)∖V(Ka)V(G_a)\setminus V(K_a) is Tr−1(n−a)T_{r-1}(n-a), which is KrK_r-free, every KrK_r-copy must intersect V(Ka)V(K_a). So 1≤j≤r1\le j\le r. The edges of QQ with positive weight are of two types: the (j2)\binom{j}{2} edges induced by V(Q)∩V(Ka)V(Q)\cap V(K_a) each carrying weight 2r(r−1)\frac{2}{r(r-1)} by (5), and the j(r−j)j(r-j) edges between KaK_a and Tr−1(n−a)T_{r-1}(n-a) each carrying weight 1r−1\frac{1}{r-1} by (5); all other edges are assigned weight zero. Thus

∑e∈E(Q)wa(e)=2r(r−1)(j2)+j(r−j)r−1\sum_{e\in E(Q)}w_a(e)=\frac{2}{r(r-1)}\binom{j}{2}+\frac{j(r-j)}{r-1}
=j(r+1−j)r=\frac{j(r+1-j)}{r}
=1+(j−1)(r−j)r=1+\frac{(j-1)(r-j)}{r}
≥1.\ge1.

The inequality holds because both (j−1)(j-1) and (r−j)(r-j) are nonnegative for 1≤j≤r1\le j\le r. Therefore, by Definition 2.2, waw_a is a fractional KrK_r-cover of GaG_a. The first part of the lemma follows.

We next calculate the total weight of waw_a. Counting the (a2)\binom{a}{2} edges inside KaK_a each of weight 2r(r−1)\frac{2}{r(r-1)} by (5) and the a(n−a)a(n-a) edges between KaK_a and Tr−1(n−a)T_{r-1}(n-a) each of weight 1r−1\frac{1}{r-1} by (5), we obtain

Wa=a(a−1)r(r−1)+a(n−a)r−1=anr−1−a2r−ar(r−1),W_a=\frac{a(a-1)}{r(r-1)}+\frac{a(n-a)}{r-1}=\frac{an}{r-1}-\frac{a^2}{r}-\frac{a}{r(r-1)},

which establishes the lemma.

Let Da:=ka−WaD_a:=k_a-W_a be the difference of the excess edge number and the total cover weight. By Definition 2.2, τr∗(Ga)≤∣wa∣=Wa\tau_r^*(G_a)\le|w_a|=W_a. Combined with (2), this implies

νr(Ga)≤τr∗(Ga)≤Wa=ka−Da.(7)\nu_r(G_a)\le\tau_r^*(G_a)\le W_a=k_a-D_a. \tag*{(7)}

Now we bound DaD_a from below to obtain an upper bound on νr(Ga)\nu_r(G_a).

Lemma 3.3. For every integer aa with 0≤a≤n0\le a\le n, we have

Da=r−22r(r−1)a2−Or(a+1).D_a=\frac{r-2}{2r(r-1)}a^2-O_r(a+1).

Proof. By Lemma 3.1-(i) and Lemma 3.2,

Da=(a(2n−a)2(r−1)−a2+ηr−1(n)−ηr−1(n−a))−(anr−1−a2r−ar(r−1))=(1r−12(r−1))a2−(12−1r(r−1))a+ηr−1(n)−ηr−1(n−a)=r−22r(r−1)a2−Or(a+1).\begin{aligned} D_a=\left(\frac{a(2n-a)}{2(r-1)}-\frac{a}{2}+\eta_{r-1}(n)-\eta_{r-1}(n-a)\right)-\left(\frac{an}{r-1}-\frac{a^2}{r}-\frac{a}{r(r-1)}\right) \\ &=\left(\frac{1}{r}-\frac{1}{2(r-1)}\right)a^2-\left(\frac{1}{2}-\frac{1}{r(r-1)}\right)a+\eta_{r-1}(n)-\eta_{r-1}(n-a) \\ &=\frac{r-2}{2r(r-1)}a^2-O_r(a+1). \end{aligned}

:::

The last equality is justified as follows: By (6), the difference ηr−1(n)−ηr−1(n−a)\eta_{r-1}(n)-\eta_{r-1}(n-a) is bounded in absolute value by (r−1)/8(r-1)/8; the linear term in aa is Or(a)O_r(a). As rr is fixed, each of these is Or(a+1)O_r(a+1), so the non-quadratic terms are Or(a+1)O_r(a+1) as claimed.

When aa is a positive fraction of nn, the quadratic term in the formula of Lemma 3.3 is of order n2n^2. Although by construction kak_a satisfies 0≤ka≤(n2)−tr−1(n)0 \leq k_a \leq\binom{n}{2}-t_{r-1}(n), it may skip certain integers and hence need not take all the admissible values. To ensure that every admissible integer is attained, we add edges to GaG_a, assigning weight 11 to each new edge. Each addition increases the excess edge count and the cover weight by the same amount, so the difference ka−Wa=Dak_a-W_a=D_a is preserved. Every integer in the admissible range is thus realized.

Lemma 3.4. For every integer kk with 0≤k≤(n2)−tr−1(n)0 \leq k \leq\binom{n}{2}-t_{r-1}(n), there exist an integer a∈{0,1,…,n}a \in\{0,1,\ldots,n\} and an nn-vertex graph HH such that

e(H)=tr−1(n)+kandνr(H)≤k−Da,e(H)=t_{r-1}(n)+k \quad\text{and}\quad\nu_r(H)\leq k-D_a,

where ka≤k<ka+1k_a \leq k < k_{a+1} if a<na<n, and k=knk=k_n if a=na=n.

Proof. If k=knk=k_n, take a=na=n and H=Gn=KnH=G_n=K_n. Lemma 3.2 together with (7) then yields νr(H)≤Wn=k−Dn\nu_r(H)\leq W_n=k-D_n, as required. Suppose now that k<knk<k_n, and choose aa maximal subject to ka≤kk_a\leq k. Since k0=0≤k<knk_0=0\leq k<k_n, such an index aa exists and satisfies 0≤a<n0\leq a<n. Maximality of aa indicates that k<ka+1k<k_{a+1}. Let d:=k−kad:=k-k_a. By Lemma 3.1-(ii)

0≤d<ka+1−ka=⌈n−ar−1⌉−1.0\leq d<k_{a+1}-k_a=\left\lceil\frac{n-a}{r-1}\right\rceil-1.

We construct HH from GaG_a by adding dd edges. First note that the number of non-edges of GaG_a is

(n2)−e(Ga)=kn−ka≥k−ka=d,\binom{n}{2}-e(G_a)=k_n-k_a\geq k-k_a=d,

so GaG_a contains sufficiently many missing edges for the required adjustment. Since e(Ga)=tr−1(n)+kae(G_a)=t_{r-1}(n)+k_a and d=k−kad=k-k_a, we have

e(H)=e(Ga)+d=tr−1(n)+k.e(H)=e(G_a)+d=t_{r-1}(n)+k.

Finally, we extend waw_a to E(H)E(H) by retaining the weights on E(Ga)E(G_a) and assigning unit weight to each added edge. To verify that the resulting weighting is a fractional KrK_r-cover, let QQ be an arbitrary copy of KrK_r in HH. If QQ contains an added edge, then that edge alone carries weight 11. Otherwise every edge of QQ lies in GaG_a, and its total weight is at least 11 by Lemma 3.2. The extended weighting is therefore a fractional KrK_r-cover of total weight Wa+dW_a+d. By Definition 2.2 and (2),

νr(H)≤Wa+d=Wa+(k−ka)=k−Da,\nu_r(H)\leq W_a+d=W_a+(k-k_a)=k-D_a,

which completes the proof of this lemma.

Now we are ready to prove our main theorems.

Proof of Theorem 1.4

The sufficiency of Theorem 1.4 follows from Theorem 1.3-(ii). It remains to prove the necessity of the theorem. We argue by contradiction. Let 1≤k≤(n2)−tr−1(n)1 \le k \le\binom{n}{2} - t_{r-1}(n) and nn sufficiently large. Suppose that ϕr(n,k)=(1−o(1))k\phi_r(n,k) = (1-o(1))k and k≠o(n2)k \ne o(n^2). Since kk is not o(n2)o(n^2), there exist a constant ε>0\varepsilon> 0 and an infinite subsequence k=k(n)k = k(n) such that k≥εn2k \ge\varepsilon n^2. By decreasing ε\varepsilon if necessary, we may assume that ε≤12(r−1)\varepsilon\le\frac{1}{2(r-1)}. For each such k=k(n)k = k(n), apply Lemma 3.4, there exist an integer a∈{0,…,n}a \in\{0,\ldots,n\} and an nn-vertex graph HH such that

e(H)=tr−1(n)+k,νr(H)≤k−Da,ka≤k<ka+1 or k=kn.e(H) = t_{r-1}(n) + k,\qquad\nu_r(H) \le k-D_a,\qquad k_a \le k < k_{a+1}\ \text{or}\ k=k_n.

By Lemma 3.3, Da=r−22r(r−1)a2−Or(a+1)D_a = \frac{r-2}{2r(r-1)}a^2-O_r(a+1). So

νr(H)≤k−Da=k−r−22r(r−1)a2+Or(a+1).\nu_r(H) \le k-D_a = k-\frac{r-2}{2r(r-1)}a^2+O_r(a+1).

Now we prove that aa is bounded below by a positive multiple of nn. If ka≤k<ka+1k_a \le k < k_{a+1}, by Lemma 3.1-(i)

εn2≤k<ka+1≤(a+1)nr−1+r−18.\varepsilon n^2 \le k < k_{a+1} \le\frac{(a+1)n}{r-1}+\frac{r-1}{8}.

Solving the above inequality yields a>(r−1)εn−1−(r−1)28εna>(r-1)\varepsilon n-1-\frac{(r-1)^2}{8\varepsilon n}, and hence, for all sufficiently large nn,

a≥(r−1)ε2n.a \ge\frac{(r-1)\varepsilon}{2}n.

If k=knk=k_n, then by Lemma 3.4, a=n≥(r−1)ε2na=n\ge\frac{(r-1)\varepsilon}{2}n, as (r−1)ε2≤14\frac{(r-1)\varepsilon}{2}\le\frac14. In either case, we have

(r−1)ε2n≤a≤n,\frac{(r-1)\varepsilon}{2}n\le a\le n,

for all sufficiently large nn. Therefore,

νr(H)≤k−Da=k−r−22r(r−1)a2+Or(a+1)≤k−(r−2)(r−1)8r(εn)2+Or(a+1)≤k−(r−2)(r−1)16r(εn)2.\begin{aligned} \nu_r(H)&\le k-D_a=k-\frac{r-2}{2r(r-1)}a^2+O_r(a+1)\\ &\le k-\frac{(r-2)(r-1)}{8r}(\varepsilon n)^2+O_r(a+1)\\ &\le k-\frac{(r-2)(r-1)}{16r}(\varepsilon n)^2. \end{aligned}

In the last inequality, a≤na\le n and sufficiently large nn allow the Or(a+1)O_r(a+1) error to be absorbed into half of the quadratic term. Since k≤(n2)−tr−1(n)<n2/2k\le\binom{n}{2}-t_{r-1}(n)<n^2/2, we have

νr(H)≤k−(r−2)(r−1)16r2kε2=k−(r−2)(r−1)8rkε2=(1−(r−2)(r−1)8rε2)k.\begin{aligned} \nu_r(H)\le k-\frac{(r-2)(r-1)}{16r}2k\varepsilon^2 \\ &= k-\frac{(r-2)(r-1)}{8r}k\varepsilon^2 \\ &=\left(1-\frac{(r-2)(r-1)}{8r}\varepsilon^2\right)k. \end{aligned}

By (1), we know that ϕr(n,k)≤νr(H)≤(1−(r−2)(r−1)8rε2)k\phi_r(n,k)\le\nu_r(H)\le\left(1-\frac{(r-2)(r-1)}{8r}\varepsilon^2\right)k. Thus the ratio ϕr(n,k)/k\phi_r(n,k)/k is bounded above by a constant strictly smaller than 11 along this subsequence, a contradiction. This finishes our proof of Theorem 1.4.

Proof of Theorem 1.5

Suppose that kn2\frac{k}{n^2} tends to δ\delta, when nn tends to infinity. By Lemma 3.4, for each kk, there exist an integer a∈{0,…,n}a \in\{0,\ldots,n\} and an nn-vertex graph HH such that

e(H)=tr−1(n)+k,νr(H)≤k−Da,ka≤k<ka+1 or k=kn.e(H)=t_{r-1}(n)+k,\qquad\nu_r(H)\leq k-D_a,\qquad k_a\leq k<k_{a+1}\text{ or }k=k_n.

Put sn:=a/ns_n:=a/n, so that 0≤sn≤10\leq s_n\leq1. If a<na<n, Lemma 3.1-(ii) gives 0≤k−ka<ka+1−ka=Or(n)0\leq k-k_a<k_{a+1}-k_a=O_r(n); if a=na=n, then k=kak=k_a. Hence k−ka=Or(n)k-k_a=O_r(n) in both cases, and ka/n2→δk_a/n^2\to\delta. By Lemma 3.1-(i) and (6),

kan2=sn(2−sn)2(r−1)+Or(1/n).\frac{k_a}{n^2}=\frac{s_n(2-s_n)}{2(r-1)}+O_r(1/n).

Since 0≤sn≤10\leq s_n\leq1, it follows that

sn=1−1−sn(2−sn)⟶1−1−2(r−1)δ=s.s_n=1-\sqrt{1-s_n(2-s_n)}\longrightarrow1-\sqrt{1-2(r-1)\delta}=s.

In particular, δ=s(2−s)/(2(r−1))\delta=s(2-s)/(2(r-1)).

Lemma 3.3 indicates that Da=r−22r(r−1)a2−Or(a+1)D_a=\frac{r-2}{2r(r-1)}a^2-O_r(a+1). By (1),

ϕr(n,k)≤νr(H)≤k−Da=k−r−22r(r−1)a2+Or(a+1)=k−r−22r(r−1)(snn)2+Or(a+1).\begin{aligned} \phi_r(n,k)&\leq\nu_r(H)\\ &\leq k-D_a\\ &=k-\frac{r-2}{2r(r-1)}a^2+O_r(a+1)\\ &=k-\frac{r-2}{2r(r-1)}(s_n n)^2+O_r(a+1). \end{aligned}

Since a≤na\leq n and k/n2→δ>0k/n^2\to\delta>0, we have Or((a+1)/k)=o(1)O_r((a+1)/k)=o(1). Thus

ϕr(n,k)k≤1−r−22r(r−1)sn2n2k+o(1).\frac{\phi_r(n,k)}{k}\leq1-\frac{r-2}{2r(r-1)}s_n^2\frac{n^2}{k}+o(1).

Therefore,

lim sup⁡n→∞ϕr(n,k)k≤lim⁡n→∞(1−r−22r(r−1)sn2n2k)=1−r−22r(r−1)s2δ=1−s(r−2)r(2−s)<1.\begin{aligned} \limsup_{n\to\infty}\frac{\phi_r(n,k)}{k} &\leq\lim_{n\to\infty}\left(1-\frac{r-2}{2r(r-1)}s_n^2\frac{n^2}{k}\right)\\ &=1-\frac{r-2}{2r(r-1)}\frac{s^2}{\delta}\\ &=1-\frac{s(r-2)}{r(2-s)}\\ &<1. \end{aligned}

The last inequality follows from r≥3r\geq3 and 0<s≤10<s\leq1.

Acknowledgments

Fuhong Ma is supported by the National Natural Science Foundation of China (Grant number 12401458) and Natural Science Foundation of Shandong Province (Grant number ZR2024QA239). Jin Yan is supported by the National Natural Science Foundation of China (Grant number 12571373) and Natural Science Foundation of Shandong Province (Grant number ZR2025MS05).

Declaration on the use of AI

During the early stages of this research, the authors constructed the counterexample graph Ga=Ka∨Tr−1(n−a)G_a = K_a \vee T_{r-1}(n-a) and obtained computational evidence supporting the main theorem, but had not yet found a rigorous mathematical proof. In subsequent discussions with AI, GPT-6 Astra suggested an approach based on assigning weights to edges. The authors adopted this suggestion and developed it further, ultimately obtaining the rigorous mathematical proof presented in this manuscript. AI models also assisted with proof checking, proofreading, and language editing. The authors take full responsibility for all AI-assisted work and for the content of the manuscript.

References

  1. [1]J. Balogh and M. C. Wigal, Packing edge disjoint cliques in graphs, Combinatorica 45 (2025), no. 5, Paper No. 56.arxiv.org/abs/2502.16683
  2. [2]P. Erdős, Some unsolved problems in graph theory and combinatorial analysis, in: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), Academic Press, London–New York, 1971, pp. 97–109.
  3. [3]E. Győri, On the number of edge disjoint triangles in graphs of given size, in: Combinatorics (Eger, 1987), Colloq. Math. Soc. János Bolyai, vol. 52, North-Holland, Amsterdam, 1988, pp. 267–276.
  4. [4]E. Győri, On the number of edge disjoint cliques in graphs of given size, Combinatorica 11 (1991), 231–243.DOI
  5. [5]E. Győri, Edge disjoint cliques in graphs, in: Sets, Graphs, and Numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, vol. 60, North-Holland, Amsterdam, 1992, pp. 357–363.
  6. [6]E. Győri and B. Keszegh, On the number of edge-disjoint triangles in K₄-free graphs, Combinatorica 37 (2017), 1113–1124.
  7. [7]R. M. Wilson, Decomposition of complete graphs into subgraphs isomorphic to a given graph, in: Proceedings of the Fifth British Combinatorial Conference, Congr. Numer. XV, Utilitas Math., Winnipeg, 1976, pp. 647–659.

Paper details

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

views · 10

downloads · 0

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

  • Mathematics

GPT-6 Astra (bare)

View statement
Looking for related papers…
Contents