betaFeedback

WorksMathematics

Linear-length cycles in the supercritical percolated hypercube

Abstract

Let QpdQ_p^d be the random subgraph of the dd-dimensional binary hypercube obtained by retaining each edge independently with probability pp. A long-standing folklore conjecture states that the emergence of the giant component in QpdQ_p^d, at p≈1/dp\approx 1/d, is accompanied by the emergence of cycles of linear length. We confirm this conjecture and determine the order of the longest cycle near the phase transition. Specifically, for every sufficiently small constant ε>0\varepsilon>0, we show that if p=(1+ε)/dp=(1+\varepsilon)/d, then with high probability the longest cycle of QpdQ_p^d has length Θ(ε22d)Θ(\varepsilon^2 2^d). The dependence on ε\varepsilon is optimal up to constant factors.

Introduction

The dd-dimensional binary hypercube QdQ^d is the graph with vertex set {0,1}d\{0,1\}^d, in which two vertices are adjacent if and only if they differ in a single coordinate. The percolated hypercube QpdQ_p^d is the random subgraph of QdQ^d obtained by retaining each edge independently with probability pp. 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 QpdQ_p^d was pioneered by Burtin [10] and Sapoženko [30], who showed that p=1/2p = 1/2 is a sharp threshold for connectivity. Results on its component structure followed. Erdős and Spencer [18] observed that, if p=c/dp = c/d with c<1c < 1, then QpdQ_p^d typically contains only components of order O(d)O(d). On the other hand, Ajtai, Komlós and Szemerédi [2] proved that, if p=c/dp = c/d with c>1c > 1, then QpdQ_p^d typically contains a connected component L1L_1 with linearly many vertices, called the giant component. These results established that the size of the largest component of QpdQ_p^d goes through a phase transition at p=(1+o(1))/dp = (1+o(1))/d.

Bollobás, Kohayakawa and Łuczak [9] determined the size of the giant more precisely. For c>0c > 0, let y(c)y(c) denote the survival probability of a Galton–Watson process with offspring distribution Poisson(c)(c). They proved that, if p=c/dp = c/d with c>1c > 1, then typically L1L_1 has y(c)2d+o(2d)y(c)2^d+o(2^d) vertices, while every other component has order O(d)O(d). Thus, in the corresponding regime, the component structure of QpdQ_p^d resembles that of the binomial random graph G(n,p)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\varepsilon> 0 and p=(1+ε)/dp = (1+\varepsilon)/d, the circumference of QpdQ_p^d is of order ε22d\varepsilon^2 2^d with high probability.

The circumference of G(n,p)G(n,p)

Erdős [20] conjectured that for every constant c>1c > 1, G(n,c/n)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>1c > 1, if p≥c/np \ge c/n, then G(n,p)G(n,p) contains a cycle of linear length whp. A weaker version of this result, covering the range c>2log⁡2c > 2\log2, 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 cc 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 QpdQ_p^d

A folklore conjecture states that the circumference of QpdQ_p^d exhibits behaviour analogous to that of G(n,p)G(n,p). Namely, it undergoes a phase transition near p=1/dp=1/d, from logarithmic to linear in the number of vertices; it then continues to grow with the giant component, and finally QpdQ_p^d 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/2p=1/2 is the threshold for the existence of a Hamilton cycle in QpdQ_p^d.

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)\varepsilon\in(0,1), there exists a constant c=c(ε)c=c(\varepsilon) such that, if p≥c/dp \ge c/d, then QpdQ_p^d typically contains a cycle covering at least (1−ε)2d(1-\varepsilon)2^d vertices.

In this paper, we establish the emergence of cycles of linear length just above p=1/dp=1/d, showing that the circumference of QpdQ_p^d 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/dp=c/d for a constant c>1c>1, then QpdQ_p^d typically contains a cycle of length Ω(2d/(dlog⁡d))\Omega(2^d/(d\log d)). We prove that the cycle can be taken to have linear length.

Theorem 1. Let ε>0\varepsilon>0 be a sufficiently small constant. There exists a constant C>0C>0 that is independent of ε\varepsilon such that, if p=p(d)=(1+ε)/dp=p(d)=(1+\varepsilon)/d, then with high probability1 QpdQ_p^d contains a cycle of length at least Cε22dC\varepsilon^2 2^d.

The next theorem shows that the dependence on ε\varepsilon is optimal. The 2-core of a graph GG is the maximal subgraph of GG of minimum degree at least 2. Every cycle of GG lies in its 2-core. Thus the circumference of GG is at most the size of the largest component of its 2-core.

Theorem 2. Let ε>0\varepsilon>0 be a sufficiently small constant and let p=p(d)=(1+ε)/dp=p(d)=(1+\varepsilon)/d. Then, whp the 2-core of the giant component of QpdQ_p^d has size (2ε2+O(ε3))2d(2\varepsilon^2+O(\varepsilon^3))2^d.

