betaFeedback

WorksMathematics

Extremal graphs for Alon's graph coupon-collector conjecture

Abstract

Let GG be a finite simple graph without isolated vertices. Starting with every vertex uncovered, at each step sample a vertex uniformly and independently and cover one of its uncovered neighbors, chosen uniformly, if any. Let \cc(G) denote the expected number of steps required to cover all vertices. Alon conjectured that disjoint unions of Kd+1K_{d+1} maximize \cc(G) among dd-regular graphs of a prescribed order whenever such unions exist. In this paper, we disprove this conjecture for every fixed d≥2d\ge2 and give a complete characterization of the extremal graphs for d=2d=2 at every order n≥3n\ge3. In particular, all but at most six vertices of any such extremal graph lie in four-cycle components.

Introduction

The classical coupon-collector problem asks how many independent random samples are needed to collect every coupon type. Alon [2] considered the following graph version. On a finite simple graph GG without isolated vertices, all vertices are initially uncovered. At each step, a vertex is sampled uniformly and independently of the previous samples. If it has uncovered neighbors, one of them is chosen uniformly and covered; otherwise the covered set remains unchanged. The sampled vertex may itself be covered or uncovered. Let cc⁡(G)\operatorname{cc}(G) denote the expected number of steps until all vertices are covered, and write mFmF for the disjoint union of mm copies of FF. Alon conjectured that, among regular graphs of prescribed order and degree, this expectation is maximized by disjoint unions of cliques.

Conjecture (Alon [2], Section 6, Remark 3). Let d,nd,n be positive integers such that d+1d+1 divides nn. For every finite simple dd-regular graph GG on nn vertices,

cc⁡(G)≤cc⁡(nd+1Kd+1).\operatorname{cc}(G) \le\operatorname{cc}\left(\frac{n}{d+1}K_{d+1}\right).

Adler, Halperin, Karp, and Vazirani [1] established linear cover time for the hypercube, while Alon [2] proved a general lower bound and upper bounds for expanders. Dimitrov and Plaxton [5] obtained cover-time bounds of the correct order for related processes in which neighbors are selected using random vertex ranks. For further background on coupon collection, see the survey of Boneh and Hofri [3] and the references therein.

In this paper, we disprove Alon’s conjecture in every fixed degree at least two. In degree two, we determine all graphs maximizing cc⁡(G)\operatorname{cc}(G) at each prescribed order; the smallest counterexample has nine vertices. The complete extremal characterization is given by the following theorem.

Theorem 1.1. For n≥3n \ge3, define

