Introduction
The d-dimensional binary hypercube Qd is the graph with vertex set {0,1}d, in which two vertices are adjacent if and only if they differ in a single coordinate. The percolated hypercube Qpd is the random subgraph of Qd obtained by retaining each edge independently with probability p. The hypercube and its random subgraphs have been studied extensively in combinatorics, probability and computer science, where they arise in a wide range of problems.
The study of the percolated hypercube Qpd was pioneered by Burtin [10] and Sapoženko [30], who showed that p=1/2 is a sharp threshold for connectivity. Results on its component structure followed. Erdős and Spencer [18] observed that, if p=c/d with c<1, then Qpd typically contains only components of order O(d). On the other hand, Ajtai, Komlós and Szemerédi [2] proved that, if p=c/d with c>1, then Qpd typically contains a connected component L1 with linearly many vertices, called the giant component. These results established that the size of the largest component of Qpd goes through a phase transition at p=(1+o(1))/d.
Bollobás, Kohayakawa and Łuczak [9] determined the size of the giant more precisely. For c>0, let y(c) denote the survival probability of a Galton–Watson process with offspring distribution Poisson(c). They proved that, if p=c/d with c>1, then typically L1 has y(c)2d+o(2d) vertices, while every other component has order O(d). Thus, in the corresponding regime, the component structure of Qpd resembles that of the binomial random graph G(n,p) [17], exhibiting the so-called Erdős–Rényi component phenomenon [14, 15].
A basic question in the study of random graphs is whether the emergence of the giant component is accompanied by the emergence of cycles of linear length. In this paper we address this question for the percolated hypercube. The circumference of a graph is the length of its longest cycle. We prove that for every sufficiently small ε>0 and p=(1+ε)/d, the circumference of Qpd is of order ε22d with high probability.
The circumference of G(n,p)
Erdős [20] conjectured that for every constant c>1, G(n,c/n) has a cycle of linear length whp. His conjecture was resolved by Ajtai, Komlós and Szemerédi [1], who showed that for any constant c>1, if p≥c/n, then G(n,p) contains a cycle of linear length whp. A weaker version of this result, covering the range c>2log2, was proved earlier by Fernandez de la Vega [19]. These results also give that the fraction of vertices missed by a longest cycle typically tends to zero as c tends to infinity. Later, Ajtai, Komlós and Szemerédi [3], and independently Bollobás [8], determined that the threshold for the existence of a Hamilton cycle in the binomial random graph equals the threshold for having minimum degree at least 2, completing the picture.
The circumference of Qpd
A folklore conjecture states that the circumference of Qpd exhibits behaviour analogous to that of G(n,p). Namely, it undergoes a phase transition near p=1/d, from logarithmic to linear in the number of vertices; it then continues to grow with the giant component, and finally Qpd becomes Hamiltonian as soon as its minimum degree reaches 2.
A breakthrough came from Condon, Espuny Díaz, Gírao, Kühn and Osthus [11], who proved the Hamiltonicity part of the conjecture. In particular, they showed that p=1/2 is the threshold for the existence of a Hamilton cycle in Qpd.
A second breakthrough came from the author together with Diskin, Erde, Kang, Krivelevich and Lichev [4], who proved the “middle” part of the conjecture in a strong form. Namely, they showed that, for every ε∈(0,1), there exists a constant c=c(ε) such that, if p≥c/d, then Qpd typically contains a cycle covering at least (1−ε)2d vertices.
In this paper, we establish the emergence of cycles of linear length just above p=1/d, showing that the circumference of Qpd indeed undergoes a phase transition near this point (see Theorem 1). This question has been reiterated over the years; see, for example, the 2014 ICM survey by Frieze [21], [16 Question 5.5], [22 Question 72], [4 Conjecture 1.2]. In this regime, by exploiting the expansion properties of linear-sized sets, Diskin, Erde, Kang and Krivelevich [13] proved that, if p=c/d for a constant c>1, then Qpd typically contains a cycle of length Ω(2d/(dlogd)). We prove that the cycle can be taken to have linear length.
Theorem 1. Let ε>0 be a sufficiently small constant. There exists a constant C>0 that is independent of ε such that, if p=p(d)=(1+ε)/d, then with high probability1 Qpd contains a cycle of length at least Cε22d.
The next theorem shows that the dependence on ε is optimal. The 2-core of a graph G is the maximal subgraph of G of minimum degree at least 2. Every cycle of G lies in its 2-core. Thus the circumference of G is at most the size of the largest component of its 2-core.
Theorem 2. Let ε>0 be a sufficiently small constant and let p=p(d)=(1+ε)/d. Then, whp the 2-core of the giant component of Qpd has size (2ε2+O(ε3))2d.
Theorem 1 settles the existence question. Theorem 2 shows why the scale ε22d is the right one near the transition. Together, the two theorems show that, for p=(1+ε)/d, where ε>0 is a sufficiently small constant, the circumference of Qpd is Θ(ε22d) whp.
Our proof uses the expansion properties of medium-sized sets and their resilience under vertex deletion. In addition, we initiate the study of structural properties of the 2-core of Qpd. We believe that these ideas could also be useful in future work.
Proof outline
Our proof combines three ingredients: a path-packing result for locally expanding graphs, a method for joining the resulting paths through successive subcubes, and expansion estimates for medium-sized sets in the 2-core.
We choose pairwise vertex-disjoint subcubes G0′ and G1′,…,Gk′ of Qd. The initial subcube has dimension d−2, while each of the remaining subcubes has dimension d−O(1). Consecutive subcubes Gj−1′ and Gj′ are joined by a perfect matching Mj in Qd for j≥2, and G0′ is joined to G1′ by a set of pairwise disjoint paths. For 0≤j≤k, let Gj be the subgraph of Qpd induced by V(Gj′).
We first find vertex-disjoint paths of at least medium length in the 2-core of the giant component of G0 that cover a linear number of vertices. We then join these paths into a single cycle using the subsequent graphs G1,…,Gk and the matching edges retained in Qpd. Here, “medium” means exponential in d, with a small positive exponent depending on ε. Working in the 2-core at the packing stage gives the optimal dependence on ε.
Finding the paths. This part of the proof uses a variant of a result of Krivelevich [27], which gives a long cycle from local expansion. We take a maximal family of vertex-disjoint cycles of at least medium length and remove their vertices. The remaining graph contains no further cycle of this length. The same result then implies that any component larger than the chosen scale contains a poorly expanding almost connected set of medium size. We successively remove such sets until all remaining components are small. Removing one edge from each of the original cycles gives the required paths.
The goal is now to show that the vertices outside the paths cannot greatly outnumber those on the paths. Each set removed in the second stage expands in the original graph, but has only a small neighbourhood in the graph remaining at the time of its removal. Thus, many of its neighbours must lie on the paths or in sets removed earlier. Using the accompanying bounds on the number of edges incident with these sets, a double-counting argument shows that the sets removed in this stage together contain at most a constant multiple of the number of vertices on the paths.
It remains to control the components left after these removals. We divide them into those with good expansion and those with poor expansion, measured in the original graph. All their external neighbours lie on the paths or in the removed sets. For the components with good expansion, counting the edges between these components and the removed vertices bounds their total order in terms of the number of removed vertices. On the other hand, too many poorly expanding components would allow us to combine a suitable collection of them with a segment of a single cycle or a single set of removed vertices to form an almost connected set. Most of its vertices would come from the poorly expanding components. The upper neighbourhood bound then gives a poorly expanding set, contradicting expansion in the original graph. Together, these comparisons show that the paths cover a positive proportion of the base graph. Applied to the 2-core, this gives the paths needed for the next step.
Joining the paths. Let P1,…,Pt be the resulting paths. For each Pi, we choose sets Si+ and Si− in its first and last thirds, respectively. We choose these sets so that each of their vertices is connected to its projection in the first auxiliary subcube along a retained path, and then to its projection in the subsequent subcubes along retained matching edges. In addition, its projection in each Gj belongs to the giant component of Gj. We may take all the sets to have the same size s, which is exponentially large in d. Their projections into the subsequent subcubes form the terminal sets through which we join the original paths.
In each round, we work in the next giant component and choose a maximal family of vertex-disjoint short paths joining the available terminal sets. These paths avoid the unused terminal sets and do not close a cycle before all the original paths have been joined. After deleting their vertices, we divide the terminal sets still to be joined into two roughly equal groups, and let U1 and U2 be their unions. If sets of size at least min{∣U1∣,∣U2∣} still expand sufficiently in the remaining graph, then we can find another short path between U1 and U2, contradicting maximality.
Thus the number of vertices in terminal sets still to be joined is controlled by the number of vertices already used. Comparing this deletion cost with the expansion of the giant component shows that, if all relevant sets of size at least min{∣U1∣,∣U2∣} initially expand by a factor of, say, 1/d2, then the number of deleted vertices is larger than min{∣U1∣,∣U2∣}/2d2; otherwise, enough expansion remains to find another connection. Consequently, at each round the number of remaining terminal sets decreases by a factor of order s/dO(1). Since s is exponentially large in d, only O(d/logs) rounds are needed. Choosing k sufficiently large, we obtain a cycle retaining a third of the vertices on the original paths, and hence of linear length.
Why the 2-core. The fraction of vertices covered in the first step, and hence retained on the cycle, is bounded below by a multiple of the ratio between the lower bound on vertex expansion and the upper bound on edge expansion of medium-sized almost connected sets. Taking the base graph to be the giant of Qpd gives a cycle covering a Θ(ε2) fraction of the vertices of L1, and thus of length Θ(ε22d) (see [13, 5] for the expansion properties of L1).
To obtain the optimal dependence on ε, we instead work with the 2-core of the giant. Theorem 6 shows that the corresponding ratio is bounded below by a constant. Thus, the resulting cycle retains a constant proportion of the vertices of the 2-core. Then, Theorem 2 gives that the 2-core typically has size Θ(ε22d), yielding a cycle of the desired length Θ(ε22d).
Plan of the paper
In Section 2, we introduce the notation and collect the preliminary results. Section 3 states the main ingredients and uses them to prove Theorem 1. Sections 4 and 5 prove the packing and joining results, respectively. Section 6 establishes the size and expansion estimates for the 2-core, including Theorem 2.
Notation and Preliminaries
Given a graph G=(V,E), for A,B⊆V, we write eG(A,B) for the number of edges with one endpoint in A and one in B, with edges inside A∩B counted twice. We write NG(A) for the set of vertices in V∖A with a neighbour in A, G[A] for the subgraph induced by A, and eG(A):=∣E(G[A])∣. For S⊆V(G), we say that S is connected in G if G[S] is connected. We say that S is almost connected in G if it is connected in G, or if G[S∪{v}] is connected for some v∈V(G)∖S. A path P⊆G is bare in G if all of the internal vertices of P have degree two in G.
We omit the dependence on the base graph when it is clear from the context.
We also use the giant-component result recalled in the introduction: for fixed c>1, the largest component of Qc/dd has (y(c)+o(1))2d vertices, and every other component has order O(d), whp [9]. Here y(c)>0 is the survival probability of a Galton–Watson process with offspring distribution Poisson(c).
Throughout the paper, we omit rounding signs whenever this does not affect the validity of our arguments. We use standard asymptotic notation, with subscripts for dependencies of implicit constants. All logarithms without a subscript are natural logarithms. We also assume that d and 1/ε are sufficiently large for the calculations below to hold.
Auxiliary graph-theoretic results
We start with a bound on the number of rooted trees in a graph of given maximum degree.
Lemma 2.1 ([7], Lemma 2). Let G be a graph with maximum degree Δ, let v∈V(G) and k≥1 be an integer. Let t(v,k) be the number of rooted trees in G which have root v and k vertices. Then,
t(v,k)≤(k−1)!kk−2Δk−1≤(eΔ)k−1.
Next, we state Harper’s edge-isoperimetric inequality for hypercubes, see [25] and also [6, 26, 28].
Lemma 2.2. For every integer d≥1 and for every set S⊆V(Qd),
e(S,V(Qd)∖S)≥∣S∣(d−log2∣S∣).
Concentration inequalities
We use the following version of the Chernoff bound for binomial random variables (see, for example, Section 21.4 of [23]).
Theorem 3 (Chernoff bound). For a binomial random variable X and any t∈[0,E[X]],
Pr[∣X−EX∣≥t]≤2exp(−3E[X]t2).
We will also use McDiarmid’s inequality, stated below (see Theorem 1 of [29]).
Theorem 4. Let n≥1 be an integer, C>0, and f:{0,1}n→R be such that if x,x′∈{0,1}n differ only in a single coordinate, then ∣f(x)−f(x′)∣≤C. Let X1,…,Xn be independent Bernoulli random variables. Let X=f(X1,…,Xn). Then, for any t≥0 we have that
Pr[∣X−EX∣≥t]≤2exp(−C2n2t2).
Auxiliary results on percolation
We first recall the standard approximation to y(1+ε), the survival probability of a Galton–Watson process with offspring distribution Poisson(1+ε), for sufficiently small ε>0 (see, for example, [24]). The same approximation applies to offspring distribution Binomial(d,(1+ε)/d) for sufficiently large d.
Lemma 2.3. Let ε>0 be a sufficiently small constant. Then, y(1+ε)=2ε+O(ε2).
The following lemma records expansion properties of the giant component.
Lemma 2.4. Let ε>0 be a sufficiently small constant and p=p(d)=(1+ε)/d. Whp the giant component L1 of Qpd has order (2ε+O(ε2))2d and the following property. For every set S⊆V(L1) of size ∣S∣≤2∣V(L1)∣/3 we have ∣NL1(S)∣≥∣S∣/d2. Finally, whp the second largest component of Qpd has order less than d2.
Proof. The bound on the second largest component and the estimate on ∣V(L1)∣ follow from [9]. For the expansion bound, [5], Corollary 6.3 implies that whp for every set S⊆V(L1) of size ∣S∣≤2∣V(L1)∣/3 we have eL1(S,V(L1)∖S)≥∣S∣/(dloglogd). The probability that Qpd has a vertex of degree larger than t=2d/logd is at most
2d(td)pt≤2d(tepd)t=2de−(1+o(1))tlogt=o(1).
Combining these two bounds gives that whp for every set S⊆V(L1) of size ∣S∣≤2∣V(L1)∣/3 we have ∣NL1(S)∣≥(∣S∣/(dloglogd))/(2d/logd)≥∣S∣/d2, which completes the proof. □
The expansion bound in the lemma above also controls the components outside the 2-core and the bare paths within it.
Corollary 2.5. Let ε>0 be a sufficiently small constant and p=p(d)=(1+ε)/d. Let C2 be the 2-core of the giant component L1 of Qpd. Then, whp every component of Qpd−V(C2) has at most d3 vertices and every bare path of C2 has at most d3−3 vertices.
Proof. First, suppose that Qpd−V(C2) contains a component C of order larger than d3. Then, Lemma 2.4 implies that C⊆L1. Since C does not intersect C2, it is acyclic and NL1(C)⊆C2 contains at most one vertex. Therefore, there exists a subtree T of C of order ∣V(T)∣∈[d3,d4+1] that has at most one neighbour in L1. Lemma 2.4 implies that this occurs with probability o(1).
Now suppose that C2 contains a bare path on at least d3−3 vertices. Let C be the subgraph of L1 consisting of d3−5 consecutive internal vertices along with the trees in L1−V(C2) attached to them. In the event that no such tree has order larger than d3, C has order in [d3−5,d7] and has at most two external neighbours in L1 (which also belong to C2). Lemma 2.4 implies that this occurs with probability o(1). □
The next lemma estimates the probability that a given vertex belongs to a sufficiently large component, and that its neighbourhood reaches a prescribed size.
Lemma 2.6. Let ε>0 be sufficiently small and p=p(d)=(1+ε)/d. Let r∈V(Qd). Then,
Pr(the component of r in Qpd has at least ε−6 vertices)=2ε+O(ε2).(1) and
Pr(there are at least d20 vertices at distance at most log2d from r in Qpd)=2ε+O(ε2).(2) Proof. Let Tr be the component of r in Qpd. Let ε−6≤i<d2. By Lemma 2.1, the number of i-vertex trees in Qd containing r is at most (ed)i−1. Lemma 2.2 gives that a connected set on i vertices spans at most (ilog2i)/2 edges, so it has at least (1+o(1))di edges leaving it. Hence,
Pr(∣V(Tr)∣=i)≤(ed)i−1pi−1(1−p)(1+o(1))di≤(epde−(1+o(1))pd)i ≤exp((1+log(1+ε)−(1+o(1))(1+ε))i)≤exp(−ε2i/10). It follows that ∣V(Tr)∣∈[ε−6,d2) with probability at most O(ε2). Lemma 2.4 implies that Tr has at least d2 vertices with probability 2ε+O(ε2). (1) follows.
To prove (7), for i≥0 let Si be the set of vertices at distance i from r in Qpd, and let S<i:=⋃j=0i−1Sj. In the event that ∣Si∣≤ε4∣S<i∣, and log3/2d≤∣S<i∣≤d20, there is a tree rooted at r (of depth i) in Qpd with log3/2d≤k≤2d20 vertices, of which at most 2ε4k vertices have a neighbor outside this set. Lemma 2.2 implies that its vertex set spans at most (klog2k)/2 edges of Qd. By Lemma 2.1, this occurs with probability at most
k=log3/2d∑2d20(ed)k−1pk−1(2ε4kk)(1−p)(k−2ε4k)d−klog2k ≤k≥log3/2d∑((edp)(2ε4e)2ε4e−(1−O(ε4))dp)k≤k≥log3/2d∑((2ε4e)2ε4e1+log(1+ε)−(1−O(ε4))(1+ε))k ≤k≥log3/2d∑((2ε4e)2ε4e−ε2/4)k=k≥log3/2d∑((2ε4e)2ε2e−1/4)ε2k=o(d−1). Lemma 2.4 implies that ∣S<log3/2d∣≥log3/2d with probability at least 2ε+O(ε2). The preceding bound gives
∣S<log2d∣≥min{d20,(1+ε4)log2d−log3/2d(log3/2d)}=d20 with probability at least 2ε+O(ε2). On the other hand Lemma 2.4 implies that Tr has at most d2 vertices with probability at least 1−2ε+O(ε2), hence it has at least d20 vertices with probability at most 2ε+O(ε2). This completes the proof of (2). □
The last lemma of the section is part of [5 Lemma 7.7] and will be used later in the proof of Theorem 1.
Lemma 2.7. Let c>1 be constant and let p=c/d. Whp every vertex v∈V(Qd) is within distance two in Qd from a vertex of the giant component L1 of Qpd.
Proof of Theorem 1
We use three results, whose proofs are given in § 4–§ 6. The first yields a family of vertex-disjoint cycles, the second joins the resulting paths into a cycle, and the third gives the expansion estimates for the 2-core needed to obtain the optimal dependence on ε and d.
Theorem 5 implies, by removing one edge from each cycle, that if every medium-sized almost connected set in a graph G has suitable expansion properties, then there exists a family of pairwise vertex-disjoint medium-length paths that covers a large proportion of V(G).
Theorem 5. Let k≥1 be an integer, 0<c≤C, and I be the interval [Imin,Imax], where Imin=min{ck/10,ck/10C} and Imax=max{10Ck/c,10Ck}. Let G be a connected graph on more than k vertices such that every almost connected set W⊆V(G) with ∣W∣∈I satisfies the following properties:
(P1) c∣W∣≤∣N(W)∣≤C∣W∣, and
(P2) for every Z⊆N(W) we have that e(W,Z)≤∣Z∣+c2k/10.
Let ℓ:=ck/10. If 2<ℓ, then G contains a family of pairwise vertex disjoint cycles of length at least ⌈ℓ⌉, covering at least
71(Cc)∣V(G)∣ vertices.
In the proof of Theorem 1, we work with a sequence of vertex-disjoint subcubes H0,…,Hk⊆Qd. We first apply Theorem 5 to find vertex-disjoint paths in the percolated subgraph of H0. We then connect them successively through H1,…,Hk until we obtain a single cycle covering at least a third of their vertices. The connections use projections of selected vertices in the first and last thirds of the paths. We call these projected sets terminal sets. Proposition 3.1 implies that this is possible when the graph sequence is sufficiently long and the graphs used for joining have suitable expansion properties. To keep track of the length retained as paths are joined, we use marked trees. Given a graph G, a marked tree is a triple B=(T,S1,S2) where T⊆G is a tree, S1,S2⊆V(T) are non-empty, and S1∩S2=∅. We call S1,S2 the terminal sets of B. The length of a marked tree B=(T,S1,S2), denoted by d(B), is defined to be
d(B):=min{dT(x,y):x∈S1, y∈S2}.
We say that the marked trees B=(T,S1,S2) and B′=(T′,S1′,S2′) are disjoint if the trees T and T′ are vertex disjoint.
Proposition 3.1. Let n,ℓ,k,r,d,s≥1 be integers. Let G be an n-vertex graph, and let G0,G1,…,Gk be pairwise vertex-disjoint subgraphs of G. For ∗∈{+,−}, i∈[r] and j∈{0,1,…,k}, let Si,j∗⊆V(Gj) be of size ∣Si,j∗∣=s, and assume that all these sets are pairwise disjoint. Suppose that the following conditions hold.
(a) There are pairwise vertex-disjoint trees T1,…,Tr⊆G0 such that for i∈[r] we have that Bi0=(Ti,Si,0+,Si,0−) is a marked tree of length at least ℓ.
(b) G contains a perfect matching Mi,j∗ between Si,j∗ and Si,j+1∗, for every ∗∈{+,−}, i∈[r], and j∈{0,…,k−1}.
(c) For every j∈[k] and every A⊆V(Gj) if ∣A∣≤2∣V(Gj)∣/3, then ∣NGj(A)∣≥∣A∣/d2.
Let β:=100d4logn/s. If βk<1/r, then G contains a cycle of length at least ∑i∈[r]d(Bi).
Remark 3.2. In Proposition 3.1, if β=1/s1−o(1) and k is a constant, then the condition βk<1/r can be replaced by the condition sk>n. This follows from the observation that the disjointness of the sets Si,j∗ implies that r<n/s.
In Proposition 3.1, β bounds the proportion of marked trees that remain after one round. After k rounds, either a cycle has been formed or at most βkr<1 marked trees remain. The latter is impossible, giving the required cycle.
The next theorem states the expansion properties of the 2-core of the giant component of Qpd that we will use in the application of Theorem 5.
Theorem 6. Let ε>0 be a sufficiently small constant and let p=p(d)=(1+ε)/d. Let
α=α(ε):=ε1/ε20,m=m(ε,d):=ε2⋅2αd,andM=M(ε,d):=ε−2⋅2αd. Let C2 be the 2-core of the giant component of Qpd. Whp every connected set S⊆V(C2) in C2 with size m≤∣S∣≤M+1 satisfies the following:
ε∣S∣/4000≤∣NC2(S)∣≤2000ε∣S∣, and
for every Z⊆NC2(S) we have that eC2(S,Z)≤∣Z∣+ε8⋅2αd.
Proof of Theorem 1. Let p1=(1+2ε/3)/d. We couple Qp1d and Qpd such that Qp1d⊆Qpd. Let α=α(ε):=ε1/ε20 be as in the statement of Theorem 6, and let k:=⌈2/α⌉, h:=⌈log2(k+1)⌉ and D:=d−h−2. Let H0⊆Qd be the (d−2)-dimensional hypercube obtained by fixing the first 2 coordinates to 1,1. Let H1,…,Hk⊆Qd be vertex-disjoint hypercubes of dimension D, obtained by fixing the first h+2 coordinates, with the first 2 fixed to 0,0. Order them so that, for 1≤j<k, Hj is connected to Hj+1 by a perfect matching Mj in Qd. In addition, the fixed coordinates in H1 are all 0. Let G0:=Qpd[V(H0)], and for j∈[k] let Gj−:=Qp1d[V(Hj)] and Gj:=Qpd[V(Hj)], thus Gj−⊆Gj.
Finding the paths in the 2-core of G0. Let E be the event that the following are satisfied.
(P1) The 2-core of G0 has a component of order (2ε2+O(ε3))2d−2, denoted by C2, that satisfies the expansion properties described in Theorem 6.
(P2) For j∈[k], Gj− has a component Lj− such that every vertex in V(Hj) is within distance at most 2 from V(Lj−) in Hj.
Theorems 2, 6 and Lemma 2.7 imply that E holds whp. We reveal G0 and the graphs Gj−, for j∈[k], and assume that E occurs. Observe that adding a vertex to an almost connected subset of Qd so that it becomes connected changes its vertex and edge boundaries by at most d. Thus (P1) gives that every almost connected set S⊆V(C2) in C2 with size m≤∣S∣≤M satisfies the following:
∣NC2(S)∣≥ε∣S∣/4000−d≥ε∣S∣/5000,
∣NC2(S)∣≤2000ε(∣S∣+1)+1≤2001ε∣S∣, and
for every Z⊆NC2(S) we have eC2(S,Z)≤∣Z∣+ε42αd+d.
Applying Theorem 5 with k=2αd, c=ε/5000 and C=2001ε and then removing an edge from each cycle gives that, for some constant A>0, there is a family of vertex-disjoint paths, each of length at least ε22αd, spanning in total at least Aε22αd vertices. Choose such a family P1,…,Pr in G0, and orient each path.
Choosing terminals and joining the paths. Let q=1/(dlogd)2. For every j∈[k], every edge e∈E(Hj) and every vertex v∈V(Hj) within distance at most one from an endpoint of e, generate a variable Ye,v∼Bernoulli(q). All these variables are mutually independent and independent of Qp1d and G0,G1−,…,Gk−. There are 2D≤2d eligible vertices for each edge. For e∈⋃j=1kE(Hj), add e to ⋃i∈[k]Gi− if at least one of its 2D associated variables is 1, and let G be the resulting graph. The edges of G are independent, each present with probability pG≤p1+2Dq<p. Thus we can couple these graphs so that Gj−⊆G[V(Hj)]⊆Gj⊆Qpd[V(Hj)] for every j∈[k].
For j∈[k] and v∈V(Hj) let P(v) be a path of length at most 2 from v to Lj− in Hj. Such a path exists in the event E by (P2). For v∈V(H0), let vj be its projection to Hj, and let Yv∼Bernoulli(1/d), independently for all such v and of all other variables. Let P(v) be the path from v to v1 obtained by changing its non-zero coordinates among the first h+2 coordinates from 1 to 0, changing its second coordinate first and its first coordinate last. Thus all intermediate vertices start with (1,0). Call v successful if the following are satisfied.
(P1) E(P(v))⊆E(Qpd), and all of the edges of the form vivi+1 are retained in Qpd for 1≤i<k,
(P2) Ye,vj=1 for j∈[k] and e∈E(P(vj)), and
(P3) Yv=1 and there does not exist a vertex u=v such that u and v differ only on their first h+2 coordinates with Yu=1.
Then, each vertex v∈V(H0) is successful with probability at least ph+2+(k−1)⋅q2k⋅d−1(1−d−1)2h+2≥d−8k. In addition, each edge and each Bernoulli random variable associated with an edge or vertex can affect the success of at most 2h+2 such vertices. McDiarmid’s inequality (see Theorem 4) gives that whp for 1≤i≤r there exist sets Si,0+ and Si,0− of successful vertices, each of size Aε22αd⋅d−8k/10 chosen from the first and last ∣V(Pi)∣/3 vertices of Pi, respectively.
Let E+ be the event that the following are satisfied.
(Q1) The sets Si,0+, Si,0−, described above, exist for i∈[r].
(Q2) For j∈[k], the second largest component of Gj has at most d2 vertices and its largest component, denoted by Lj, satisfies the following property. For every set S⊆V(Lj) of size ∣S∣≤2∣V(Lj)∣/3 we have that ∣NLj(S)∣≥∣S∣/d2.
The preceding argument and Lemma 2.4 imply that E+ occurs whp. We reveal the remaining randomness and assume that E+ occurs. For i∈[r], j∈[k], and ∗∈{+,−} let Si,j∗ be the projection of Si,0∗ in Gj. In the event E+, (P2) implies that the set Si,j∗ lies in the component of Gj containing Lj−. Since ∣Si,j∗∣>d2 and, by (Q2), the second largest component of Gj has order at most d2 it follows that Si,j∗ lies in Lj. In addition, by (P1), for 2≤j≤k, Si,j∗ is connected to Si,j−1∗ via a matching in Qpd. For 1≤i≤r take Ti to be the tree obtained by taking the union of the path Pi and the paths P(v) for v∈Si,0+∪Si,0−. (P1) implies that Ti⊆Qpd. Then, (P3) implies that the three Ti, i∈[r] are vertex disjoint, as are the projected terminal sets in each subcube. This gives a set of vertex disjoint marked trees Bi0=(Ti,Si,1+,Si,1−) each of length at least Aε22αd/3. Let L1+ be the union of L1 and these marked trees.
Applying Proposition 3.1 (see also Remark 3.2) with k−1 rounds to L1+ and the giants L2,…,Lk with s=2αd−Oε(logd) and k=⌈2/α⌉ implies that Qpd spans a cycle of length at least Aε22d/3, completing the proof.
Proof of Theorem 5
We use the following variant of Krivelevich’s result on long cycles in locally expanding graphs (Theorem 1 of [27]).
Proposition 4.1. Let h≥1, and r≥2. Let G be a connected graph on more than h vertices satisfying:
∣N(W)∣≥r, for every almost connected W⊆V(G) with h/2≤∣W∣≤h. Then G contains a cycle of length at least r+1.
Proof. Fix v∈V(G), and let Tv be a depth-first search (DFS) tree of G rooted at v. By Proposition 2.1 of [27], there exist a vertex u and a set X of children of u in Tv such that, if W denotes the union of the subtrees rooted at the vertices of X, then h/2≤∣W∣≤h. The set W is almost connected, with witness u. Let Pv,u be the v–u path in Tv. By the ancestor–descendant property of DFS (Proposition 2.2 of [27]), every external neighbour of W lies on Pv,u; hence NG(W)⊆V(Pv,u). By the hypothesis, ∣NG(W)∣≥r. Let a be the vertex of NG(W) closest to v in Tv and let b∈W be adjacent to a. The a–b path in Tv contains all the vertices of NG(W) and at least one vertex of W. Adding the edge ab therefore gives a cycle with at least ∣NG(W)∣+1≥r+1 vertices.
We now pass from a single cycle to a packing that covers a positive proportion of the graph, proving Theorem 5. For the proof outline, see § 1.3.
We now prove Theorem 5. For a sketch of its proof see § 1.3.
Proof of Theorem 5. Let h:=max{k,ck}. Let C1,…,Ct be a maximal family of vertex-disjoint cycles, each of length at least ⌈ℓ⌉ in G. Note that (P1) implies that ∣N(W)∣≥ℓ for every almost connected W⊆V(G) with k/2≤∣W∣≤k. Thus, Proposition 4.1 implies that G has at least one cycle of length at least ⌈ℓ⌉, so t≥1. For i∈[t] let
Si:=V(Ci).
We now define pairwise disjoint subsets St+1,St+2,… of V(G) recursively. For i≥t+1, given the sets St+1,…,Si−1, let S≤i−1:=⋃j=1i−1Sj and Si be an almost connected subset of V(G)∖S≤i−1 satisfying
∣Si∣∈[h/2,h],and∣N(Si)∖S≤i−1∣<ℓ.(3)
If no such set exists, then set Si=∅ and stop. We let τ be the largest index i such that Si=∅. Let
S:=S≤τ,S−:=S≤t,andU:=V(G)∖S.
By maximality of the cycle family C1,…,Ct, G[U] contains no cycle of length at least ⌈ℓ⌉. Since Sτ+1=∅, every almost connected set X⊆U with h/2≤∣X∣≤h satisfies ∣NG[U](X)∣=∣NG(X)∖S∣≥ℓ. If a component Q of G[U] had more than h vertices, then every set that is almost connected in Q is also almost connected in G, and its neighbourhood in Q equals its neighbourhood in G[U]. Hence, Proposition 4.1 yields a cycle of length at least ⌈ℓ⌉ in Q, contradicting the maximality of C1,…,Ct. Thus every component of G[U] has at most h vertices.
Partition the components of G[U] according to their neighbourhoods in G, into A1,A2,…,Ax and B1,B2,…,By, where
∣NG(Ai)∣≥c∣Ai∣/2 for i∈[x]and∣NG(Bi)∣<c∣Bi∣/2 for i∈[y].
Assign each poorly expanding component to the last removed set it meets: for j∈[y] let σ(j) be the maximum index i∈[τ] such that Bj is incident to Si. Such an index exists since G is connected and S=∅. For i∈[τ] let Ti:=Si∪⋃j:σ(j)=iBj, and let
A:=i=1⋃xAi,T:=i=1⋃τTi,T−:=i=1⋃tTi.
Then V(G)=T+(T∖T−)⊎A.
Claim 4.2. The following inequalities hold.
∣T−∣≤(c2C)∣S−∣.(4) ∣T∖T−∣+∣A∣≤(c5C)∣S−∣.(5)
Proof. First we prove that ∣Ti∣≤2(C/c)∣Si∣ for i∈[τ]∖[t]. Indeed, assume otherwise. Since every Bj has at most h vertices, there is a subset ϕ(i)⊆σ−1(i) such that Ti′:=Si∪⋃j∈ϕ(i)Bj has size in [2(C/c)∣Si∣,2(C/c)∣Si∣+h]⊆[(C/c)h,2(C/c)h+h]⊆[(C/c)h,3(C/c)h]⊆I. The set Ti′ is almost connected, since each selected component is incident to Si. Thus (P1) gives ∣NG(Ti′)∣≥c∣Ti′∣. But
∣NG(Ti′)∣≤∣NG(Si)∣+j∈ϕ(i)∑∣NG(Bj)∣<C∣Si∣+2c∣Ti′∣≤c∣Ti′∣,
a contradiction.
The same argument applies to any connected segment R of a cycle with ck/10≤∣R∣≤h, together with any of the Bj assigned to that cycle and incident to R. Partition each Ci, i∈[t], into consecutive segments with between ck/10 and ck vertices. This is possible since ∣Ci∣≥ck/10. Assign each Bj with σ(j)=i to one segment incident to it. Applying the preceding argument to each segment and its assigned components, and summing, gives ∣Ti∣≤2(C/c)∣Si∣ also for i∈[t]. Summing over i∈[t] gives (4).
To prove (5), let m be the number of edges from S− to V(G)∖S−. First, for each of the cycle segments R above, (P1) and (P2) give that eG(R,V(G)∖R)≤C∣R∣+c2k/10≤C∣R∣+c∣R∣≤2C∣R∣. Consequently, summing over the segments gives
m≤2C∣S−∣.(6)
For i>t, let T<i:=⋃j<iTj, T>i:=⋃j>iTj and S<i:=S≤i−1. Counting edges between earlier and later parts gives
m≥eG(S−,(T∖T−)∪A)≥i=t+1∑τeG(Ti,T<i)+eG(A,S)−i=t+1∑τeG(Ti,T>i∪A).
Now, since Ti is almost connected and ck/10≤∣Ti∣≤2C∣Si∣/c≤2Ch/c, (P1) applies to Ti. By the definition of σ, every neighbour of a component assigned to Ti lies in S≤i. Thus (3) gives
eG(Ti,T<i)≥∣NG(Ti)∩T<i∣≥c∣Ti∣−∣N(Si)∖S<i∣≥c∣Ti∣−10ck≥54c∣Ti∣.
Also, (P2) and (3) give
eG(Ti,T>i∪A)=eG(Si,T>i∪A)≤eG(Si,N(Si)∖S<i)≤10ck+10c2k≤52c∣Si∣≤52c∣Ti∣.
Finally, the Ai are components of G[U], so
eG(A,S)=i=1∑xeG(Ai,S)≥i=1∑x∣NG(Ai)∣≥2c∣A∣.
Combining the above inequalities gives
2C∣S−∣≥i=t+1∑τeG(Ti,T<i)+eG(A,S)−i=t+1∑τeG(Ti,T>i∪A)≥i=t+1∑τ54c∣Ti∣+2c∣A∣−i=t+1∑τ52c∣Ti∣≥52c(∣A∣+∣T∖T−∣).
Rearranging the above inequality gives (5).
(4) and (5) give that ∣V(G)∣=∣T−∣+∣T∖T−∣+∣A∣≤7C∣S−∣/c. Thus C1,…,Ct cover at least (1/7)(c/C)∣V(G)∣ vertices, completing the proof.
Proof of Proposition 3.1
For a sketch of the proof of Proposition 3.1, see Section 1.3. We first analyze one round, comparing the number of vertices used by the connecting paths with the expansion available to the unused terminal sets.
Lemma 5.1. Let n,d,s≥1, and r≥2 be integers. Let G be an n-vertex graph, and let S1,…,S2r⊆V(G) be pairwise disjoint sets of size s. Assume that
∣NG(A)∣≥d2∣A∣for every A⊆V(G) with ∣A∣≤2n/3.(7) Let M be a perfect matching on the set [2r]. Let M+ be the set of matchings M+ on [2r] satisfying the following conditions.
(I) M+ is a matching on [2r] that is edge disjoint from M, and the graph ([2r],M∪M+) is either a Hamilton cycle or acyclic.
(II) There is a family of vertex-disjoint paths P={Pxy:xy∈M+} such that, for every xy∈M+, the path Pxy is an Sx-Sy path in G of length at most
L:=20d2logn−1. In addition, with U:=⋃P∈PV(P), we have that U∩Sz=∅ for every z∈[2r]∖V(M+), i.e. the paths in P avoid every set Sz such that z is not matched by M+.
Let M+∈M+ be of maximum cardinality. If ([2r],M∪M+) is not a Hamilton cycle, then
r−∣M+∣≤s100d4lognr.(8)
Proof of Lemma 5.1. Let M+∈M+ have maximum cardinality, and let
Γ:=([2r],M∪M+),m:=∣M+∣,q:=r−m.
If Γ is a Hamilton cycle, then ∣M+∣=r and (8) holds trivially. Otherwise, condition (I) implies that Γ is acyclic. Since M is a perfect matching and M+ is a matching, every vertex in Γ has degree 1 or 2. Hence every component of Γ is a path of length at least 1. Consequently, the number of components of Γ is ∣V(Γ)∣−∣E(Γ)∣=2r−(r+m)=q.
Let X be the set of endpoints of the components of Γ. Since M is a perfect matching, these endpoints are precisely the vertices not covered by M+; that is, X=[2r]∖V(M+). In particular, ∣X∣=2q≥2. We partition these endpoints so that an edge across the two parts either joins distinct path components or closes the final cycle. If q=1, then Γ is a Hamilton path, and we let X+ and X− be singleton sets containing its two distinct endpoints. If q≥2, let X+ be the set of endpoints of ⌊q/2⌋ components of Γ, and let X−:=X∖X+. In both cases, X=X+⊎X−, with ∣X+∣,∣X−∣≥2q/3, and, for every x+∈X+ and x−∈X−, the graph Γ+{x+x−} is either a Hamilton cycle or acyclic.
Since M+∈M+, there exists a family P={Pxy:xy∈M+} of vertex-disjoint paths of length at most L such that, for every xy∈M+, the path Pxy⊆G has one endpoint in Sx and the other in Sy, and its vertex set avoids Sz for every z∈[2r]∖V(M+). Let U:=⋃xy∈M+V(Pxy). Then
∣U∣≤m(L+1)=20d2mlogn≤20d2rlogn,(9)
where the last inequality follows from m=∣M+∣≤r.
For ∗∈{+,−}, let S(X∗):=⋃i∈X∗Si. Also let S(X)=S(X+)∪S(X−). Since X=[2r]∖V(M+), the choice of P gives
∣S(X∗)∣≥32qsandS(X∗)∩U=∅.(10)
Suppose, for a contradiction, that (8) fails; that is, q=r−m>r(100d4logn)/s. We show that the remaining terminal sets can still be joined by a short path avoiding U. First, by the expansion hypothesis and (9), for every W⊆V(G)∖U with 2qs/3≤∣W∣≤2n/3, we have
∣NG−U(W)∣=∣NG(W)∖U∣≥d2∣W∣−20d2rlogn≥d2∣W∣−5d2qs≥2d2∣W∣.(11)
We now grow neighbourhoods in G−U from the two groups of terminals. Let S0−:=S(X−) and, for i≥1, define Si−:=NG−U(Si−1−)∪Si−1−. Since 2qs/3≤∣S0−∣≤∣Si−1−∣, (11) implies that, if ∣Si−1−∣<2n/3, then
∣Si−∣=∣NG−U(Si−1−)∣+∣Si−1−∣≥(1+2d21)∣Si−1−∣.
It follows by induction that, with t:=⌊L/2⌋,
∣St−∣≥min{(1+2d21)t∣S0−∣,32n}≥min{(1+2d21)t,32n}=32n.
Indeed, since 0≤1/(2d2)≤1, the inequality log(1+x)≥x−x2/2≥x/2 gives
(1+2d21)t=exp(tlog(1+2d21))≥exp(4d2t)≥exp(logn)=n.
For the penultimate inequality, note that n≥2rs≥4 and hence t=⌊L/2⌋≥10d2logn−3/2≥4d2logn.
Defining Si+ analogously gives ∣St+∣≥2n/3. Hence St+∩St−=∅. Let v∈St+∩St−. Then there is an S(X+)–v path of length at most t and a v–S(X−) path of length at most t, both in G−U. Their concatenation contains an S(X+)–S(X−) path P of length at most 2t≤L.
Let P′ be a shortest subpath of P with one endpoint in S(X+) and the other in S(X−). Denote its endpoints by u+ and u−, and let x+∈X+ and x−∈X− be the unique indices such that u+∈Sx+ and u−∈Sx−. By the minimality of P′, its vertex set is disjoint from S(X)∖{u+,u−}. Indeed, if an internal vertex of P′ belonged to S(X+) or S(X−), then an appropriate proper subpath of P′ would be a shorter S(X+)–S(X−) path.
By construction, Γ+{x+x−} is either a Hamilton cycle or acyclic. The edge x+x− is not in M: if q≥2, then x+ and x− lie in distinct components of Γ, while if q=1, they are the endpoints of a Hamilton path on 2r≥4 vertices. Moreover, x+ and x− are not covered by M+, so M+∪{x+x−} is a matching edge-disjoint from M. Thus condition (I) holds. Since P′⊆G−U, the set P∪{P′} is a family of vertex-disjoint paths. Furthermore, both U and V(P′) are disjoint from Sz for every z∈X∖{x+,x−}, so this enlarged family also satisfies condition (II). Therefore, M+∪{x+x−}∈M+, contradicting the maximality of M+. Hence (8) holds. □
Proof of Proposition 3.1. Let ℓ=∑i∈[r]d(Bi). Re-index the sets so that Si,j=Si,j+ and Si+r,j=Si,j− for i∈[r] and j∈{0,1,…,k}, and re-index the matchings in the same way. We prove by induction on j∈{0,1,…,k} the following statement, denoted by P(j). Either G contains a cycle of length at least ℓ, or there is a family of at most βjr pairwise disjoint marked trees in G, with all vertices in ⋃i=0jV(Gi), and with terminal sets in {Si,j:i∈[2r]} whose total length is at least ℓ.
The base case P(0) follows from condition (a) by taking B0={(Ti,Si,0,Si+r,0):i∈[r]}.
Let 0≤j<k and assume that P(j) holds. If its first alternative holds, there is nothing to prove. Otherwise, let Bj={Bi=(Ti,Sai,j,Sbi,j):i∈[t]}.
We first handle the case t=1. Condition (c) implies that Gj+1 is connected. Let Q be a shortest Sa1,j+1–Sb1,j+1 path in Gj+1, with endpoints u∈Sa1,j+1 and v∈Sb1,j+1. Let u′∈Sa1,j and v′∈Sb1,j be matched to u and v by Ma1,j and Mb1,j, respectively. Then Q, the edges uu′ and vv′, and the unique u′–v′ path in T1 form a cycle of length at least d(B1)≥ℓ. Thus P(j+1) holds.
We may therefore assume that t≥2. Relabel the 2t terminal sets and the associated matchings by
Ai:=Sai,j+1,Ai+t:=Sbi,j+1,Fi:=Mai,j,Fi+t:=Mbi,j(i∈[t]).
and let M:={{i,i+t}:i∈[t]}. Apply Lemma 5.1 in Gj+1 to A1,…,A2t and M. Let M+ have maximum cardinality among the matchings allowed by that lemma, let P be a witnessing family of paths, and put Γ:=([2t],M∪M+). If Γ is acyclic, then, writing t′:=t−∣M+∣, Lemma 5.1 and ∣V(Gj+1)∣≤n give t′≤βt.
The graph Γ records how the current marked trees are joined. For every x∈V(M+), let ux∈Ax be the endpoint in Ax of the unique path in P incident with x, and let vx be the vertex matched to ux by Fx.
If Γ is a Hamilton cycle, then the paths in P, the matching edges uxvx, and, for each i∈[t], the unique vi–vi+t path in Ti form a cycle. Its length is at least ∑i=1td(Bi)≥ℓ, so P(j+1) holds.
Suppose instead that Γ is acyclic. Its t′ components are paths, each with two endpoints not covered by M+. For each component C, form a graph TC by taking the trees Ti corresponding to the edges of M in C, the paths in P corresponding to the edges of M+ in C, and the matching edges uxvx for x∈V(C)∩V(M+). At each of the two endpoints x of C, also add the entire perfect matching Fx. By condition (II) of Lemma 5.1, the corresponding sets Ax are disjoint from all paths in P. Since C is a path and all constituent trees and paths are otherwise vertex-disjoint, TC is a tree; moreover, the trees obtained from distinct components are vertex-disjoint.
Taking the two sets Ax indexed by the endpoints x of C as the terminal sets of TC gives a marked tree. Every path between these terminal sets traverses each marked tree of Bj corresponding to an edge of M in C, from one of its terminal sets to the other. Consequently, the total length of the resulting t′ marked trees is at least the total length of Bj, and hence at least ℓ. Moreover, t′≤βt≤βj+1r. Thus P(j+1) holds, completing the induction.
Finally, apply P(k). If G contained no cycle of length at least ℓ, there would be a family of at most βkr<1 marked trees whose total length is at least ℓ. Such a family would be empty, a contradiction. Hence G contains a cycle of length at least ℓ. □
Properties of the 2-core
Throughout this section, let ε>0 be a sufficiently small constant and let p=(1+ε)/d. Let L1 denote the largest component of Qpd and let C2 denote the largest component of its 2-core.
This section has two goals. We first estimate ∣V(C2)∣, proving Theorem 2. The proof uses local explorations to identify configurations that certify whether a vertex can belong to the core. We then prove Theorem 6. For this, we consider spanning trees of connected sets in C2 and attach their boundary vertices as leaves. Explorations from the leaves and from the interior of such a tree have different constraints: the leaves need further connections in the core, whereas edges from an interior vertex to vertices outside the tree can only lead outside the core.
The order of the 2-core
We begin with the heuristic behind Theorem 2. A vertex v should belong to C2 when it has two neighbours in Qpd whose explorations in Qpd−{v} survive for long enough. Each exploration has survival probability approximately 2ε, and the explorations are approximately independent. This suggests that the probability that v belongs to C2 is Pr(Bin(d,2εp)≥2)≈2ε2, and hence that ∣V(C2)∣ is approximately 2ε22d.
The proof makes this heuristic precise in two steps. For the upper bound, a vertex in the core must either belong to a small connected subgraph containing a cycle or have two neighbours whose explorations reach a fixed large size. Estimating the probability of these local configurations gives the desired upper bound for a fixed vertex. For the lower bound, we construct two disjoint explorations from neighbours of v, each of which reaches many vertices lying on cycles. These configurations place v in a large component of the 2-core and therefore in C2 whp. In both directions, we use McDiarmid’s inequality to establish concentration of the number of vertices satisfying the corresponding properties.
Proof of Theorem 2. We first prove the upper bound. Let r=ε−6 and call a vertex v good if it lies in a connected subgraph of Qpd of order at most 2r+1 containing a cycle, or if at least two of its neighbours in Qpd have components of order at least r in Qpd−{v}. Every vertex of C2 is good.
For a fixed pair u,u′ of neighbours, explore their components in Qpd−{v} successively, stopping each exploration when it reaches r vertices and never querying an edge to a previously reached vertex. If v is good and does not lie in a connected subgraph of order at most 2r+1 containing a cycle, then both explorations reach r vertices for some such pair. By (1), the probability that both explorations reach this size is 4ε2+O(ε3)+od(1). Thus the probability that v is good is at most
i=3∑2ε−6+1(ed)i−1pi−1(2i)p+(2d)p2(4ε2+O(ε3))=2ε2+O(ε3).
An application of McDiarmid’s inequality gives that whp there are at most (2ε2+O(ε3))2d good vertices, hence ∣V(C2)∣≤(2ε2+O(ε3))2d whp.
We now prove the lower bound. Fix v∈V(Qd) and let L=log2(d−2). Let Qd(v) be the (d−2)-dimensional subcube induced by the vertices that agree with v in their first two coordinates, and let Qpd(v)=Qpd[V(Qd(v))].
Expose the edges incident to v in Qpd(v). Form Nv by choosing L of its neighbours, or all of them if there are fewer than L. Let R(v)={i∈[d]:∃u∈Nv such that u and v differ in their ith coordinate} be the set of coordinates on which v differs from its neighbours in Nv. For u∈Nv, let Q(u,v) be the percolated subcube obtained from Qpd(v) by fixing the coordinates in R(v) to their values at u. Its underlying cube has dimension d−∣R(v)∣−2. Let Nu,v be the set of vertices within distance L from u in Q(u,v). Let E(u,v) be the event that ∣Nu,v∣≥d20/2 and at least d2 vertices w∈Nu,v lie on the 4-cycle w0w1w1,1w1,0w0 in Qpd, where wi1,i2 is obtained from w by changing coordinate j∈{1,2} whenever ij=1. Let Ev be the event that there exists a pair of vertices u,u′∈Nv such that the events E(u,v) and E(u′,v) occur. Note that in the event Ev the vertex v lies in a component of the 2-core of Qpd with at least 2d2 vertices.
By (2), for u∈Nv the probability that at least d20 vertices lie at distance at most L from u in Q(u,v) is x=2ε+O(ε2). Since the corresponding 4-cycles are vertex disjoint, each of them belongs to Qpd independently with probability p4. Thus, by the Chernoff bound at least d2 of these cycles belong to Qpd whp. It follows that
Pr(Ev)≥(2d−2)(xp)2(1−xp)d−4−Pr(Bin(d−2,p)≥log2d)+o(1)=2(1+o(1))(xpd)2e−xpd=2((2ε+O(ε2))(1+ε))2e−(2ε+O(ε2))(1+ε)=(2ε2+O(ε3))e−2ε+O(ε2)=2ε2+O(ε3).
The event Ev depends only on edge indicators within cube distance L+3 of v. Changing one edge therefore affects at most 2dL+3≤e2log3d of those events. McDiarmid’s inequality (see Theorem 4) gives that the event Ev occurs for at least (2ε2+O(ε3))2d vertices v∈V(Qpd) whp. Each of those vertices lies in a component of the 2-core of Qpd with at least 2d2 vertices, hence by Lemma 2.4 in C2 whp. This completes the proof of the lower bound on ∣V(C2)∣.
Expansion properties of connected subsets of the 2-core
We first discuss why connected sets in C2 should expand by a factor of order ε. The heuristic for Theorem 2 suggests that a vertex has degree at least k in the core when at least k of the explorations from its neighbours survive. Thus, for each fixed k≥3, we expect only O(εk2d) vertices of degree at least k, compared with Θ(ε22d) vertices in the core altogether. If the degree-two vertices are spread roughly uniformly among the bare paths joining vertices of higher degree, then C2 resembles an almost 3-regular graph whose edges have been replaced by paths of typical length Θ(1/ε). This suggests that expansion by a constant factor before these subdivisions becomes expansion by a factor of order ε in C2.
This picture resembles the anatomy of the 2-core of the binomial random graph, for which a much finer description was proved by Ding, Lubetzky and Peres [12].
A standard way to study the boundary of a connected set is to choose a spanning tree as a witness, count the possible trees, and bound the probability that a given witness has an unusually small or large boundary. Applied directly in Qpd, however, this argument does not capture the scale we need inside C2: a tree may have a neighbourhood of order ∣V(T)∣ in Qpd even when its neighbourhood in the core has order ε∣V(T)∣. We therefore need witnesses that also record the constraints imposed by membership in the core.
Start with a spanning tree of a connected set in C2 and attach its neighbours in C2 as leaves. The resulting tree T is interior-closed in C2: every neighbour in C2 of a non-leaf vertex already belongs to T. Explorations leaving the interior must therefore die out outside the core. By contrast, an exploration from a leaf must grow, find a cycle, or return to the tree through an additional edge. Heuristically, extinction at an interior vertex contributes a factor of about 1−2ε, while growth from a leaf contributes a factor of about 2ε. Thus, for a tree with t′ vertices and s leaves, the expression pt′−1(1−2ε)t′−s(2ε)s suggests the probability scale for such a witness. The proof below handles the possible cycles, returns and dependencies through explicit explorations.
To obtain sufficiently strong bounds, we further restrict the form of the witness. For example, for the upper bound on expansion, we prune paths from an interior-closed tree while preserving its number of leaves. The resulting subtree has the following property: every leaf either has a neighbour of degree at least three in the tree or is incident to an additional edge with both endpoints in the tree. We call such trees special. Harper’s inequality, together with a union bound, shows that connected sets in the relevant size range typically span few additional edges. Leaves of the second type are therefore rare. Leaves of the first type impose a useful restriction when counting trees: their incident edges are not subdivided when the tree is reconstructed from its contracted form. This gives the sharper count needed for the expansion bounds.
We first define special (a,b)-trees, where a and b count these two types of leaves. Lemma 6.2 bounds their number, and Lemma 6.3 shows how to prune or extend an interior-closed tree to obtain a special one. Then, Lemma 6.5 bounds the possible numbers of leaves of special trees in C2. We finally combine these bounds to prove Theorem 6.
Definition 6.1. For a tree T on at least three vertices, denote by A(T) the set of leaves of T whose unique neighbor in T has degree at least three, and by B(T) the remaining leaves.
For a graph H⊇T, call T an H-special (a,b)-tree if ∣A(T)∣=a, ∣B(T)∣=b, and every leaf in B(T) is incident to an edge of E(H[V(T)])∖E(T). The edges of E(H[V(T)])∖E(T) are called (H,T)-surplus edges.
We say that T is interior-closed in H if NH(v)⊆V(T) for every non-leaf v of T. It is almost interior-closed in H if the same condition holds for every non-leaf that is not a neighbor of a leaf in T.
For a tree T, write ℓ(T) for its number of leaves.
Lemma 6.2. Let H be a graph of maximum degree at most d, let v∈V(H), and let k≥3 and a,b≥0 be integers. Let t(v,a,b,k) be the number of H-special (a,b)-trees rooted at v, with k vertices, in which v has degree at least 3.
If k≥4(a+b), then
t(v,a,b,k)≤(a+b)dk−1(a+2b2e3k)a+2b.(12)
Proof. Let ℓ=a+b be the number of leaves of T. Fix an ordering of V(H). For each vertex u, label its neighbours injectively by elements of [d] according to this ordering. Direct the edges of a counted tree T away from its root v, and label each directed edge uw by the label of w at u.
Contract every maximal bare subpath of T into a single edge. Record on each resulting edge the sequence of labels along the corresponding path, and let T′ be the resulting rooted tree. It has ℓ leaves and at most ℓ−2 vertices of degree at least three, including the root. Thus, with h:=∣V(T′)∣, we have that ℓ+1≤h≤2ℓ−1.
The outgoing edges of T′ at each vertex have distinct first labels, inherited from the corresponding outgoing edges in H. Lemma 2.1 gives that the number of such first-labeled rooted trees is at most (ed)h−1.
Given T′, to determine T first choose the a leaves in A(T′) in at most (aℓ)≤2ℓ ways. Their incident edges have length one before and after contraction. The remaining length assignments number
(h−a−2k−a−2)≤(a+2bk)≤(a+2bek)a+2b.
Here we used that h−a−2≤a+2b and a+2b≤k/2. The remaining labels can be chosen in at most dk−h ways. Thus,
t(v,a,b,k)≤h=ℓ∑2ℓ−1(ed)h−12ℓ(a+2bek)a+2bdk−h≤ℓdk−1(a+2b2e3k)a+2b.
Lemma 6.3. Whp every tree T⊆C2 with at least d3 vertices that is interior-closed in C2 admits trees
T−⊆T⊆T+⊆C2 with the following properties.
(i) ∣V(T−)∣≥∣V(T)∣/d3, ℓ(T−)=ℓ(T), and T− is Qpd-special.
(ii) ∣V(T+)∣≤d3∣V(T)∣, ℓ(T)≤ℓ(T+)≤2ℓ(T), and T+ is Qpd-special and almost interior-closed in C2.
Proof. It suffices to construct T− and T+ in the high-probability event given in Corollary 2.5, that is, in the event that every component of Qpd−V(C2) has at most d3 vertices and every bare path in C2 has at most d3−3 vertices.
To obtain T−, let F=E(Qpd[V(T)])∖E(T). Recursively delete a leaf whose parent has degree two in the current tree and which is not incident to F, until no such leaf exists. Let T− be the resulting tree. No endpoint of an edge in F is deleted. Thus every remaining leaf with a degree-two parent is incident to a surplus edge whose endpoints both remain, so T− is special. At each step the parent becomes a leaf, so the number of leaves is unchanged.
This process cannot leave fewer than three vertices. Indeed, since T has more than d3−1 vertices, it is not a bare path in C2. Thus it has a non-leaf vertex v of degree at least three in C2. Since T is interior-closed, the neighbors of v lie in V(T). Either v has degree at least three in T, in which case none of its neighbors is deleted, or v is incident to a (Qpd,T)-surplus edge. In the latter case, both endpoints of that edge and the tree path between them remain.
Finally, each component spanned by E(T)∖E(T−) is a bare path in C2 and has as an endpoint a distinct leaf of T−. Since each such path has at most d3−3 vertices we have that
∣V(T)∣≤∣V(T−)∣+(d3−3)ℓ(T−)≤d3∣V(T−)∣.
To obtain T+, start from T and proceed in two stages. First, whenever a leaf has a degree-two parent, is not incident to a surplus edge, and has degree two in C2, append its other edge in C2. Repeat until no such leaf remains. This stage preserves the number of leaves.
Next, consider a leaf that is not incident to a surplus edge and whose parent does not have degree at least three. After the first stage, such a leaf has degree at least three in C2. Append two of its edges in C2 that are absent from the current tree. Their other endpoints lie outside the tree, since the leaf is not incident to a surplus edge. Repeat until no such leaf remains, and denote the resulting tree by T+. This stage increases the number of leaves by at most a factor of two, so ℓ(T)≤ℓ(T+)≤2ℓ(T).
By construction, T+ is special. Every non-leaf vertex of T+ that is neither a parent of a leaf nor a vertex of T has degree two in C2. Since T is interior-closed, it follows that T+ is almost interior-closed.
Finally, each component spanned by E(T+)∖E(T) is a bare path in C2, possibly extended by two edges, and has at most d3−1 vertices. Consequently,
∣V(T+)∣≤∣V(T)∣+(d3−1)ℓ(T)≤d3∣V(T)∣,
as required. □
Special trees in Qpd
For the rest of this section let E be the event that every connected set U in Qpd with m/d4≤∣U∣≤Md6 spans at most (1+ε12)∣U∣ edges in Qpd.
Lemma 6.4. Whp the event E occurs.
Proof. If E does not occur, then there is a tree T⊆Qpd of order s∈[m/d4,Md6] that spans ε12s additional edges in Qpd. Harper’s inequality implies that a set of size s≤d6M spans at most slog2s≤2αds edges in Qd. Thus Lemma 2.1 gives
Pr(E)≤s=m/d4∑d6M2d(ed)s−1ps−1(ε12s2αds)pε12s≤s=m/d4∑d6M2d+3s(ε12s2eαdps)ε12s ≤s=m/d4∑d6M2d3sε13s=s=m/d4∑d6M2d3sεs/ε7=o(1).
We now bound the numbers of leaves of special trees in C2. For a tree of order s in the range below, the bound on b shows that few leaves are supported by surplus edges. The bounds on a then give O(εs) leaves in total, and Ω(εs) leaves when the tree is almost interior-closed.
Lemma 6.5. Let
α=α(ε):=ε1/ε20,m=m(ε,d):=ε2⋅2αd,andM=M(ε,d):=ε−2⋅2αd. Whp every Qpd-special (a,b)-tree T⊆C2 of order s with m/d4≤s≤Md5 satisfies
b<ε10s,a≤1000εs. If, in addition, T is almost interior-closed in C2, then a≥εs/1000.
Proof. Assume that there exists a Qpd-special (a,b)-tree T⊆C2 of order s with m/d4≤s≤Md5. The proof is divided into 4 cases, which we rule out. Cases 1 and 2 give the upper bounds on b and a, respectively. For Cases 3 and 4, we use almost interior-closedness to prove the lower bound on a.
Case 1: b≥ε10s. Each leaf in B(T) meets a surplus edge, and a surplus edge meets at most two such leaves. Hence V(T) spans at least ∣V(T)∣−1+b/2≥(1+ε11)∣V(T)∣ edges, contradicting the event E. Hence Case 1 does not occur whp.
For the remaining cases, we first record a necessary condition on the leaves of T. For a leaf v∈V(T) we denote by C(v,T) the component of v in Qpd−(V(T)∖{v}).
Property (P1): For every leaf vertex v of T at least one of the following holds.
C(v,T) has size at least ε−6.
C(v,T) has size less than ε−6 and it spans a cycle.
v is connected to another vertex of T via a path of length at most ε−6 that uses no edge of T.
(P1) follows from the fact that V(T)⊆V(C2) implies that every vertex v∈V(T) either lies on a cycle or on a path connecting two cycles in Qpd. To bound the probability that a given tree T satisfies (P1), we use the following exploration procedure.
Let r=ε−6 and enumerate the leaves as L(T)={v1,…,va+b}. We explore from them in this order. Having constructed the exploration trees F1,…,Fi−1, let Ui=V(T)∪⋃j<iV(Fj) and start Fi at vi. Extend Fi by depth-first search, querying edges from its vertices to V(Qd)∖((Ui∖{vi})∪V(Fi)). Stop when Fi reaches r vertices or when the component of vi in Qpd−(Ui∖{vi}) has been fully explored.
For i∈[a+b], call the leaf vi successful if ∣V(Fi)∣=r. Note that conditioned on F1,…,Fi−1, the exploration process for determining Fi is dominated by a branching process with offspring distribution Binomial(d,p). Thus, by (1), conditioned on F1,…,Fi−1 the vertex vi is successful with probability at most 2ε+O(ε2)≤5ε/2.
Let U=V(T)∪⋃j≤a+bV(Fj). If (P1) is satisfied, then every non-successful exploration tree Fi is incident to an unqueried present edge spanned by U that does not belong to T∪⋃jFj. Since this union is a spanning tree on U, the number z of such surplus edges satisfies, in the event E,
z≤ε11∣U∣+1≤ε11rs+1≤2ε5s.
Here ∣U∣≤rs≤Md6. Each surplus edge is incident to at most two exploration trees, so at most 4ε5s leaves are non-successful. If a≥ε3s and b≤ε10s, the probability that at least a−4ε5s leaves are successful is at most
(b+4ε5sa+b)(5ε/2)a−4ε5s≤(5ε/2)aexp(O(ε2log(1/ε)a))≤(3ε)a.
Let H1 be the full exploration history and let A1(T) be the event that at least a−4ε5s leaves are successful. This event is determined by H1, and E together with (P1) implies A1(T). The exploration does not query edges of T. Therefore, for every fixed tree T⊆Qd in this range,
Pr(the event E occurs and T satisfies (P1))≤Pr(A1(T))≤(3ε)a.(13)
Case 2: b≤ε10s and a>1000εs. If a+b>s/4, then a>s/5 for sufficiently small ε.
Lemma 2.1 and (13) bound the probability of such a tree, together with E, by
s=m/d4∑d5M2d(edp)s−1(3ε)s/5=o(1).
Otherwise s≥4(a+b) and a>b, and the tree has a vertex of degree at least three at which to root it. Lemma 6.2 and (13) now give the following bound for the remaining part of Case 2:
Pr(¬E)+s=m/d4∑d5Ma=1000εs∑sb=0∑ε10s2d(a+b)ds−1(a2e3s)a+2bps−1(3ε)a≤o(1)+s=m/d4∑d5Ma=1000εs∑s23d(pd)s−1(a6εe3s)a(a2e3s)2ε10s≤o(1)+s=m/d4∑d5Ma=1000εs∑s23dεεs(10006e3⋅(2e3ε−1)ε)ε9s=o(1).
Hence Case 2 does not occur whp.
For cases 3 and 4, we use the additional restriction imposed by almost interior-closedness. Let U and H1 be as defined at the end of the preceding exploration. Let K(T) be the set of vertices of T that are neither leaves nor parents of leaves. For v∈K(T) let C(v,T) be the component of v in Qpd−(U∖{v}).
Property (P2): For v∈K(T), C(v,T) is a tree.
Indeed, if (P2) does not hold, then v has a neighbor outside U that also belongs to C2. This contradicts the assumption that T is almost interior-closed in C2. Let A2(T) be the event that T satisfies (P2). Let E2 be the high-probability event that every component of Qpd−V(C2) has at most d3 vertices, as in Corollary 2.5.
Conditional on H1, we couple a further exploration with k=∣K(T)∣ independent branching processes with offspring distribution Binomial(D,p), where D=(1−ε4)d. The coupling will be such that, in the event E2∩A2(T), every descendant corresponds to a distinct newly discovered vertex outside C2. In particular, all k processes die out.
Let R=K(T), R+=U, and let F consist of the unqueried edges in Qd from R to V(Qd)∖R+. Sequentially, for i=1,…,k, start a queue Qi={ui} with one artificial root. While Qi=∅, remove a vertex from Qi and query D edges from F, one at a time. After each query, remove that edge from F. If it is present, let ae be its endpoint outside R+, add ae to both R and R+, and add one child to Qi. Update F immediately by adding the unqueried edges from ae to outside R+ and removing edges now spanned by R+. Thus each present query discovers a new vertex. If no eligible edge remains before the D queries have been completed, return FAILURE and complete the branching processes with fresh independent Bernoulli trials. Terminate the ith iteration once Qi=∅.
Now assume that the event E2∩A2(T) occurs and a+b≤1001εs. We will show that FAILURE does not occur. Indeed, every discovered vertex outside K(T) lies in a tree attached to a vertex of K(T), so there are at most d4k such vertices. Thus, ∣R+∣≤∣U∣+d4∣K(T)∣≤2d4s. Therefore ∣R∣/∣R+∣≥(s−2(a+b))/rs≥1/2r. Harper’s inequality gives that R+ spans at most α2/3d∣R+∣≤ε10d∣R∣ edges. Hence eQd(R,V(Qd)∖R+)≥(1−ε5)d∣R∣. If FAILURE occurs, then it occurs when the t-th artificial vertex is processed for some t≤∣R∣ at which point F=∅. Thus at most Dt edges had entered F and had been processed. On the other hand, each of the at least (1−ε5)d∣R∣ edges from R to V(Qd)∖R+ had entered F and had been processed. Since (1−ε5)d∣R∣>D∣R∣ we have that FAILURE cannot occur.
In particular, all of the k processes die out. The extinction probability of each process is 1−2ε+O(ε2). Uniformly over the full history H1, we obtain, for a+b≤1001εs,
Pr(E2∩A2(T)∣H1)≤(1−2ε+O(ε2))k≤e−7εk/4≤e−3εs/2.(14)
Case 3: T is almost interior-closed in C2, b≤ε10s and a<ε3s. If T has a vertex of degree at least 3, then it has at least 3 leaves, hence b≥max{0,3−a}, and Lemma 6.2 applies. Otherwise T is a path. Lemma 6.2 and (14) give the following upper bound on the probability of Case 3:
Pr(¬E2)+s=m/d4∑d5M2dds−1ps−1e−3εs/2+s=m/d4∑d5Ma=0∑ε3sb=max{0,3−a}∑ε10s2d(a+b)ds−1(a+2b2ε3s)a+2bps−1e−3εs/2≤s=m/d4∑d5M24d(dp)s(ε32ε3)3ε3se−3εs/2≤s=m/d4∑d5M24d((ε32ε3)3ε2e−1/2)εs=o(1).
Case 4: T is almost interior-closed in C2, b≤ε10s and ε3s≤a<εs/1000. Lemma 6.2, (13) and (14) give the following upper bound on the probability of Case 4:
Pr(¬E)+Pr(¬E2)+s=m/d4∑d5Ma=ε3s∑εs/1000b=0∑ε10s2d(a+b)ds−1(a2ε3s)a+2bps−1(3ε)ae−3εs/2≤o(1)+s=m/d4∑d5Ma=ε3s∑εs/100023d(a6ε3s)a(a2ε3s)2ε7ae−εs/2≤o(1)+s=m/d4∑d5Ma=ε3s∑εs/100023d(a7ε3s)ae−εs/2≤o(1)+s=m/d4∑d5Ma=ε3s∑εs/100023d((7000ε3)1/1000e−1/2)εs=o(1).
□
Proof of Theorem 6. Let α, m, M be as in Theorem 6. Let E+ be the event that E and the high-probability events in Lemmas 6.3 and 6.5 occur. It suffices to prove that in the event E+, (1) and (2) hold. For the lower bound in (1), we extend a tree witness and use the lower bound on its number of leaves. For the upper bound we prune a tree witness and use the upper bound on its number of leaves. For (2), the surplus-edge bound suffices.
First, suppose that the lower bound in (1) does not hold, and let S⊆V(C2) be connected and of size ∣S∣∈[m,M+1] such that ∣NC2(S)∣≤ε∣S∣/4000. Then, ∣S∪NC2(S)∣≤2(M+1) and therefore S∪NC2(S) spans at most ∣S∪NC2(S)∣+t edges, where t:=ε12∣S∪NC2(S)∣. Choose a spanning tree on C2[S], attach to it the vertices in NC2(S) via the edges in C2 and let T be the resulting tree. Then T is interior-closed in C2. Every leaf of T lying in S is incident to a surplus edge, since its degree in C2 is at least two. There are at most t+1 surplus edges, so ℓ(T)≤∣NC2(S)∣+2(t+1). Lemma 6.3 implies that T can be extended into a Q_d_p-special (a′,b′)-tree T+ that is almost interior-closed in C2, has at most d3∣V(T)∣≤2d3(M+1) vertices, and has at most 2ℓ(T) leaves. Therefore,
ℓ(T+)≤2ℓ(T)≤2∣NC2(S)∣+4(t+1)<1000ε∣S∣≤1000ε∣V(T+)∣.
This contradicts the lower bound on a′ given in Lemma 6.5. Hence in the event E+, the lower bound in (1) holds.
Second, suppose that the upper bound in (1) does not hold. Let S⊆V(C2) be connected and of size s=∣S∣∈[m,M+1] such that ∣NC2(S,V(C2)∖S)∣>2000εs. Choose a spanning tree on C2[S] and attach all vertices of NC2(S) as leaves, obtaining an interior-closed tree T of order at most (d+1)s. Lemma 6.3 implies that T contains a Qpd-special (a′,b′)-tree T− with ∣V(T−)∣≥∣V(T)∣/d3 and ℓ(T−)=ℓ(T). Its order lies in the range of Lemma 6.5, and
∣V(T−)∣a′+b′=∣V(T−)∣ℓ(T−)≥s+∣NC2(S,V(C2)∖S)∣∣NC2(S,V(C2)∖S)∣≥(1+2000ε)s2000εs>1500ε.
This contradicts the bounds a′≤1000ε∣V(T−)∣ and b′<ε10∣V(T−)∣ in Lemma 6.5. Hence in the event E+, the upper bound in (1) holds.
Finally, if (2) fails, there are a connected set S and Z⊆NC2(S) such that S∪Z spans more than (1+ε12)∣S∪Z∣ edges, contradicting E. Hence in the event E+, (2) holds.
Acknowledgements
This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/ESP3863424 and the SNSF grant 200021-228014. For open access purposes, the authors have applied a CC BY public copyright license to any author accepted manuscript version arising from this submission.
Statement on AI use. The results presented in this paper were obtained without AI assistance. ChatGPT Pro was used for text editing, polishing, and proofreading.