In this paper
AbstractIntroductionPreliminaries and component distributionsExtremal graphs of degree twoNeighborhood structure and extremalityClique unions and uniform boundsDeclaration of generative AI and AI-assisted technologiesReferencesWorksMathematics
Extremal graphs for Alon's graph coupon-collector conjecture
Abstract
Let 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 maximize \cc(G) among -regular graphs of a prescribed order whenever such unions exist. In this paper, we disprove this conjecture for every fixed and give a complete characterization of the extremal graphs for at every order . 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 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 denote the expected number of steps until all vertices are covered, and write for the disjoint union of copies of . 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 be positive integers such that divides . For every finite simple -regular graph on vertices,
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 at each prescribed order; the smallest counterexample has nine vertices. The complete extremal characterization is given by the following theorem.
Theorem 1.1. For , define
where denotes disjoint union. For every finite simple 2-regular graph on vertices,
Equality holds precisely when , or when and
Moreover, let be the completion time of the same covering process on a graph , with each vertex sampled at the rings of an independent rate-1 Poisson clock. Then
with equality at any positive for exactly the same graphs.
For fixed degree and a fixed bound of at least on component order, unions of uniquely maximize at all sufficiently large orders divisible by . 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 be the number of discrete steps required to cover , so that . 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 denote the completion time of this continuous-time process. We write for an exponential random variable of rate . 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 , and put . Their superposition has rate . Its labels are independent, with probabilities , 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 ,
If are independent variables, where and , then
and
The last identity follows from the memoryless property: the successive order-statistic spacings have rates .
Lemma 2.4. If has vertices and no isolated vertices, then
The continuous-time processes on distinct components are independent.
Proof. By Lemma 2.1, superposing the independent rate-1 clocks gives a Poisson process of rate . Its successive vertex labels are independent and uniform on , and independent of the interarrival times , which have distribution . Generate the neighbor choices using further independent randomness. The covering states at ring times then follow the discrete process, and
Since depends only on the labels and neighbor choices, conditioning on gives .
The expectations are finite. From any nonempty uncovered set, choose a vertex and a neighbor . Sampling produces a new covering, so the expected number of steps until the next covering is at most . There are exactly coverings, hence . Finally, distinct components use disjoint sets of clocks and independent neighbor choices. Their continuous-time processes are therefore independent.
Lemma 2.5. For , define
Then and . Consequently, for every integer ,
Proof. View as , with vertex classes and . Let and count the clock rings in and , respectively, up to time . These are independent Poisson random variables with mean . Each ring in covers a new vertex of until both vertices of are covered, and the same statement holds with and interchanged. Thus the four-cycle is completely covered by time if and only if and . It follows that
In , 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 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 . Since this distribution does not depend on the history, the last waiting time is independent of the first two. Let be the sum of the first two waiting times and the last waiting time. Then has density , , and and are independent. Therefore,
A disjoint union is completely covered by time 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 copies of a graph ,
Taking , , and then , , gives (7) and (8), respectively.
For integers , let be the number of independent uniform draws from types required to collect at least copies of each type. This is the classical repeated coupon-collector problem.
Theorem 2.6 (Newman–Shepp [8 Theorem 2]). For each fixed ,
Erdős and Rényi [7] obtained the corresponding limiting distribution.
Extremal graphs of degree two
For a 2-regular graph , form an auxiliary multigraph on the same vertex set by placing one edge between the two neighbors of each vertex of . If is uncovered, its covering rate is
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 . 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 be the probability that this infection process covers an -cycle by time . For , use two parallel edges; the two successive waiting times then have distribution , so . Set for the generating functions below. The auxiliary multigraph of an odd cycle is isomorphic to that cycle, whereas the auxiliary multigraph of consists of two disjoint -cycles. The equality in law therefore gives
In particular, , and .
Lemma 3.1. For , put . There are positive coefficients such that
where and
All generating functions are formal power series in .
Proof. Consider an -cycle with vertex set , where , with two parallel edges when . Start with every vertex uninfected. Place independent rate- 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 and a nonempty set of vertices. Choose a clockwise orientation of the cycle, and let be the numbers of vertices outside strictly between consecutive vertices of . Thus
Trace potential infection paths backward from at time . For , let be the set of vertices at time from which a path, using vertical time segments and transmission arrows, can reach at time . Then . On encountering an arrow during the backward exploration, add to if is already an ancestor. Since there is no recovery, every vertex that enters the ancestor set remains in as increases.
Within a gap containing 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 . 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 has the same process law as , where is a rate-1 Poisson process. Distinct gaps use disjoint families of transmission arrows, so their growth processes are independent. This also covers ; for , the two parallel edges provide the two distinct boundary channels. Let count the ancestors acquired in the -th gap. The vertices of remain ancestors throughout, so
Conditional on all transmission arrows, every vertex of is uninfected at time 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
Define
In particular, . Taking expectations and using the independence of the gap processes gives
For the gap functional, fix , and let be the first arrival time of . This is the first backward arrow that enlarges the ancestor set within the gap. If , the integral in (13) is zero, contributing to . Conditional on , the subsequent arrivals form an independent rate-1 Poisson process , and
The conditional expectation of the exponential in (13) is therefore . Since has density ,
Differentiating, and recalling that , yields
with the separate boundary condition .
For each vertex , let be the event that is uninfected at time . Since complete infection means that none of the events occurs, inclusion–exclusion and (14) give
where
The weight of is well defined, since choosing a different starting vertex only cyclically permutes the gap lengths.
To evaluate , count pairs with and , assigning each pair the weight of . Each subset has exactly choices of the marked vertex, so their total weight is . Alternatively, choose the marked vertex in ways and specify its ordered clockwise gaps , where the entries are nonnegative and sum to . These data determine a unique marked subset: starting at the marked vertex, move successively steps around the cycle. These increments are positive and sum to , so the selected vertices are distinct and the last move returns to the starting vertex. Thus
This count also holds when the gap sequence is periodic: the marked vertices are distinct choices, even if some of the resulting cyclic gap sequences coincide. Put , and let denote coefficient extraction. Expanding the product of copies of gives
Consequently, , and (17) becomes
For , its right-hand side is , since , so the same identity holds with the stated convention for .
Divide (19) by , multiply by , and sum over . Using as the coefficient-extraction variable, we obtain
All rearrangements are valid as formal power series, since each coefficient receives only finitely many contributions. The recurrence for implies
Writing yields
Equivalently, as functions of , . Repeated integration from to , starting with , proves (12).
For the remainder of the section, fix and put
The coefficient of in (11) gives . Since by (12), we have
Lemma 3.2. Define by
Then
Proof. Set . Substitution in (12) gives
Let have density on , and let have density on . Their masses agree:
For , we have . Thus is negative below , positive above , and has total mass zero. The integral of an increasing function against is therefore at least its integral against , with strict inequality when the function is strictly increasing. Applying this observation to the monomials gives
with equality for and strict inequality for . The expression on the right is the coefficient of in , whose linear coefficient is . This proves the assertions about the coefficients of .
For the remaining bounds, put . Then , and integration by parts gives
On , the function is nonincreasing. Since and , pairing with on gives
Both integrals are nonpositive: on the first interval, and on the second. Finally, implies .
Lemma 3.3. We have , for , and
Proof. The coefficients
lie between and , by the alternating-series bounds. Put
These series have nonnegative coefficients and start in degree 3. Since
the generating-function identity gives
This proves and for . In particular,
The coefficientwise inequality and (20) now give
Finally, Lemma 3.2 yields
Proof of Theorem 1.1. Fix . By (10), the completion-time distribution function of a cycle , divided by , is for odd and for even . Lemma 3.3 therefore permits replacing a cycle by four-cycles together with, respectively, no additional component, one , two ’s, or one , according as its length is congruent to modulo 4. Each replacement preserves the order and does not increase the distribution function. The inequality is strict unless the original cycle is , , , or ; replacing by leaves the distribution function unchanged.
The resulting graph is , whose normalized distribution function is . The inequalities give three further strict replacements:
Each replacement increases the number of four-cycles, so iteration terminates. In the resulting graph, , , and . The congruence determines
in the four residue classes, respectively. These give exactly the extremal graphs stated in the theorem, allowing for the equality .
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 . 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 on vertices.
Equality at any positive holds if and only if all components of are four-cycles.
Proof. Apply and for 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:
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 ,
Both graphs are simple and 2-regular on vertices, and
In particular,
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 is the unique extremal graph at order , whereas is not isomorphic to it. For , the tail-integral identity (3) and Lemma 2.4 give
Expanding the integrands and applying
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 , put , using open neighborhoods. Partition the vertices into equivalence classes according to equality of their open neighborhoods. If has minimum degree , let be the largest size of such a class consisting of vertices of degree .
Theorem 4.1. Let be a finite simple graph with minimum degree , and put . There is a constant such that
Proof. When the uncovered set is , a ring is successful exactly when its vertex belongs to . The total rate of the next covering and the rate at which a particular is covered are
In particular, every ordering of the vertices has positive probability of occurring as the order in which they are covered.
Equality holds precisely when is contained in a single class of degree- vertices with the same open neighborhood. Indeed, if , then every satisfies and , forcing . 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 along that order is at most . This maximum is attained by first covering all vertices outside a class of size .
Condition on a covering order . By Lemma 2.2, the holding time at each state is exponential with rate , independently of the next transition. Thus the successive holding times, conditional on , are independent. If the order contains holding times of rate , its conditional completion time is , where is a sum of independent variables and is an independent sum of exponential variables of rates greater than . Consequently
To verify this asymptotic, condition on and apply the Erlang tail formula from Lemma 2.3, namely . After division by , the highest power converges by dominated convergence with dominator , and the lower powers vanish. All rates in are integers at least , so ; this also makes the contribution from negligible. An order containing no rate- 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 is , and every order attaining it has a positive leading coefficient. This proves the result and the positivity of .
For a -regular graph write .
Corollary 4.2. Let be a finite simple -regular graph, . Then , with equality if and only if has a component. If it has exactly such components, then
In particular, is the unique connected -regular graph whose completion-time tail has a polynomial factor of degree $d-1.
Proof. Let be a class of vertices with the same open neighborhood . Every vertex of is adjacent to all of , so . If , then , , and the edges between the two classes account for every edge incident with a vertex of . Consequently, these vertices form a component. The converse is immediate.
In a component, each class must generate clock rings to cover the opposite class. These two times are independent sums of variables of distribution . Thus Lemma 2.3 gives, with
the component survival probability is
Every other component has and hence a lower-order tail by Theorem 4.1. Independence of components gives the stated coefficient.
Corollary 4.3. Fix and a positive integer divisible by , and put . For all sufficiently large , uniquely maximizes , up to isomorphism, among the -regular graphs on vertices.
Proof. If , then . Otherwise the ratio tends to , where is the number of components of . This limit equals exactly when . For every other graph the limit is strictly smaller than . Since there are only finitely many graphs on vertices, a common threshold for 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 and . For all sufficiently large divisible by , the graph uniquely maximizes , up to isomorphism, among all -regular
graphs on vertices whose components have at most vertices. More precisely, if counts the vertices lying outside components, then
for every sufficiently large admissible , uniformly over all such .
Proof. Write , , and . For each connected -regular graph of order at most , Corollary 4.2 gives . Since there are only finitely many such component types, a common can be chosen so that
for every such . Using for and for , we obtain
Put and . Multiplying component distribution functions and summing these inequalities gives
Since , the tail-integral identity (3) implies
Here the possible negative contribution before is bounded using and the monotonicity of .
Choose with . Such a point exists for , since is continuous and strictly decreasing from to . We have , and the explicit tail of gives . For all sufficiently large , the interval lies above , and on this interval
Consequently
Multiplication by , using Lemma 2.4, yields
For , the integer is positive and divisible by , so . Since , the last error tends to zero exponentially in , independently of . For all sufficiently large , it is at most , proving the asserted bound and strict extremality. When , both sides are zero. ∎
Clique unions and uniform bounds
Proposition 5.1. Fix an integer . For divisible by both and , put
As through these common multiples,
In particular, for all sufficiently large such .
Proof. Partition into the two vertex classes of each of its complete bipartite components. There are classes, each of size . A uniform vertex sample selects each class with probability . 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 classes has been sampled at least times. Thus, as discrete random variables,
Applying Theorem 2.6 gives
For a single , 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 neighbors. The strong Markov property in Lemma 2.1, applied at the time of the th covering, shows that the conditional distribution of the final waiting time is , independently of the preceding history. Consequently, its continuous completion time is , where is the sum of independent variables and is independent of . Hence
The lower bound follows from . For the upper bound, condition on and use , which remains valid when . For ,
Independence of the summands in therefore gives . Let , and let be the maximum of independent copies of . By component independence, has the same distribution as . The lower bound in (29) compares with the maximum of independent variables, whose expectation is by Lemma 2.3, where . For the upper bound, apply the union bound and integrate the resulting tail estimate to obtain
Since , Lemma 2.4 yields
For fixed , the difference between and is the constant , while . Subtracting (30) from (28) therefore proves (26).
The error term in (26) depends on the fixed degree . 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
with an absolute implied constant.
Proposition 5.2. For every integer ,
In particular, . Consequently there is no absolute constant such that for every -regular graph on vertices.
Proof. Let be the first step by which each component has received at least vertex samples. Every sample can cover at most one vertex in its own component, so . After steps, the sample count in the first component is . The deficient component still needs samples, each arriving with probability . Therefore
The last equality follows by symmetry and telescoping, using
Writing , induction gives : the initial value is , and
This proves the required lower bound. Since the graph has and , its excess above is at least , whereas .
For the upper bound, construct the following coupling. Let be independent sums of independent variables of distribution , and let be independent of them and of each other. The two clique completion times have the joint law of , while the times of the th clock ring in the two components have the joint law of . Thus
Poissonization gives
By Lemma 2.3, , 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
The weaker order estimate is compatible with this family, whose expected completion time is .
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]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]N. Alon, Problems and results in extremal combinatorics—II, Discrete Mathematics 308 (2008), 4460–4472.DOI
- [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]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]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]R. Durrett, Essentials of Stochastic Processes, third ed., Springer, Cham, 2016.
- [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]D. J. Newman and L. Shepp, The double Dixie cup problem, American Mathematical Monthly 67 (1960), 58–61.DOI
- [9]G. Fibich and T. Levin, Universal bounds for spreading on networks, Chaos 34 (2024), 053101.DOI
- [10]G. Fibich, T. Levin, and S. Schochet, Funnel theorems for spreading on networks, Chaos 35 (2025), 073109.DOI