Gn⋆={n4C4,n≡0(mod4),C5⊔n−54C4,n≡1(mod4),C6⊔n−64C4,n≡2(mod4),C3⊔n−34C4,n≡3(mod4),G_n^\star= \begin{cases} \frac{n}{4}C_4, & n \equiv0 \pmod{4},\\ C_5 \sqcup\frac{n-5}{4}C_4, & n \equiv1 \pmod{4},\\ C_6 \sqcup\frac{n-6}{4}C_4, & n \equiv2 \pmod{4},\\ C_3 \sqcup\frac{n-3}{4}C_4, & n \equiv3 \pmod{4}, \end{cases}

where ⊔\sqcup denotes disjoint union. For every finite simple 2-regular graph GG on nn vertices,

cc⁡(G)≤cc⁡(Gn⋆).(1)\operatorname{cc}(G) \le\operatorname{cc}(G_n^\star). \tag*{(1)}

Equality holds precisely when G≅Gn⋆G \cong G_n^\star, or when n≡2(mod4)n \equiv2 \pmod{4} and

G≅2C3⊔n−64C4.G \cong2C_3 \sqcup\frac{n-6}{4}C_4.

Moreover, let THT_H be the completion time of the same covering process on a graph HH, with each vertex sampled at the rings of an independent rate-1 Poisson clock. Then

P(TG≤t)≥P(TGn⋆≤t)(t>0),(2)\mathbb{P}(T_G \le t) \ge\mathbb{P}(T_{G_n^\star} \le t) \qquad(t > 0), \tag*{(2)}

with equality at any positive tt for exactly the same graphs.

For fixed degree d≥2d \ge2 and a fixed bound of at least 2d2d on component order, unions of Kd,dK_{d,d} uniquely maximize cc⁡(G)\operatorname{cc}(G) at all sufficiently large orders divisible by 2d2d. The results for general degree also identify the neighborhood structure governing the completion-time tail and disprove the uniform additive estimate suggested alongside Alon’s conjecture.

Preliminaries and component distributions

Let NGN_G be the number of discrete steps required to cover GG, so that cc⁡(G)=ENG\operatorname{cc}(G) = \mathbb{E}N_G. This uniform neighbor-selection rule is called process UNI in [5]. Give each vertex an independent Poisson clock of rate 1, and apply the same covering rule whenever its clock rings. Let TGT_G denote the completion time of this continuous-time process. We write Exp⁡(a)\operatorname{Exp}(a) for an exponential random variable of rate aa. All logarithms are natural. We use standard facts about Poisson clocks and finite-state continuous-time Markov chains; see [6 Sections 2.1, 2.2, 2.4, 4.1, and 4.2]. The tail-integral and exponential-distribution identities below can be found in [6 Section 2.1 and Appendix A.3].

Lemma 2.1. Let independent Poisson clocks have rates λ1,…,λs>0\lambda_1,\ldots,\lambda_s > 0, and put Λ=∑i=1sλi\Lambda= \sum_{i=1}^{s}\lambda_i. Their superposition has rate Λ\Lambda. Its labels are independent, with probabilities λi/Λ\lambda_i/\Lambda, and independent of the interarrival times. After an almost surely finite stopping time, the clocks restart independently with the same rates, independently of the past.

Lemma 2.2. Finite-state continuous-time Markov chains with the same generator and initial distribution have the same law. At a nonabsorbing state, the holding time is exponential with the total transition rate and independent of the next state.

Lemma 2.3. For a nonnegative random variable TT,

ET=∫0∞P(T>t) dt.(3)\mathbb{E}T = \int_{0}^{\infty} \mathbb{P}(T > t)\,\mathrm{d}t. \tag*{(3)}

If X1,…,XkX_1,\ldots,X_k are independent Exp⁡(λ)\operatorname{Exp}(\lambda) variables, where k≥1k \ge1 and λ>0\lambda> 0, then

P(X1+⋯+Xk>t)=e−λt∑j=0k−1(λt)jj!(t≥0).\mathbb{P}(X_1+\cdots+X_k>t)=e^{-\lambda t}\sum_{j=0}^{k-1}\frac{(\lambda t)^j}{j!}\qquad(t\ge0).

and

Emax⁡1≤i≤kXi=Hkλ,Hk=∑j=1k1j.\mathbb{E}\max_{1\le i\le k}X_i=\frac{H_k}{\lambda},\qquad H_k=\sum_{j=1}^{k}\frac{1}{j}.

The last identity follows from the memoryless property: the successive order-statistic spacings have rates kλ,(k−1)λ,…,λk\lambda,(k-1)\lambda,\ldots,\lambda.

Lemma 2.4. If GG has nn vertices and no isolated vertices, then

cc⁡(G)=nETG.(4)\operatorname{cc}(G)=n\mathbb{E}T_G. \tag*{(4)}

The continuous-time processes on distinct components are independent.

Proof. By Lemma 2.1, superposing the nn independent rate-1 clocks gives a Poisson process of rate nn. Its successive vertex labels are independent and uniform on V(G)V(G), and independent of the interarrival times Z1,Z2,…Z_1,Z_2,\ldots, which have distribution Exp⁡(n)\operatorname{Exp}(n). Generate the neighbor choices using further independent randomness. The covering states at ring times then follow the discrete process, and

TG=∑j=1NGZj.T_G=\sum_{j=1}^{N_G}Z_j.

Since NGN_G depends only on the labels and neighbor choices, conditioning on NGN_G gives ETG=ENG/n\mathbb{E}T_G=\mathbb{E}N_G/n.

The expectations are finite. From any nonempty uncovered set, choose a vertex uu and a neighbor vv. Sampling vv produces a new covering, so the expected number of steps until the next covering is at most nn. There are exactly nn coverings, hence ENG≤n2\mathbb{E}N_G\le n^2. Finally, distinct components use disjoint sets of clocks and independent neighbor choices. Their continuous-time processes are therefore independent.

Lemma 2.5. For t≥0t\ge0, define

q(t)=1−(1+2t)e−2t,(5)q(t)=1-(1+2t)e^{-2t}, \tag*{(5)}
r(t)=1−9e−2t+(8+6t)e−3t.(6)r(t)=1-9e^{-2t}+(8+6t)e^{-3t}. \tag*{(6)}

Then P(TC4≤t)=q(t)2\mathbb{P}(T_{C_4}\le t)=q(t)^2 and P(TK3≤t)=r(t)\mathbb{P}(T_{K_3}\le t)=r(t). Consequently, for every integer k≥1k\ge1,

P(T3kC4≤t)=q(t)6k,(7)\mathbb{P}(T_{3kC_4}\le t)=q(t)^{6k}, \tag*{(7)}
P(T4kK3≤t)=r(t)4k.(8)\mathbb{P}(T_{4kK_3}\le t)=r(t)^{4k}. \tag*{(8)}

Proof. View C4C_4 as K2,2K_{2,2}, with vertex classes LL and RR. Let AtA_t and BtB_t count the clock rings in LL and RR, respectively, up to time tt. These are independent Poisson random variables with mean 2t2t. Each ring in LL covers a new vertex of RR until both vertices of RR are covered, and the same statement holds with LL and RR interchanged. Thus the four-cycle is completely covered by time tt if and only if At≥2A_t\ge2 and Bt≥2B_t\ge2. It follows that

P(TC4≤t)=P(At≥2)P(Bt≥2)=(1−(1+2t)e−2t)2=q(t)2.\mathbb{P}(T_{C_4}\le t)=\mathbb{P}(A_t\ge2)\mathbb{P}(B_t\ge2)=\left(1-(1+2t)e^{-2t}\right)^2=q(t)^2.

In K3K_3, every vertex has an uncovered neighbor while at least two vertices remain uncovered. Hence every ring is successful until the second covering, and the first two waiting times are

independent Exp⁡(3)\operatorname{Exp}(3) variables. After the second covering, exactly one vertex remains uncovered. It is covered at the next ring from either of its two neighbors, whose combined clock rate is 2. By the strong Markov property in Lemma 2.1, the conditional distribution of this last waiting time, given the history up to the second covering, is Exp⁡(2)\operatorname{Exp}(2). Since this distribution does not depend on the history, the last waiting time is independent of the first two. Let XX be the sum of the first two waiting times and YY the last waiting time. Then XX has density 9se−3s9s e^{-3s}, Y∼Exp⁡(2)Y \sim\operatorname{Exp}(2), and XX and YY are independent. Therefore,

P(TK3≤t)=∫0t9se−3s(1−e−2(t−s)) ds=1−(1+3t)e−3t−9e−2t(1−(1+t)e−t)=1−9e−2t+(8+6t)e−3t=r(t).\mathbb{P}(T_{K_3} \le t) = \int_0^t 9s e^{-3s}\left(1-e^{-2(t-s)}\right)\,ds = 1-(1+3t)e^{-3t}-9e^{-2t}\left(1-(1+t)e^{-t}\right) = 1-9e^{-2t}+(8+6t)e^{-3t}=r(t).

A disjoint union is completely covered by time tt if and only if all its components are completely covered by that time. By Lemma 2.4, the component completion times are independent. Thus, for mm copies of a graph FF,

P(TmF≤t)=(P(TF≤t))m.\mathbb{P}(T_{mF}\le t)=\left(\mathbb{P}(T_F\le t)\right)^m.

Taking F=C4F=C_4, m=3km=3k, and then F=K3F=K_3, m=4km=4k, gives (7) and (8), respectively.

For integers m,d≥1m,d\ge1, let Dm,dD_{m,d} be the number of independent uniform draws from mm types required to collect at least dd copies of each type. This is the classical repeated coupon-collector problem.

Theorem 2.6 (Newman–Shepp [8 Theorem 2]). For each fixed d≥2d\ge2,

EDm,d=m(log⁡m+(d−1)log⁡log⁡m+Od(1))(m→∞).(9)\mathbb{E}D_{m,d}=m\left(\log m+(d-1)\log\log m+O_d(1)\right)\qquad(m\to\infty). \tag*{(9)}

Erdős and Rényi [7] obtained the corresponding limiting distribution.

Extremal graphs of degree two

For a 2-regular graph GG, form an auxiliary multigraph on the same vertex set by placing one edge between the two neighbors of each vertex of GG. If uu is uncovered, its covering rate is

∑v∼u1#{uncovered neighbors of v}=1+12#{covered auxiliary neighbors of u},\sum_{v\sim u}\frac{1}{\#\{\text{uncovered neighbors of }v\}}=1+\frac{1}{2}\#\{\text{covered auxiliary neighbors of }u\},

with multiplicities counted. Thus the covering process has the same generator as an infection process in which each vertex becomes infected spontaneously at rate 1, and each infected neighbor transmits infection at rate 1/21/2. Both processes start from the empty set, so Lemma 2.2 shows that their evolving covered and infected sets have the same law, with the same time parameter. This auxiliary infection process is a special case of the discrete Bass model. Bounds on adoption probabilities and decompositions of susceptibility events are given in [9, 10].

Let Fm(t)F_m(t) be the probability that this infection process covers an mm-cycle by time tt. For m=2m=2, use two parallel edges; the two successive waiting times then have distribution Exp⁡(2)\operatorname{Exp}(2), so F2=qF_2=q. Set F1(t)=1−e−tF_1(t)=1-e^{-t} for the generating functions below. The auxiliary multigraph of an odd cycle is isomorphic to that cycle, whereas the auxiliary multigraph of C2mC_{2m} consists of two disjoint mm-cycles. The equality in law therefore gives

P(TCℓ≤t)={Fℓ(t),ℓ odd,Fℓ/2(t)2,ℓ even.(10)\mathbb{P}(T_{C_\ell}\le t)= \begin{cases} F_\ell(t), & \ell\ \text{odd},\\ F_{\ell/2}(t)^2, & \ell\ \text{even}. \end{cases} \tag*{(10)}

In particular, F3=rF_3=r, and TC6=dT2C3T_{C_6}\overset{\mathrm{d}}{=}T_{2C_3}.

Lemma 3.1. For t>0t>0, put a=e−ta=e^{-t}. There are positive coefficients cj(t)c_j(t) such that

∑m≥1Fm(t)mxm=−log⁡(1−Ct(x)),Ct(x)=∑j≥1cj(t)xj,(11)\sum_{m\geq1}\frac{F_m(t)}{m}x^m=-\log(1-C_t(x)),\qquad C_t(x)=\sum_{j\geq1}c_j(t)x^j, \tag*{(11)}

where c1(t)=1−ac_1(t)=1-a and

cj(t)=a2∫01−avj−2(j−2)!1−a−v(a+v)2 dv(j≥2).(12)c_j(t)=a^2\int_0^{1-a}\frac{v^{j-2}}{(j-2)!}\frac{1-a-v}{(a+v)^2}\,dv\qquad(j\geq2). \tag*{(12)}

All generating functions are formal power series in xx.

Proof. Consider an mm-cycle with vertex set VV, where m≥2m\geq2, with two parallel edges when m=2m=2. Start with every vertex uninfected. Place independent rate-1/21/2 Poisson transmission arrows on each oriented edge and independent rate-1 spontaneous-infection marks at each vertex. An arrow from an infected vertex infects its endpoint, and infection is permanent. Fix t≥0t\geq0 and a nonempty set SS of rr vertices. Choose a clockwise orientation of the cycle, and let k1,…,krk_1,\ldots,k_r be the numbers of vertices outside SS strictly between consecutive vertices of SS. Thus

ki≥0,k1+⋯+kr=m−r.k_i\geq0,\qquad k_1+\cdots+k_r=m-r.

Trace potential infection paths backward from SS at time tt. For 0≤s≤t0\leq s\leq t, let BsB_s be the set of vertices at time t−st-s from which a path, using vertical time segments and transmission arrows, can reach SS at time tt. Then B0=SB_0=S. On encountering an arrow x→yx\to y during the backward exploration, add xx to BsB_s if yy is already an ancestor. Since there is no recovery, every vertex that enters the ancestor set remains in BsB_s as ss increases.

Within a gap containing k≥1k\geq1 vertices, the ancestor set advances from its two ends. Until the gap is filled, exactly two oriented boundary edges can add another ancestor, each at rate 1/21/2. When only one vertex remains, the two arrows capable of adding it are still distinct. The total rate of acquiring another gap vertex is therefore 1 at every stage. By the memoryless property of the Poisson clocks, the number acquired by backward time ss has the same process law as min⁡{Ps,k}\min\{P_s,k\}, where PP is a rate-1 Poisson process. Distinct gaps use disjoint families of transmission arrows, so their growth processes are independent. This also covers r=1r=1; for m=2m=2, the two parallel edges provide the two distinct boundary channels. Let Xi(s)X_i(s) count the ancestors acquired in the ii-th gap. The rr vertices of SS remain ancestors throughout, so

∣Bs∣=r+∑i=1rXi(s).|B_s|=r+\sum_{i=1}^{r}X_i(s).

Conditional on all transmission arrows, every vertex of SS is uninfected at time tt exactly when the backward ancestor region contains no spontaneous-infection mark. The marks have rate 1 and are independent of the arrows. Hence their conditional avoidance probability is

exp⁡(−∫0t∣Bs∣ ds)=e−rt∏i=1rexp⁡(−∫0tXi(s) ds).\exp\left(-\int_0^t|B_s|\,ds\right)=e^{-rt}\prod_{i=1}^{r}\exp\left(-\int_0^tX_i(s)\,ds\right).

Define

hk(t)=Eexp⁡(−∫0tmin⁡{Ps,k} ds)(k≥0).(13)h_k(t)=\mathbb{E}\exp\left(-\int_0^t\min\{P_s,k\}\,ds\right)\qquad(k\geq0). \tag*{(13)}

In particular, h0(t)=1h_0(t)=1. Taking expectations and using the independence of the gap processes gives

P(S is entirely uninfected at time t)=e−rt∏i=1rhki(t)=ar∏i=1rhki(t).(14)\mathbb{P}(S\text{ is entirely uninfected at time }t)=e^{-rt}\prod_{i=1}^{r}h_{k_i}(t)=a^r\prod_{i=1}^{r}h_{k_i}(t). \tag*{(14)}

For the gap functional, fix k≥1k \ge1, and let E∼Exp⁡(1)E \sim\operatorname{Exp}(1) be the first arrival time of PP. This is the first backward arrow that enlarges the ancestor set within the gap. If E>tE>t, the integral in (13) is zero, contributing e−te^{-t} to hk(t)h_k(t). Conditional on E=s≤tE=s \le t, the subsequent arrivals form an independent rate-1 Poisson process P′P', and

∫0tmin⁡{Pv,k} dv=(t−s)+∫0t−smin⁡{Pu′,k−1} du.\int_0^t \min\{P_v,k\}\,\mathrm{d}v=(t-s)+\int_0^{t-s}\min\{P'_u,k-1\}\,\mathrm{d}u.

The conditional expectation of the exponential in (13) is therefore e−(t−s)hk−1(t−s)e^{-(t-s)}h_{k-1}(t-s). Since EE has density e−se^{-s},

hk(t)=e−t+∫0te−se−(t−s)hk−1(t−s) ds=e−t(1+∫0thk−1(u) du).(15)\begin{aligned} h_k(t)&=e^{-t}+\int_0^t e^{-s}e^{-(t-s)}h_{k-1}(t-s)\,\mathrm{d}s\\ &=e^{-t}\left(1+\int_0^t h_{k-1}(u)\,\mathrm{d}u\right). \tag*{(15)} \end{aligned}

Differentiating, and recalling that a=e−ta=e^{-t}, yields

hk′(t)=−hk(t)+ahk−1(t),hk(0)=1(k≥1),(16)h'_k(t)=-h_k(t)+ah_{k-1}(t),\qquad h_k(0)=1\qquad(k\ge1), \tag*{(16)}

with the separate boundary condition h0(t)≡1h_0(t)\equiv1.

For each vertex vv, let AvA_v be the event that vv is uninfected at time tt. Since complete infection means that none of the events AvA_v occurs, inclusion–exclusion and (14) give

Fm(t)=1+∑r=1m(−1)r∑S⊆V∣S∣=rP(⋂v∈SAv)=1+∑r=1m(−a)rWm,r(t),(17)\begin{aligned} F_m(t)=1+\sum_{r=1}^{m}(-1)^r\sum_{\substack{S\subseteq V\\|S|=r}}\mathbb{P}\left(\bigcap_{v\in S}A_v\right) \\ &=1+\sum_{r=1}^{m}(-a)^rW_{m,r}(t), \tag*{(17)} \end{aligned}

where

Wm,r(t)=∑S⊆V∣S∣=r∏i=1rhki(S)(t).W_{m,r}(t)=\sum_{\substack{S\subseteq V\\|S|=r}}\prod_{i=1}^{r}h_{k_i(S)}(t).

The weight of SS is well defined, since choosing a different starting vertex only cyclically permutes the gap lengths.

To evaluate Wm,rW_{m,r}, count pairs (S,v)(S,v) with ∣S∣=r|S|=r and v∈Sv\in S, assigning each pair the weight of SS. Each subset has exactly rr choices of the marked vertex, so their total weight is rWm,r(t)rW_{m,r}(t). Alternatively, choose the marked vertex in mm ways and specify its ordered clockwise gaps (k1,…,kr)(k_1,\ldots,k_r), where the entries are nonnegative and sum to m−rm-r. These data determine a unique marked subset: starting at the marked vertex, move successively k1+1,…,kr+1k_1+1,\ldots,k_r+1 steps around the cycle. These increments are positive and sum to mm, so the selected vertices are distinct and the last move returns to the starting vertex. Thus

rWm,r(t)=m∑k1,…,kr≥0k1+⋯+kr=m−r∏i=1rhki(t).(18)rW_{m,r}(t)=m\sum_{\substack{k_1,\ldots,k_r\ge0\\k_1+\cdots+k_r=m-r}}\prod_{i=1}^{r}h_{k_i}(t). \tag*{(18)}

This count also holds when the gap sequence is periodic: the rr marked vertices are distinct choices, even if some of the resulting cyclic gap sequences coincide. Put H(x,t)=∑k≥0hk(t)xkH(x,t)=\sum_{k\ge0}h_k(t)x^k, and let [xj][x^j] denote coefficient extraction. Expanding the product of rr copies of HH gives

[xm−r]H(x,t)r=∑k1,…,kr≥0k1+⋯+kr=m−r∏i=1rhki(t).[x^{m-r}]H(x,t)^r=\sum_{\substack{k_1,\ldots,k_r\ge0\\k_1+\cdots+k_r=m-r}}\prod_{i=1}^{r}h_{k_i}(t).

Consequently, Wm,r(t)=(m/r)[xm−r]H(x,t)rW_{m,r}(t)=(m/r)[x^{m-r}]H(x,t)^r, and (17) becomes

Fm(t)=1+∑r=1mmr(−a)r[xm−r]H(x,t)r.(19)F_m(t)=1+\sum_{r=1}^{m}\frac{m}{r}(-a)^r[x^{m-r}]H(x,t)^r. \tag*{(19)}

For m=1m=1, its right-hand side is 1−a1-a, since h0=1h_0=1, so the same identity holds with the stated convention for F1F_1.

Divide (19) by mm, multiply by xmx^m, and sum over m≥1m\ge1. Using zz as the coefficient-extraction variable, we obtain

∑m≥1Fm(t)mxm=−log⁡(1−x)+∑r≥1(−a)rr∑m≥rxm[zm−r]H(z,t)r=−log⁡(1−x)+∑r≥1(−axH(x,t))rr=−log⁡(1−x)−log⁡(1+axH(x,t))=−log⁡K(x,t),K(x,t)=(1−x)(1+axH(x,t)).\begin{aligned} \sum_{m\ge1}\frac{F_m(t)}{m}x^m=-\log(1-x)+\sum_{r\ge1}\frac{(-a)^r}{r}\sum_{m\ge r}x^m[z^{m-r}]H(z,t)^r \\ &=-\log(1-x)+\sum_{r\ge1}\frac{(-axH(x,t))^r}{r} \\ &=-\log(1-x)-\log(1+axH(x,t)) \\ &=-\log K(x,t),\qquad K(x,t)=(1-x)(1+axH(x,t)). \end{aligned}

All rearrangements are valid as formal power series, since each coefficient receives only finitely many contributions. The recurrence for hkh_k implies

Ht=1−(1−ax)H,Kt=2(1−x)−(2−ax)K,K(x,0)=1.H_t=1-(1-ax)H,\qquad K_t=2(1-x)-(2-ax)K,\qquad K(x,0)=1.

Writing K=1−∑j≥1cjxjK=1-\sum_{j\ge1}c_jx^j yields

c1=1−a,cj′=−2cj+acj−1,cj(0)=0(j≥2).c_1=1-a,\qquad c_j'=-2c_j+ac_{j-1},\qquad c_j(0)=0\quad(j\ge2).

Equivalently, as functions of aa, dda(cj/a2)=−cj−1/a2\frac{d}{da}(c_j/a^2)=-c_{j-1}/a^2. Repeated integration from aa to 11, starting with c1/a2=(1−a)/a2c_1/a^2=(1-a)/a^2, proves (12).

For the remainder of the section, fix t>0t>0 and put

b=q(t),p=1−e−tb,δ=1−p,gm=Fm(t)bm.b=\sqrt{q(t)},\qquad p=\frac{1-e^{-t}}{b},\qquad\delta=1-p,\qquad g_m=\frac{F_m(t)}{b^m}.

The coefficient of x2x^2 in (11) gives b2=c12+2c2b^2=c_1^2+2c_2. Since 0<c2≤c12/20<c_2\le c_1^2/2 by (12), we have

12≤p<1,0<δ<p.(20)\frac{1}{\sqrt{2}}\le p<1,\qquad0<\delta<p. \tag*{(20)}

Lemma 3.2. Define Δj\Delta_j by

Ct(x/b)=1−(1−x)eδx+Δ(x).C_t(x/b)=1-(1-x)e^{\delta x}+\Delta(x).

Then

Δ(x)=∑j≥3Δjxj,Δj>0,Δ4≤Δ32,Δ5≤Δ34.\Delta(x)=\sum_{j\ge3}\Delta_jx^j,\qquad\Delta_j>0,\qquad\Delta_4\le\frac{\Delta_3}{2},\qquad\Delta_5\le\frac{\Delta_3}{4}.

Proof. Set α=e−t/b\alpha=e^{-t/b}. Substitution v=byv=by in (12) gives

cjbj=∫0pyj−2(j−2)!w(y) dy,w(y)=α2(p−y)(α+y)2(j≥2).\frac{c_j}{b^j}=\int_0^p\frac{y^{j-2}}{(j-2)!}w(y)\,dy,\qquad w(y)=\frac{\alpha^2(p-y)}{(\alpha+y)^2}\quad(j\ge2).

Let μ\mu have density w(y)w(y) on [0,p][0,p], and let ν\nu have density p+yp+y on [0,δ][0,\delta]. Their masses agree:

μ([0,p])=c2b2=1−p22=pδ+δ22=ν([0,δ]).\mu([0,p])=\frac{c_2}{b^2}=\frac{1-p^2}{2}=p\delta+\frac{\delta^2}{2}=\nu([0,\delta]).

For 0<y<δ0<y<\delta, we have w(y)≤p−y<p+yw(y)\le p-y<p+y. Thus μ−ν\mu-\nu is negative below δ\delta, positive above δ\delta, and has total mass zero. The integral of an increasing function against μ\mu is therefore at least its integral against ν\nu, with strict inequality when the function is strictly increasing. Applying this observation to the monomials gives

cjbj≥∫0δyj−2(j−2)!(p+y) dy=δj−1(j−δ)j!.\frac{c_j}{b^j}\ge\int_0^\delta\frac{y^{j-2}}{(j-2)!}(p+y)\,\mathrm{d}y=\frac{\delta^{j-1}(j-\delta)}{j!}.

with equality for j=2j=2 and strict inequality for j≥3j\ge3. The expression on the right is the coefficient of xjx^j in 1−(1−x)eδx1-(1-x)e^{\delta x}, whose linear coefficient is p=c1/bp=c_1/b. This proves the assertions about the coefficients of Δ\Delta.

For the remaining bounds, put L(y)=ν([0,y])−μ([0,y])L(y)=\nu([0,y])-\mu([0,y]). Then L≥0L\ge0, and integration by parts gives

Δj=∫0pyj−3(j−3)!L(y) dy(j≥3).\Delta_j=\int_0^p\frac{y^{j-3}}{(j-3)!}L(y)\,\mathrm{d}y\qquad(j\ge3).

On [δ,p][\delta,p], the function L(y)=μ([y,p])L(y)=\mu([y,p]) is nonincreasing. Since δ+p=1\delta+p=1 and δ<1/2\delta<1/2, pairing yy with 1−y1-y on [δ,p][\delta,p] gives

Δ4−12Δ3=∫0δ(y−12)L(y) dy+∫δ1/2(y−12)(L(y)−L(1−y)) dy≤0.\Delta_4-\frac{1}{2}\Delta_3=\int_0^\delta\left(y-\frac{1}{2}\right)L(y)\,\mathrm{d}y+\int_\delta^{1/2}\left(y-\frac{1}{2}\right)\bigl(L(y)-L(1-y)\bigr)\,\mathrm{d}y\le0.

Both integrals are nonpositive: L≥0L\ge0 on the first interval, and L(y)≥L(1−y)L(y)\ge L(1-y) on the second. Finally, 0≤y≤p<10\le y\le p<1 implies Δ5≤Δ4/2≤Δ3/4\Delta_5\le\Delta_4/2\le\Delta_3/4.

Lemma 3.3. We have g2=1g_2=1, gm>1g_m>1 for m≥3m\ge3, and

1<g3<g5<g33,gm>g3 (m≥5),gm>g5 (m≥8).1<g_3<g_5<g_3^3,\qquad g_m>g_3\ (m\ge5),\qquad g_m>g_5\ (m\ge8).

Proof. The coefficients

sj=[xj]e−δx1−x=∑i=0j(−δ)ii!s_j=[x^j]\frac{e^{-\delta x}}{1-x}=\sum_{i=0}^j\frac{(-\delta)^i}{i!}

lie between p=1−δp=1-\delta and 11, by the alternating-series bounds. Put

D(x)=Δ(x)e−δx1−x,E(x)=−log⁡(1−D(x)).D(x)=\Delta(x)\frac{e^{-\delta x}}{1-x},\qquad E(x)=-\log(1-D(x)).

These series have nonnegative coefficients and start in degree 3. Since

1−Ct(x/b)=(1−x)eδx(1−D(x)),1-C_t(x/b)=(1-x)e^{\delta x}(1-D(x)),

the generating-function identity gives

gm=1+m[xm]E(x)(m≥2).g_m=1+m[x^m]E(x)\qquad(m\ge2).

This proves g2=1g_2=1 and gm>1g_m>1 for m≥3m\ge3. In particular,

g3−1=3Δ3,g5−1=5(s2Δ3+pΔ4+Δ5).g_3-1=3\Delta_3,\qquad g_5-1=5(s_2\Delta_3+p\Delta_4+\Delta_5).

The coefficientwise inequality E≥DE\ge D and (20) now give

gm−1≥mpΔ3>3Δ3=g3−1(m≥5),g_m-1\ge mp\Delta_3>3\Delta_3=g_3-1\qquad(m\ge5),
gm−1≥mp(Δ3+Δ4+Δ5)>5(Δ3+Δ4+Δ5)≥g5−1(m≥8).g_m-1\ge mp(\Delta_3+\Delta_4+\Delta_5)>5(\Delta_3+\Delta_4+\Delta_5)\ge g_5-1\qquad(m\ge8).

Finally, Lemma 3.2 yields

g5−1≤5(1+12+14)Δ3=354Δ3<9Δ3=3(g3−1)<g33−1.g_5-1\le5\left(1+\frac{1}{2}+\frac{1}{4}\right)\Delta_3=\frac{35}{4}\Delta_3<9\Delta_3=3(g_3-1)<g_3^3-1.

Proof of Theorem 1.1. Fix t>0t > 0. By (10), the completion-time distribution function of a cycle CℓC_{\ell}, divided by bℓb^{\ell}, is gℓg_{\ell} for odd ℓ\ell and gℓ/22g_{\ell/2}^{2} for even ℓ\ell. Lemma 3.3 therefore permits replacing a cycle by four-cycles together with, respectively, no additional component, one C5C_{5}, two C3C_{3}’s, or one C3C_{3}, according as its length is congruent to 0,1,2,30,1,2,3 modulo 4. Each replacement preserves the order and does not increase the distribution function. The inequality is strict unless the original cycle is C3C_{3}, C4C_{4}, C5C_{5}, or C6C_{6}; replacing C6C_{6} by 2C32C_{3} leaves the distribution function unchanged.

The resulting graph is uC3⊔wC4⊔vC5uC_{3} \sqcup wC_{4} \sqcup vC_{5}, whose normalized distribution function is g3ug5vg_{3}^{u}g_{5}^{v}. The inequalities 1<g3<g5<g331 < g_{3} < g_{5} < g_{3}^{3} give three further strict replacements:

3C3⟶C5⊔C4,2C5⟶2C3⊔C4,C3⊔C5⟶2C4.3C_{3} \longrightarrow C_{5} \sqcup C_{4}, \qquad2C_{5} \longrightarrow2C_{3} \sqcup C_{4}, \qquad C_{3} \sqcup C_{5} \longrightarrow2C_{4}.

Each replacement increases the number of four-cycles, so iteration terminates. In the resulting graph, u≤2u \le2, v≤1v \le1, and uv=0uv = 0. The congruence 3u+5v≡n(mod4)3u + 5v \equiv n \pmod{4} determines

(u,v)=(0,0),(0,1),(2,0),(1,0)(u,v) = (0,0), (0,1), (2,0), (1,0)

in the four residue classes, respectively. These give exactly the extremal graphs stated in the theorem, allowing for the equality C6↔2C3C_{6} \leftrightarrow2C_{3}.

By component independence, all the comparisons of distribution functions can be multiplied. Every graph outside the stated equality cases requires at least one strict replacement, so its distribution function is strictly larger at every t>0t > 0. Integrating the tail inequalities and applying Lemma 2.4 proves the expectation statement and its equality cases.

Corollary 3.4. For every finite simple 2-regular graph GG on nn vertices.

P(TG≤t)≥q(t)n/2(t>0).\mathbb{P}(T_G \le t) \ge q(t)^{n/2} \qquad(t > 0).

Equality at any positive tt holds if and only if all components of GG are four-cycles.

Proof. Apply g2=1g_{2} = 1 and gm>1g_{m} > 1 for m≥3m \ge3 to (10), and multiply over the components.

Thus every extremal graph has all but at most six vertices in four-cycle components. Among orders divisible by three, triangle unions are extremal exactly at orders three and six. The smallest counterexample in degree two therefore has nine vertices:

cc⁡(C4⊔C5)>cc⁡(3K3).(21)\operatorname{cc}(C_{4} \sqcup C_{5}) > \operatorname{cc}(3K_{3}). \tag*{(21)}

Theorem 1.1 also gives counterexamples at every larger order divisible by three. At orders divisible by twelve, the comparison has the following explicit form.

Corollary 3.5. For every integer k≥1k \ge1,

cc⁡(3kC4)>cc⁡(4kK3).(22)\operatorname{cc}(3kC_{4}) > \operatorname{cc}(4kK_{3}). \tag*{(22)}

Both graphs are simple and 2-regular on 12k12k vertices, and

P(T3kC4≤t)<P(T4kK3≤t)(t>0).(23)\mathbb{P}(T_{3kC_{4}} \le t) < \mathbb{P}(T_{4kK_{3}} \le t) \qquad(t > 0). \tag*{(23)}

In particular,

cc⁡(3C4)=39096868116200000≈24.134,(24)\operatorname{cc}(3C_{4}) = \frac{390968681}{16200000} \approx24.134, \tag*{(24)}
cc⁡(4K3)=2227388670199685021500≈22.998.(25)\operatorname{cc}(4K_{3}) = \frac{222738867019}{9685021500} \approx22.998. \tag*{(25)}

The first exact value also equals the expected number of rolls of a fair six-sided die needed to see every face twice; it is recorded in [4 Problem 9].

Proof of Corollary 3.5. The strict comparisons follow from Theorem 1.1, since 3kC43kC_4 is the unique extremal graph at order 12k12k, whereas 4kK34kK_3 is not isomorphic to it. For k=1k=1, the tail-integral identity (3) and Lemma 2.4 give

cc⁡(3C4)=12∫0∞(1−q(t)6) dt.\operatorname{cc}(3C_4)=12\int_0^\infty\left(1-q(t)^6\right)\,\mathrm{d}t.
cc⁡(4K3)=12∫0∞(1−r(t)4) dt.\operatorname{cc}(4K_3)=12\int_0^\infty\left(1-r(t)^4\right)\,\mathrm{d}t.

Expanding the integrands and applying

∫0∞tje−at dt=j!aj+1(a>0, j=0,1,2,…)\int_0^\infty t^j e^{-at}\,\mathrm{d}t=\frac{j!}{a^{j+1}}\qquad(a>0,\ j=0,1,2,\ldots)

yields (24) and (25).

Remark 3.6. The distributional comparisons concern the Poissonized completion times. Their expectation consequences for the discrete process follow from (4).

Neighborhood structure and extremality

For a nonempty vertex set UU, put NG(U)=⋃u∈UNG(u)N_G(U)=\bigcup_{u\in U}N_G(u), using open neighborhoods. Partition the vertices into equivalence classes according to equality of their open neighborhoods. If GG has minimum degree δ≥1\delta\geq1, let τδ(G)\tau_\delta(G) be the largest size of such a class consisting of vertices of degree δ\delta.

Theorem 4.1. Let GG be a finite simple graph with minimum degree δ≥1\delta\geq1, and put τ=τδ(G)\tau=\tau_\delta(G). There is a constant cG>0c_G>0 such that

P(TG>t)∼cGtτ−1e−δt(t→∞).\mathbb{P}(T_G>t)\sim c_G t^{\tau-1}e^{-\delta t}\qquad(t\to\infty).

Proof. When the uncovered set is UU, a ring is successful exactly when its vertex belongs to NG(U)N_G(U). The total rate of the next covering and the rate at which a particular u∈Uu\in U is covered are

λ(U)=∣NG(U)∣≥δ,aU(u)=∑v∈NG(u)1∣NG(v)∩U∣>0.\lambda(U)=|N_G(U)|\geq\delta,\qquad a_U(u)=\sum_{v\in N_G(u)}\frac{1}{|N_G(v)\cap U|}>0.

In particular, every ordering of the vertices has positive probability of occurring as the order in which they are covered.

Equality λ(U)=δ\lambda(U)=\delta holds precisely when UU is contained in a single class of degree-δ\delta vertices with the same open neighborhood. Indeed, if ∣NG(U)∣=δ|N_G(U)|=\delta, then every u∈Uu\in U satisfies NG(u)⊆NG(U)N_G(u)\subseteq N_G(U) and ∣NG(u)∣≥δ|N_G(u)|\geq\delta, forcing NG(u)=NG(U)N_G(u)=N_G(U). The converse follows immediately. Once a covering order reaches such a set, all subsequent nonempty uncovered sets remain in the same class. Hence the number of holding times of rate δ\delta along that order is at most τ\tau. This maximum is attained by first covering all vertices outside a class of size τ\tau.

Condition on a covering order π\pi. By Lemma 2.2, the holding time at each state is exponential with rate λ(U)\lambda(U), independently of the next transition. Thus the successive holding times, conditional on π\pi, are independent. If the order contains k≥1k\geq1 holding times of rate δ\delta, its conditional completion time is X+YX+Y, where YY is a sum of kk independent Exp⁡(δ)\operatorname{Exp}(\delta) variables and XX is an independent sum of exponential variables of rates greater than δ\delta. Consequently

P(X+Y>t)∼δk−1(k−1)!EeδXtk−1e−δt.\mathbb{P}(X+Y>t)\sim\frac{\delta^{k-1}}{(k-1)!}\mathbb{E}e^{\delta X}t^{k-1}e^{-\delta t}.

To verify this asymptotic, condition on XX and apply the Erlang tail formula from Lemma 2.3, namely P(Y>s)=e−δs∑j=0k−1(δs)jj!\mathbb{P}(Y>s)=e^{-\delta s}\sum_{j=0}^{k-1}\frac{(\delta s)^j}{j!}. After division by tk−1e−δtt^{k-1}e^{-\delta t}, the highest power converges by dominated convergence with dominator eδXe^{\delta X}, and the lower powers vanish. All rates in XX are integers at least δ+1\delta+1, so Ee(δ+1/2)X<∞\mathbb{E}e^{(\delta+1/2)X}<\infty; this also makes the contribution from X>tX>t negligible. An order containing no rate-δ\delta holding time has an exponentially smaller tail by the same bound. Finally, average over the finitely many covering orders. Their probabilities are positive, the largest possible kk is τ\tau, and every order attaining it has a positive leading coefficient. This proves the result and the positivity of cGc_G.

For a dd-regular graph write τ(G)=τd(G)\tau(G)=\tau_d(G).

Corollary 4.2. Let GG be a finite simple dd-regular graph, d≥2d\ge2. Then 1≤τ(G)≤d1\le\tau(G)\le d, with equality τ(G)=d\tau(G)=d if and only if GG has a Kd,dK_{d,d} component. If it has exactly b≥1b\ge1 such components, then

P(TG>t)∼2bdd−1(d−1)!td−1e−dt.\mathbb{P}(T_G>t)\sim\frac{2bd^{d-1}}{(d-1)!}t^{d-1}e^{-dt}.

In particular, Kd,dK_{d,d} is the unique connected dd-regular graph whose completion-time tail has a polynomial factor of degree $d-1.

Proof. Let CC be a class of vertices with the same open neighborhood DD. Every vertex of DD is adjacent to all of CC, so ∣C∣≤d|C|\le d. If ∣C∣=d|C|=d, then ∣D∣=d|D|=d, C∩D=∅C\cap D=\varnothing, and the edges between the two classes account for every edge incident with a vertex of C∪DC\cup D. Consequently, these vertices form a Kd,dK_{d,d} component. The converse is immediate.

In a Kd,dK_{d,d} component, each class must generate dd clock rings to cover the opposite class. These two times are independent sums of dd variables of distribution Exp⁡(d)\operatorname{Exp}(d). Thus Lemma 2.3 gives, with

sd(t)=e−dt∑j=0d−1(dt)jj!,s_d(t)=e^{-dt}\sum_{j=0}^{d-1}\frac{(dt)^j}{j!},

the component survival probability is

2sd(t)−sd(t)2∼2dd−1(d−1)!td−1e−dt.2s_d(t)-s_d(t)^2\sim\frac{2d^{d-1}}{(d-1)!}t^{d-1}e^{-dt}.

Every other component has τ≤d−1\tau\le d-1 and hence a lower-order tail by Theorem 4.1. Independence of components gives the stated coefficient.

Corollary 4.3. Fix d≥2d\ge2 and a positive integer hh divisible by 2d2d, and put B=(h/(2d))Kd,dB=(h/(2d))K_{d,d}. For all sufficiently large tt, BB uniquely maximizes P(TG>t)\mathbb{P}(T_G>t), up to isomorphism, among the dd-regular graphs on hh vertices.

Proof. If τ(G)<d\tau(G)<d, then P(TG>t)/P(TB>t)→0\mathbb{P}(T_G>t)/\mathbb{P}(T_B>t)\to0. Otherwise the ratio tends to 2db/h2db/h, where bb is the number of Kd,dK_{d,d} components of GG. This limit equals 11 exactly when G≅BG\cong B. For every other graph the limit is strictly smaller than 11. Since there are only finitely many graphs on hh vertices, a common threshold for tt can be chosen.

For regular graphs of bounded component order, the corresponding extremal statement holds for the expected completion time. The component multiplicities may vary arbitrarily with the total order.

Theorem 4.4. Fix integers d≥2d\ge2 and L≥2dL\ge2d. For all sufficiently large nn divisible by 2d2d, the graph Bn=(n/(2d))Kd,dB_n=(n/(2d))K_{d,d} uniquely maximizes cc⁡(G)\operatorname{cc}(G), up to isomorphism, among all dd-regular

graphs on nn vertices whose components have at most LL vertices. More precisely, if s(G)s(G) counts the vertices lying outside Kd,dK_{d,d} components, then

cc⁡(Bn)−cc⁡(G)≥e−d32s(G)\operatorname{cc}(B_n)-\operatorname{cc}(G) \ge\frac{e^{-d}}{32}s(G)

for every sufficiently large admissible nn, uniformly over all such GG.

Proof. Write FH(t)=P(TH≤t)F_H(t)=\mathbb{P}(T_H\le t), Q(t)=FKd,d(t)Q(t)=F_{K_{d,d}}(t), and S(t)=1−Q(t)S(t)=1-Q(t). For each connected dd-regular graph H≇Kd,dH\not\cong K_{d,d} of order at most LL, Corollary 4.2 gives (1−FH(t))/S(t)→0(1-F_H(t))/S(t)\to0. Since there are only finitely many such component types, a common t0>0t_0>0 can be chosen so that

1−FH(t)≤min⁡{12,∣V(H)∣8dS(t)}(t≥t0)1-F_H(t)\le\min\left\{\frac{1}{2},\frac{|V(H)|}{8d}S(t)\right\}\qquad(t\ge t_0)

for every such HH. Using log⁡(1−x)≥−2x\log(1-x)\ge-2x for 0≤x≤1/20\le x\le1/2 and −log⁡(1−y)≥y-\log(1-y)\ge y for 0≤y<10\le y<1, we obtain

log⁡FH(t)−∣V(H)∣2dlog⁡Q(t)≥∣V(H)∣4dS(t)(t≥t0).\log F_H(t)-\frac{|V(H)|}{2d}\log Q(t)\ge\frac{|V(H)|}{4d}S(t)\qquad(t\ge t_0).

Put N=n/(2d)N=n/(2d) and s=s(G)s=s(G). Multiplying component distribution functions and summing these inequalities gives

FG(t)≥Q(t)Nexp⁡(s4dS(t))(t≥t0).F_G(t)\ge Q(t)^N\exp\left(\frac{s}{4d}S(t)\right)\qquad(t\ge t_0).

Since ex−1≥xe^x-1\ge x, the tail-integral identity (3) implies

ETBn−ETG=∫0∞(FG(t)−Q(t)N) dt≥−t0Q(t0)N+s4d∫t0∞Q(t)NS(t) dt.\begin{aligned} \mathbb{E}T_{B_n}-\mathbb{E}T_G &=\int_0^\infty\left(F_G(t)-Q(t)^N\right)\,\mathrm{d}t\\ &\ge-t_0Q(t_0)^N+\frac{s}{4d}\int_{t_0}^\infty Q(t)^N S(t)\,\mathrm{d}t. \end{aligned}

Here the possible negative contribution before t0t_0 is bounded using FG≥0F_G\ge0 and the monotonicity of QQ.

Choose uNu_N with S(uN)=1/NS(u_N)=1/N. Such a point exists for N>1N>1, since SS is continuous and strictly decreasing from 11 to 00. We have uN→∞u_N\to\infty, and the explicit tail of Kd,dK_{d,d} gives S(uN+1)/S(uN)→e−dS(u_N+1)/S(u_N)\to e^{-d}. For all sufficiently large NN, the interval [uN,uN+1][u_N,u_N+1] lies above t0t_0, and on this interval

S(t)≥e−d2N,Q(t)N≥(1−1/N)N≥14.S(t)\ge\frac{e^{-d}}{2N},\qquad Q(t)^N\ge(1-1/N)^N\ge\frac{1}{4}.

Consequently

ETBn−ETG≥se−d32dN−t0Q(t0)N.\mathbb{E}T_{B_n}-\mathbb{E}T_G\ge\frac{s e^{-d}}{32dN}-t_0Q(t_0)^N.

Multiplication by n=2dNn=2dN, using Lemma 2.4, yields

cc⁡(Bn)−cc⁡(G)≥se−d16−nt0Q(t0)N.\operatorname{cc}(B_n)-\operatorname{cc}(G)\ge\frac{s e^{-d}}{16}-nt_0Q(t_0)^N.

For G≇BnG\not\cong B_n, the integer ss is positive and divisible by 2d2d, so s≥2ds\ge2d. Since 0<Q(t0)<10<Q(t_0)<1, the last error tends to zero exponentially in nn, independently of GG. For all sufficiently large nn, it is at most se−d/32s e^{-d}/32, proving the asserted bound and strict extremality. When G≅BnG\cong B_n, both sides are zero. ∎

Clique unions and uniform bounds

Proposition 5.1. Fix an integer d≥2d \ge2. For nn divisible by both 2d2d and d+1d+1, put

Bn,d=n2dKd,d,Hn,d=nd+1Kd+1.B_{n,d} = \frac{n}{2d}K_{d,d}, \qquad H_{n,d} = \frac{n}{d+1}K_{d+1}.

As n→∞n \to\infty through these common multiples,

cc⁡(Bn,d)−cc⁡(Hn,d)=(d−1)ndlog⁡log⁡n+Od(n).(26)\operatorname{cc}(B_{n,d})-\operatorname{cc}(H_{n,d})=\frac{(d-1)n}{d}\log\log n+O_d(n). \tag*{(26)}

In particular, cc⁡(Bn,d)>cc⁡(Hn,d)\operatorname{cc}(B_{n,d})>\operatorname{cc}(H_{n,d}) for all sufficiently large such nn.

Proof. Partition Bn,dB_{n,d} into the two vertex classes of each of its complete bipartite components. There are m=n/dm=n/d classes, each of size dd. A uniform vertex sample selects each class with probability 1/m1/m. A sample from one class covers a vertex of its opposite class until the latter is full. The graph is therefore covered exactly when each of the mm classes has been sampled at least dd times. Thus, as discrete random variables,

NBn,d=dDn/d,d.(27)N_{B_{n,d}} \mathrel{\overset{\mathrm{d}}{=}} D_{n/d,d}. \tag*{(27)}

Applying Theorem 2.6 gives

cc⁡(Bn,d)=nd(log⁡(n/d)+(d−1)log⁡log⁡(n/d)+Od(1)).(28)\operatorname{cc}(B_{n,d})=\frac{n}{d}\left(\log(n/d)+(d-1)\log\log(n/d)+O_d(1)\right). \tag*{(28)}

For a single Kd+1K_{d+1}, every ring is successful while at least two vertices remain uncovered. Once only one uncovered vertex remains, a ring is successful precisely when it occurs at one of its dd neighbors. The strong Markov property in Lemma 2.1, applied at the time of the ddth covering, shows that the conditional distribution of the final waiting time is Exp⁡(d)\operatorname{Exp}(d), independently of the preceding history. Consequently, its continuous completion time is S=X+YS=X+Y, where XX is the sum of dd independent Exp⁡(d+1)\operatorname{Exp}(d+1) variables and Y∼Exp⁡(d)Y\sim\operatorname{Exp}(d) is independent of XX. Hence

e−dt≤P(S>t)≤e−dtEedX=(d+1)de−dt(t≥0).(29)e^{-dt}\le\mathbb{P}(S>t)\le e^{-dt}\mathbb{E}e^{dX}=(d+1)^d e^{-dt}\qquad(t\ge0). \tag*{(29)}

The lower bound follows from S≥YS\ge Y. For the upper bound, condition on XX and use P(Y>t−X∣X)≤e−d(t−X)\mathbb{P}(Y>t-X\mid X)\le e^{-d(t-X)}, which remains valid when X>tX>t. For Z∼Exp⁡(d+1)Z\sim\operatorname{Exp}(d+1),

EedZ=(d+1)∫0∞e−s ds=d+1.\mathbb{E}e^{dZ}=(d+1)\int_0^\infty e^{-s}\,ds=d+1.

Independence of the dd summands in XX therefore gives EedX=(d+1)d\mathbb{E}e^{dX}=(d+1)^d. Let h=n/(d+1)h=n/(d+1), and let MhM_h be the maximum of hh independent copies of SS. By component independence, THn,dT_{H_{n,d}} has the same distribution as MhM_h. The lower bound in (29) compares MhM_h with the maximum of hh independent Exp⁡(d)\operatorname{Exp}(d) variables, whose expectation is Hh/dH_h/d by Lemma 2.3, where Hh=∑j=1h1/jH_h=\sum_{j=1}^h 1/j. For the upper bound, apply the union bound and integrate the resulting tail estimate to obtain

Hhd≤EMh≤∫0∞min⁡{1,h(d+1)de−dt} dt=log⁡(h(d+1)d)+1d.\frac{H_h}{d}\le\mathbb{E}M_h\le\int_0^\infty\min\{1,h(d+1)^d e^{-dt}\}\,dt=\frac{\log(h(d+1)^d)+1}{d}.

Since Hh=log⁡h+O(1)H_h=\log h+O(1), Lemma 2.4 yields

cc⁡(Hn,d)=nd(log⁡(n/(d+1))+Od(1)).(30)\operatorname{cc}(H_{n,d})=\frac{n}{d}\left(\log(n/(d+1))+O_d(1)\right). \tag*{(30)}

For fixed dd, the difference between log⁡(n/d)\log(n/d) and log⁡(n/(d+1))\log(n/(d+1)) is the constant log⁡((d+1)/d)\log((d+1)/d), while log⁡log⁡(n/d)=log⁡log⁡n+o(1)\log\log(n/d)=\log\log n+o(1). Subtracting (30) from (28) therefore proves (26).

The error term in (26) depends on the fixed degree dd. In degree two, Theorem 1.1 gives the exact extremal classification at every order, and Corollary 3.5 gives the strict comparison with triangle unions already at order twelve. When the degree is allowed to grow with the order, Alon [2, Section 6, Remark 3] also suggested the uniform additive estimate

cc⁡(G)≤n+O((nlog⁡n)/d),(31)\operatorname{cc}(G) \le n + O((n\log n)/d), \tag*{(31)}

with an absolute implied constant.

Proposition 5.2. For every integer m≥2m \ge2,

0≤cc⁡(2Km)−(2m+2m4m(2mm))≤3m−1.0 \le\operatorname{cc}(2K_m) - \left(2m + \frac{2m}{4^m}\binom{2m}{m}\right) \le\frac{3}{m-1}.

In particular, cc⁡(2Km)≥2m+m\operatorname{cc}(2K_m) \ge2m + \sqrt{m}. Consequently there is no absolute constant CC such that cc⁡(G)≤n+C(nlog⁡n)/d\operatorname{cc}(G) \le n + C(n\log n)/d for every dd-regular graph on nn vertices.

Proof. Let τm\tau_m be the first step by which each component has received at least mm vertex samples. Every sample can cover at most one vertex in its own component, so N2Km≥τmN_{2K_m} \ge\tau_m. After 2m2m steps, the sample count in the first component is B∼Bin⁡(2m,1/2)B \sim\operatorname{Bin}(2m,1/2). The deficient component still needs ∣B−m∣|B-m| samples, each arriving with probability 1/21/2. Therefore

Eτm=2m+2E∣B−m∣=2m+2m4m(2mm).\mathbb{E}\tau_m = 2m + 2\mathbb{E}|B-m| = 2m + \frac{2m}{4^m}\binom{2m}{m}.

The last equality follows by symmetry and telescoping, using

(j−m)(2mj)=m((2m−1j−1)−(2m−1j))(j>m).(j-m)\binom{2m}{j}=m\left(\binom{2m-1}{j-1}-\binom{2m-1}{j}\right)\qquad(j>m).

Writing am=4−m(2mm)a_m=4^{-m}\binom{2m}{m}, induction gives am≥1/(2m)a_m \ge1/(2\sqrt{m}): the initial value is a1=1/2a_1=1/2, and

am+1am=2m+12m+2≥mm+1.\frac{a_{m+1}}{a_m}=\frac{2m+1}{2m+2}\ge\sqrt{\frac{m}{m+1}}.

This proves the required lower bound. Since the graph has n=2mn=2m and d=m−1d=m-1, its excess above nn is at least m\sqrt{m}, whereas (nlog⁡n)/d=O(log⁡m)(n\log n)/d=O(\log m).

For the upper bound, construct the following coupling. Let X1,X2X_1,X_2 be independent sums of m−1m-1 independent variables of distribution Exp⁡(m)\operatorname{Exp}(m), and let E1,E2∼Exp⁡(1)E_1,E_2\sim\operatorname{Exp}(1) be independent of them and of each other. The two clique completion times have the joint law of Si=Xi+Ei/(m−1)S_i=X_i+E_i/(m-1), while the times of the mmth clock ring in the two components have the joint law of Qi=Xi+Ei/mQ_i=X_i+E_i/m. Thus

0≤max⁡iSi−max⁡iQi≤max⁡(E1,E2)m(m−1).0\le\max_i S_i-\max_i Q_i\le\frac{\max(E_1,E_2)}{m(m-1)}.

Poissonization gives

cc⁡(2Km)=2mEmax⁡iSi,Eτm=2mEmax⁡iQi.\operatorname{cc}(2K_m)=2m\mathbb{E}\max_i S_i,\qquad\mathbb{E}\tau_m=2m\mathbb{E}\max_i Q_i.

By Lemma 2.3, Emax⁡(E1,E2)=3/2\mathbb{E}\max(E_1,E_2)=3/2, which proves the upper bound.

The additive estimate therefore fails already for two disjoint cliques because of the imbalance between the numbers of samples received by the two components. Stirling’s formula also gives

cc⁡(2Km)=2m+2mπ+O(m−1/2).\operatorname{cc}(2K_m)=2m+2\sqrt{\frac{m}{\pi}}+O(m^{-1/2}).

The weaker order estimate cc⁡(G)=O(n+(nlog⁡n)/d)\operatorname{cc}(G)=O(n+(n\log n)/d) is compatible with this family, whose expected completion time is n+O(n)=O(n)n+O(\sqrt{n})=O(n).

Declaration of generative AI and AI-assisted technologies

The authors used a large language model during the preparation of this manuscript for assistance with mathematical exploration, checking arguments, organization and language editing. The authors are responsible for the mathematical statements, proofs, references and final text.

School of Mathematical Science, Tianjin Normal University, Tianjin 300387, P.R. China E-mail address: [email protected]

School of Mathematical Sciences, Tiangong University, Tianjin 300387, P.R. China E-mail address: [email protected]

References

  1. [1]M. Adler, E. Halperin, R. M. Karp, and V. V. Vazirani, A stochastic process on the hypercube with applications to peer-to-peer networks, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing, ACM, 2003, pp. 575–584.
  2. [2]N. Alon, Problems and results in extremal combinatorics—II, Discrete Mathematics 308 (2008), 4460–4472.DOI
  3. [3]A. Boneh and M. Hofri, The coupon-collector problem revisited—a survey of engineering problems and computational methods, Communications in Statistics. Stochastic Models 13 (1997), 39–66.DOI
  4. [4]M. M. Conroy, A collection of dice problems, version of September 8, 2018, Problem 9, pp. 16–19. https://www.karlin.mff.cuni.cz/~nagy/NMSA202/dice1.pdf.
  5. [5]N. B. Dimitrov and C. G. Plaxton, Optimal cover time for a graph-based coupon collector process, Journal of Discrete Algorithms 19 (2013), 39–51.
  6. [6]R. Durrett, Essentials of Stochastic Processes, third ed., Springer, Cham, 2016.
  7. [7]P. Erdős and A. Rényi, On a classical problem of probability theory, Publ. Math. Inst. Hungar. Acad. Sci. 6 (1961), 215–220.
  8. [8]D. J. Newman and L. Shepp, The double Dixie cup problem, American Mathematical Monthly 67 (1960), 58–61.DOI
  9. [9]G. Fibich and T. Levin, Universal bounds for spreading on networks, Chaos 34 (2024), 053101.DOI
  10. [10]G. Fibich, T. Levin, and S. Schochet, Funnel theorems for spreading on networks, Chaos 35 (2025), 073109.DOI

Paper details

vlnc:W_9drhtmhp
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

a large language model

View statement
Looking for related papers…
Contents