Theorem 1 settles the existence question. Theorem 2 shows why the scale ε22d\varepsilon^2 2^d is the right one near the transition. Together, the two theorems show that, for p=(1+ε)/dp=(1+\varepsilon)/d, where ε>0\varepsilon>0 is a sufficiently small constant, the circumference of QpdQ_p^d is Θ(ε22d)\Theta(\varepsilon^2 2^d) 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 QpdQ_p^d. 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′G'_0 and G1′,…,Gk′G'_1,\ldots,G'_k of QdQ^d. The initial subcube has dimension d−2d-2, while each of the remaining subcubes has dimension d−O(1)d-O(1). Consecutive subcubes Gj−1′G'_{j-1} and Gj′G'_j are joined by a perfect matching MjM_j in QdQ^d for j≥2j\ge2, and G0′G'_0 is joined to G1′G'_1 by a set of pairwise disjoint paths. For 0≤j≤k0\le j\le k, let GjG_j be the subgraph of QpdQ_p^d induced by V(Gj′)V(G'_j).

We first find vertex-disjoint paths of at least medium length in the 22-core of the giant component of G0G_0 that cover a linear number of vertices. We then join these paths into a single cycle using the subsequent graphs G1,…,GkG_1,\ldots,G_k and the matching edges retained in QpdQ_p^d. Here, “medium” means exponential in dd, with a small positive exponent depending on ε\varepsilon. Working in the 22-core at the packing stage gives the optimal dependence on ε\varepsilon.

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 22-core, this gives the paths needed for the next step.

Joining the paths. Let P1,…,PtP_1,\ldots,P_t be the resulting paths. For each PiP_i, we choose sets Si+S_i^+ and Si−S_i^- 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 GjG_j belongs to the giant component of GjG_j. We may take all the sets to have the same size ss, which is exponentially large in dd. 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 U1U_1 and U2U_2 be their unions. If sets of size at least min⁡{∣U1∣,∣U2∣}\min\{|U_1|,|U_2|\} still expand sufficiently in the remaining graph, then we can find another short path between U1U_1 and U2U_2, 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∣}\min\{|U_1|,|U_2|\} initially expand by a factor of, say, 1/d21/d^2, then the number of deleted vertices is larger than min⁡{∣U1∣,∣U2∣}/2d2\min\{|U_1|,|U_2|\}/2d^2; 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)s/d^{O(1)}. Since ss is exponentially large in dd, only O(d/log⁡s)O(d/\log s) rounds are needed. Choosing kk 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 QpdQ^d_p gives a cycle covering a Θ(ε2)\Theta(\varepsilon^2) fraction of the vertices of L1L_1, and thus of length Θ(ε22d)\Theta(\varepsilon^2 2^d) (see [13, 5] for the expansion properties of L1L_1).

To obtain the optimal dependence on ε\varepsilon, 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)\Theta(\varepsilon^2 2^d), yielding a cycle of the desired length Θ(ε22d)\Theta(\varepsilon^2 2^d).

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)G=(V,E), for A,B⊆VA,B\subseteq V, we write eG(A,B)e_G(A,B) for the number of edges with one endpoint in AA and one in BB, with edges inside A∩BA\cap B counted twice. We write NG(A)N_G(A) for the set of vertices in V∖AV\setminus A with a neighbour in AA, G[A]G[A] for the subgraph induced by AA, and eG(A):=∣E(G[A])∣e_G(A):=|E(G[A])|. For S⊆V(G)S\subseteq V(G), we say that SS is connected in GG if G[S]G[S] is connected. We say that SS is almost connected in GG if it is connected in GG, or if G[S∪{v}]G[S\cup\{v\}] is connected for some v∈V(G)∖Sv\in V(G)\setminus S. A path P⊆GP\subseteq G is bare in GG if all of the internal vertices of PP have degree two in GG.

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>1c>1, the largest component of Qc/ddQ^d_{c/d} has (y(c)+o(1))2d(y(c)+o(1))2^d vertices, and every other component has order O(d)O(d), whp [9]. Here y(c)>0y(c)>0 is the survival probability of a Galton–Watson process with offspring distribution Poisson(c)(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 dd and 1/ε1/\varepsilon 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.

References

  1. [1]M. Ajtai, J. Komlós, and E. Szemerédi. The longest path in a random graph. Combinatorica, 1:1–12, 1981.DOI
  2. [2]M. Ajtai, J. Komlós, and E. Szemerédi. Largest random component of a k-cube. Combinatorica, 2(1):1–7, 1982.
  3. [3]M. Ajtai, J. Komlós, and E. Szemerédi. First occurrence of Hamilton cycles in random graphs. North-Holland Mathematics Studies, 115(C):173–178, 1985.DOI
  4. [4]M. Anastos, S. Diskin, J. Erde, M. Kang, M. Krivelevich, and L. Lichev. Nearly spanning cycle in the percolated hypercube. arXiv preprint arXiv:2505.04436, 2025.arxiv.org/abs/2505.04436
  5. [5]M. Anastos, S. Diskin, L. Lichev, and M. Zhukovskii. Diameter and mixing time of the giant component in the percolated hypercube. arXiv preprint arXiv:2510.13348, 2025.arxiv.org/abs/2510.13348
  6. [6]A. J. Bernstein. Maximally connected arrays on the n-cube. SIAM J. Appl. Math., 15:1485–1489, 1967.DOI
  7. [7]A. Beveridge, A. Frieze, and C. McDiarmid. Random minimum length spanning trees in regular graphs. Combinatorica, 18(3):311–333, 1998.DOI
  8. [8]B. Bollobás. The evolution of random graphs. Trans. Am. Math. Soc., 286:257–274, 1984.
  9. [9]B. Bollobás, Y. Kohayakawa, and T. Łuczak. The evolution of random subgraphs of the cube. Random Structures Algorithms, 3(1):55–90, 1992.
  10. [10]J. D. Burtin. The probability of connectedness of a random subgraph of an n-dimensional cube. Problemy Peredači Informacii, 13(2):90–95, 1977.
  11. [11]P. Condon, A. Espuny Díaz, A. Girão, D. Kühn, and D. Osthus. Hamiltonicity of random subgraphs of the hypercube. Mem. Amer. Math. Soc., 304(1534):v+132, 2024.
  12. [12]J. Ding, E. Lubetzky, and Y. Peres. Anatomy of the giant component: The strictly supercritical regime. European Journal of Combinatorics, 35:155–168, 2014.arxiv.org/abs/1202.6112
  13. [13]S. Diskin, J. Erde, M. Kang, and M. Krivelevich. Isoperimetric inequalities and supercritical percolation on high-dimensional graphs. Combinatorica, 44(4):741–784, 2024.arxiv.org/abs/2304.00016
  14. [14]S. Diskin and M. Krivelevich. Supercritical site percolation on the hypercube: small components are small. Combinatorics, Probability and Computing, 32(3):422–427, 2023.arxiv.org/abs/2204.05074
  15. [15]S. Diskin and M. Krivelevich. Components, large and small, are as they should be ii: supercritical percolation on regular graphs of constant degree. International Mathematics Research Notices, 2025(12):rnaf167, 2025.arxiv.org/abs/2408.04599
  16. [16]J. Erde, M. Kang, and M. Krivelevich. Expansion in supercritical random subgraphs of the hypercube and its consequences. Ann. Probab., 51:127–156, 2023.arxiv.org/abs/2111.06752
  17. [17]P. Erdős and A. Rényi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17–61, 1960.
  18. [18]P. Erdős and J. Spencer. Evolution of the n-cube. Comput. Math. Appl., 5(1):33–39, 1979.DOI
  19. [19]W. Fernandez de la Vega. Long paths in random graphs. Studia Sci. Math. Hungar., 14(4):335–340, 1979.
  20. [20]M. Fiedler, editor. Recent advances in graph theory. Academia, Prague, 1975.
  21. [21]A. Frieze. Random structures and algorithms. In Proceedings of the International Congress of Mathematicians (ICM 2014), Seoul, Korea, August 13–21, 2014. Vol. I: Plenary lectures and ceremonies, pages 311–340. Seoul: KM Kyung Moon Sa, 2014.
  22. [22]A. Frieze. Hamilton Cycles in Random Graphs: a bibliography. arXiv:1901.07139, 2019.arxiv.org/abs/1901.07139
  23. [23]A. Frieze and M. Karoński. Introduction to random graphs, 2016.DOI
  24. [24]J. B. S. Haldane. A mathematical theory of natural and artificial selection, part v: Selection and mutation. Proceedings of the Cambridge Philosophical Society, 23(7):838–844, 1927.
  25. [25]L. H. Harper. Optimal assignments of numbers to vertices. SIAM J. Appl. Math., 12:131–135, 1964.DOI
  26. [26]S. Hart. A note on the edges of the n-cube. Discrete Mathematics, 14:157–163, 1976.
  27. [27]M. Krivelevich. Long cycles in locally expanding graphs, with applications. Combinatorica, 39(1):135–151, 2019.arxiv.org/abs/1609.06851
  28. [28]J. H. Lindsey. Assignment of numbers to vertices. Amer. Math. Monthly, 71:508–516, 1964.DOI
  29. [29]C. McDiarmid. On the method of bounded differences. In Surveys in Combinatorics 1989, pages 148–188. London Mathematical Society Lecture Notes, 1989.DOI
  30. [30]A. A. Sapoženko. Metric properties of almost all functions of the algebra of logic. Diskret. Analiz, 10:91–119, 1967.

Paper details

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

views · 0

downloads · 0

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

  • Mathematics

ChatGPT Pro

View statement
Looking for related papers…
Contents