Pith. sign in

REVIEW 4 major objections 3 minor 1 cited by

Cover time of random subgraphs of the hypercube

T0 review · 4 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Above the connectivity threshold, the cover time of $Q_{n,p}$ is $(1+o(1))\,\frac{p}{\log 2\,\log(2p/(2p-1))}\,n\log n$ with high probability.

desk verdict The main result is real but Theorem 1 as printed has the logarithmic factor inverted; the proof itself derives the correct reciprocal formula, so the paper needs a mandatory correction before it can be cited. read the letter →

arxiv 2506.03375 v1 pith:G2CVSDH2 submitted 2025-06-03 math.CO cs.DS

Colin Cooper , Alan Frieze , Wesley Pegden This is my paper
classification math.COcs.DS MSC 05C8105C8060J10
keywords covertimerandomwalkhypercubesubgraphconnectivitythresholdconductancefirstvisitexpander
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper determines, up to a $1+o(1)$ factor, how long a simple random walk on the random subgraph $Q_{n,p}$ of the $d$-dimensional hypercube needs to visit every vertex, for every edge-retention probability $p \ge p_c = \tfrac12(1+\theta\,\log d/d)$ above the connectivity threshold. The central result is Theorem 1: with probability tending to 1, the cover time equals $(1+o(1))\,\frac{p}{\log 2\,\log(2p/(2p-1))}\,n\log n$. This matters because $Q_{n,p}$ is a canonical random model of a sparse, high-dimensional graph with exponentially many vertices, and its cover time had previously been known only for the full cube or in much looser bounds. The formula interpolates smoothly between the classical $n\log n$ cover time at $p=1$ and a $n\log n\log\log n$ regime just above the threshold.

What carries the argument

The load-bearing object is the first visit time lemma (Lemma 2 of the paper, quoted from [7]). For a random walk with mixing time $T$, it bounds the probability that vertex $v$ remains unvisited at time $t\ge T$ by roughly $(1+p_v)^{-t}$ with $p_v=\pi_v/R_v$, where $R_v$ is the expected number of visits to $v$ during the mixing time and $\pi_v=d_v/2m$ is the stationary mass of $v$. The proof needs $R_v=1+O(1/\log d)$, and obtains this from property P3, which says that vertices of degree at most $L=100d/\log d$ are isolated at distance at least $h=d/(2\log d)$; the walk drifts away from such a vertex fast enough that returns over $T=\log^7 n$ steps are negligible. The conductance bound $\Phi=\Omega(1/(d^3\log d))$ (Proposition 5) is what makes $T=\log^7 n$ a genuine mixing time.

What would settle it

For $p=\tfrac12(1+\theta\log d/d)$, compute the expected number of pairs of vertices of degree at most $100d/\log d$ whose graph distance is at most $d/(2\log d)$; the proof's property P3 requires this to be $o(1)$, so a find of even one such pair at larger and larger $d$ would invalidate the return-count estimate and the lower bound.

Watch

Extended reading notes

Core claim

The paper's claim is that above the connectivity threshold the cover time is controlled entirely by vertices of degree $d\varepsilon$, where $p=(1+\varepsilon)/2$: these are the last vertices visited, and their number determines the lower bound through a second moment estimate. The proof combines a first visit time lemma, which reduces unvisited probabilities to expected return counts $R_v$ over the mixing time, with high-probability structural properties of $Q_{n,p}$: conductance $\Phi=\Omega(1/(d^3\log d))$, mixing time $T=\log^7 n$, return counts $R_v=1+O(1/\log d)$ for every vertex, and isolation of low-degree vertices at distance $h=d/(2\log d)$. From these ingredients the expected number of unvisited vertices at time $t$ is shown to be concentrated around $\sum_i X(i)e^{-it/dnp}$, whose maximum near $i=d\varepsilon$ yields the formula.

Load-bearing premise

The proof needs the high-probability structural facts P1 and P3: that the random subgraph has conductance $\Omega(1/(d^3\log d))$ and that low-degree vertices are isolated at distance at least $d/(2\log d)$; if either fails, the estimate $R_v=1+O(1/\log d)$ and the unvisited-probability formula can break.

Editorial extensions

If this is right

  • With high probability, $t_{\rm cov}(Q_{n,p}) = (1+o(1))\,\frac{p}{\log 2\,\log(2p/(2p-1))}\,n\log n$ for every $p\ge p_c$.
  • When $d\varepsilon=\ell\log d$ with $\ell$ constant, the cover time is asymptotic to $\frac{1}{2\log 2}\,n\log n\log\log n$.
  • When $\varepsilon$ is constant, the cover time is $\Theta(n\log n)$, and it converges to the full-cube value $n\log n$ as $p\to 1$.
  • Vertices of degree about $d\varepsilon$ are, with high probability, the last vertices to be visited.
  • The mixing time $T=\log^7 n$ is enough for the first-visit-time estimates to hold simultaneously for all vertices.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • One extension the paper leaves implicit: the same template should give the cover time for random subgraphs of other Cartesian product graphs with a similar degree distribution, provided an analogue of the expander theorem holds.
  • A testable prediction of the formula is that the identity of the last visited vertices shifts from degree $d\varepsilon$ to degree 1 exactly at the connectivity threshold; below $p_c$ the cover time should instead be governed by isolated vertices and disconnected components.
  • If the structural lemmas hold with weaker constants, the mixing time can likely be reduced below $\log^7 n$, so the only logarithmic factor in the input would be the isolation distance $h=d/(2\log d)$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 3 minor

Summary. This paper studies the simple random walk on Q_{n,p}, the random subgraph of the d-dimensional hypercube Q_n (n=2^d) obtained by retaining each edge independently with probability p, for p above the connectivity threshold p_c = (1/2)(1 + θ log d/d). The main result, Theorem 1, claims that w.h.p. the cover time satisfies tcov(Q_{n,p}) = (1+o(1)) p/(log 2 · log(2p/(2p−1))) n log n. The proof combines a first-visit-time lemma from the authors' earlier work, a conductance lower bound for Q_{n,p}, structural properties of low-degree vertices, an upper bound via expected number of unvisited vertices, and a lower bound via concentration and second-moment estimates on vertices of degree dε. The upper bound is largely explicit; the lower bound separates the cases ε ≤ 1/100 and ε ≥ 1/100, the latter being deferred. The theorem's displayed formula is internally inconsistent with the derivation in Section 3.1, which gives the reciprocal expression.

Significance. If the proof is completed, the paper would give the first sharp asymptotic for the cover time of supercritical random subgraphs of the hypercube above the connectivity threshold, extending Matthews' classical result for Q_n and the authors' earlier cover-time results for random graphs. The approach is principled: the first-visit-time lemma is used as a black box from [7], no empirical parameters enter, and the final formula has a clean logarithmic correction near the threshold. The upper-bound argument using concentration of degree counts is elegant and essentially complete. However, the theorem statement as printed is false (the formula is inverted), the chosen mixing time T = log^7 n appears too small to meet the stated n^{-3} mixing condition, and the constant-ε lower bound is only sketched. These are fixable but must be addressed before the result is accepted.

major comments (4)
  1. [Section 1, Theorem 1, Eq. (1); Section 3.1] The displayed formula (1) is inverted relative to the paper's own derivation. In Section 3.1 the authors solve E S(t)=1, obtain α = log(2p/(2p−1)), and conclude tcov ∼ ndp · log(2p/(2p−1)). Since n log n = nd log 2, this is equivalent to tcov ∼ (p log(2p/(2p−1))/log 2) n log n. Theorem 1 instead states p/(log 2 · log(2p/(2p−1))) n log n. The printed formula fails the p=1 limit (it gives n log n/(log 2)^2 instead of n log n) and the p→1/2+ limit (it gives 0 instead of ∞), and it contradicts the remark following the theorem. The theorem statement and any summary containing the formula are therefore false as written; the proof, if correct, establishes the reciprocal version. This is a mandatory correction.
  2. [Section 2.3, Eq. (7), Proposition 5] The choice T = log^7 n does not satisfy Condition (i) of Lemma 2 with the conductance bound proved in Proposition 5. Proposition 5 gives Φ = Ω(1/(d^3 log d)) = Ω(1/(log^3 n log log n)), so the bound (6) gives a mixing error of order (1 − Φ^2/2)^T ≈ exp(−log n/(2 log^2 log n)) when T = log^7 n, which is much larger than the required n^{-3}. Taking T = log^8 n or T = log^7 n log^2 log n would fix this, and Lemma 4 still applies for any T = O(log^k n) with constant k. This is load-bearing because Lemma 2's Condition (i) is used to justify the unvisited-probability estimate (4).
  3. [Section 3.3, Case where ε ≥ 1/100] The lower-bound proof for constant ε is incomplete. The final paragraph asserts that 'an argument similar to Section 2.4' will ensure R_{γ(v,w)} = 1+o(1), but no such argument is supplied. This is the main technical step needed to control correlations in the second moment for the constant-ε case. The appeal to Lemma 6.2 is also unclear, because the phrase 'δ = α0 dε' uses δ in a way that conflicts with the earlier definition of δ as the o(1) time shrinkage in t_L = (1−δ)ndp log(2p/(2p−1)). The missing verification of R_γ = 1+o(1) must be provided before the lower bound can be considered proved.
  4. [Section 2.4, Lemma 4, second case] In the proof of Lemma 4, the second case assumes 'at most 2 vertices of degree at most L' lie within distance h of v. This is not demonstrated; Property P3 only guarantees that low-degree vertices are pairwise at distance at least h, and does not by itself bound the number of such vertices in a radius-h ball by a universal constant. Since the proof of R_v = 1+O(1/log d) rests on this case, the authors should supply the missing counting or probabilistic argument, for example using P(d_v ≤ L) and the volume of a Hamming ball.
minor comments (3)
  1. [Section 2.3] The treatment of the lazy walk is informal: since Condition (i) of Lemma 2 requires a lazy (aperiodic) chain, the paper should state precisely whether all estimates are first proved for the lazy walk and then translated to the simple walk, or how the factor-2 cancellation is handled in (4).
  2. [Section 3.3, Eq. (21)] The notation E|S(t)^2| should be E|S(t)|^2, and the exponent (1−ν) in (20) should explicitly refer back to the definition in (3).
  3. [Section 3.2, Eq. (15)] The displayed formula for α is typographically ambiguous: α = log p/(p−1+(1/2)^{1+δ}) should be log(p/(p−1+2^{-(1+δ)})), and the expansion should be +O(δ) rather than −O(δ).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof derives the cover-time formula from a general first-visit-time lemma and independent structural estimates; no fitted parameter is renamed as a prediction. Theorem 1's displayed formula is inverted relative to the paper's own §3.1 derivation, but that is an internal consistency issue, not a circular reduction.

full rationale

The paper's derivation chain is not circular. The central device, Lemma 2 (the first visit time lemma), is quoted from the authors' earlier paper [7], but it is a parameter-free general statement about reversible Markov chains with explicit hypotheses (mixing, Tπ_v = o(1), lower bound on |R(T,z)|); the present paper verifies these hypotheses for Q_{n,p} (Sections 2.3-2.4) rather than assuming the cover-time conclusion. Lemma 3 from Cooper-Frieze-Radzik [9] is likewise a general auxiliary lemma used only to verify condition (ii) of Lemma 2; it is not fitted to reproduce tcov ~ ndp log(2p/(2p-1)). The structural inputs P1-P6 are proved in the appendix: conductance (Proposition 5) uses Harper's edge-isoperimetric inequality and an external expansion theorem [12]; low-degree-vertex isolation is Lemma 7.1; degree-count concentration is Section 4.4. Property P4 is a heuristic explanation in Section 4.3, not an input to the upper-bound summation (13)-(18) or to the lower-bound second-moment computation (20)-(22). No data are fitted, and no prediction is forced by definition: the upper bound solves ES(t)=1 to obtain alpha = log(2p/(2p-1)), and the lower bound shows that at t_L = (1-o(1)) ndp log(2p/(2p-1)) many degree-dε vertices remain unvisited. The only substantive issue is an internal inconsistency in Theorem 1: Eq. (1) prints tcov ~ (p/(log 2 log(2p/(2p-1)))) n log n, while Section 3.1 derives tcov ~ ndp log(2p/(2p-1)), which, since n=2^d, equals (p log(2p/(2p-1))/log 2) n log n. This is a correction/correctness problem, not a circular reduction, and it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted to data; the constants theta, delta, omega, h, L are auxiliary asymptotic variables that disappear from the leading-order formula. The proof rests on several established external theorems, including the first visit time lemma and conductance mixing bounds, none of which encode the target cover time result. No new physical or mathematical entities are introduced.

assumptions (6)
  • standard math First visit time lemma (Lemma 2) from Cooper-Frieze [7]: bounds P(A_v(t)) via R_v and p_v under mixing and return conditions.
    Used in Section 3 to express the probability a vertex is unvisited; it is an established general lemma, not tailored to the hypercube subgraph.
  • standard math Lemma 3 from Cooper-Frieze-Radzik [9]: Condition (ii) of the first visit time lemma holds when T=o(n^3), T pi_v=o(1), and R_v is bounded by a constant.
    Invoked in Section 2.1 to justify the first visit time lemma conditions for Q_{n,p}.
  • standard math Conductance-based mixing bound (6) from Jerrum-Sinclair: |P_u^{(t)}(x)-pi_x| <= (pi_x/pi_u)^{1/2}(1-Phi^2/2)^t.
    Used in Section 2.3 to set T = log^7 n; standard tool for reversible Markov chains.
  • standard math Harper's edge isoperimetric inequality for the hypercube, Eq (23): min edge boundary >= |S|(d-log_2 |S|).
    Used in Section 4.1 to bound conductance for sets of intermediate size.
  • standard math Expander and giant-component results from Ajtai-Komlos-Szemeredi [1] and Erde-Kang-Krivelevich [12, Theorem 1.4].
    Used in Case 2 of the conductance proof in Section 4.1 to obtain an expander subgraph of Q_{n,p}.
  • domain assumption The theorem's domain assumption d epsilon >= theta log d, equivalently p >= 1/2(1+theta log d/d), so Q_{n,p} is connected with high probability.
    This parameter regime is the scope of Theorem 1; the proofs of isolation and minimum degree rely on it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Cover time of random subgraphs of the hypercube." pith.science (2026). https://pith.science/paper/G2CVSDH2

@misc{pith2026250603375,
  author       = {Pith},
  title        = {Pith review of: Cover time of random subgraphs of the hypercube},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/G2CVSDH2}},
  note         = {Machine review of arXiv:2506.03375}
}
abstract

$Q_{n,p}$, the random subgraph of the $n$-vertex hypercube $Q_n$, is obtained by independently retaining each edge of $Q_n$ with probability $p$. We give precise values for the cover time of $Q_{n,p}$ above the connectivity threshold.

Discussion (0). Sign in to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections

    math.PR 2026-07 accept novelty 7.0 of 10

    Cover time of slow continuous-time BRW on the b-ary Hamming cube is x_★d plus λ^{-1}log d (b>2) or χ^{-1}log log d (b=2), up to O_P(1).

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [7]

    Cooper and A

    C. Cooper and A. M. Frieze, The cover time of the giant component of Gn,p. Random Structures and Algorithms, 32 (2008) 401-439

    work page 2008

  2. [1]

    Ajtai, J

    M. Ajtai, J. Koml´ os, and E. Szemer´ edi. Largest random component of ak–cube. Com- binatorica, 2(1):1–7, (1982)

    work page 1982

  3. [2]

    Aldous and J

    D. Aldous and J. A. Fill. Reversible Markov Chains and Random Walks on Graphs. Unfinished monograph, 2002 (Recompiled version, 2014)

    work page 2002

  4. [3]

    Beveridge, A

    A. Beveridge, A. Frieze, and C. McDiarmid. Random minimum length spanning trees in regular graphs. Combinatorica, 18(3):311–333, (1998)

    work page 1998

  5. [4]

    Bollob´ as, Complete matchings in random subgraphs of the cube

    B. Bollob´ as, Complete matchings in random subgraphs of the cube. Random Structures and Algorithms 1 (1990) 95-104

    work page 1990

  6. [5]

    Y. D. Burtin, On the probability of connectedness of a random subgraph of the n-cube. (in Russian) Problemy Peredaci Informacii 13 (1977) 90-95

    work page 1977

  7. [6]

    Cooper and A

    C. Cooper and A. M. Frieze, The cover time of random regular graphs. SIAM Journal on Discrete Mathematics, 18 (2005) 728-740

    work page 2005

  8. [8]

    Cooper and A

    C. Cooper and A. M. Frieze, The cover time of random geometric graphs. Random Structures and Algorithms, 38 (2011) 324-349

    work page 2011

Show all 23 references
  1. [9]

    Cooper, A

    C. Cooper, A. M. Frieze and T. Radzik, The cover times of random walks on hyper- graphs. Theoretical Computer Science, 509 (2013) 51-69

    2013

  2. [10]

    Diaconis and M

    P. Diaconis and M. Shahshahani, Time to reach stationarity in the Bernoulli-Laplace diffusion model, SIAM J. Math. Anal., 18, 208–218 (1987)

    1987

  3. [11]

    Diaconis, R

    P. Diaconis, R. L. Graham and J. A. Morrison, Asymptotic analysis of a random walk on a hypercube with many dimensions, Random Structures and Algorithms, 1(1) (1990) 51-72

    1990

  4. [12]

    J. Erde, M. Kang and M. Krivelevich. Expansion in supercritical random subgraphs of the cube and its consequences. Random Structures and Algorithms, 65 (2024) 576-600

    2024

  5. [13]

    Feller, An Introduction to Probability Theory, Volume I

    W. Feller, An Introduction to Probability Theory, Volume I. (Second edition) Wiley (1960)

    1960

  6. [14]

    A. M. Frieze and M. Karo´ nski.Introduction to Random Graphs. Cambridge University Press, (2015)

    2015

  7. [15]

    D. A. Levin and Y. Peres. Markov Chains and Mixing Times . American Mathematical Society, (2017)

    2017

  8. [16]

    L. H. Harper. Optimal numberings and isoperimetric problems on graphs. J. Combina- torial Theory 1, 385–393, (1966). 11

    1966

  9. [17]

    Jerrum and A

    M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: an approach to approximate counting and integration. In Approximation Algorithms for NP-hard Prob- lems. (D. Hochbaum ed.) PWS (1996) 482-520

    1996

  10. [18]

    Matthews

    P. Matthews. Covering problems for Brownian motion on spheres. Ann. Prob. 16 (1988) 189-199

    1988

  11. [19]

    Matthews

    P. Matthews. Some sample path properties of a random walk on the cube. J. Theor. Probab. 2 (1989) 129–146. 4 Appendix: Conductance and other technical details 4.1 Conductance of Qn,p The conductance Φ = Φ G of a graph G = (V, E) is defined as ΦG = min S⊂V (G) 0<π(S)≤1/2 e(S : ...

    1989

  12. [20]

    Moreover, if dε = (i − 1 +θ) logd, where i is a fixed integer and θ ∈ (0, 1) constant, the minimum degree δ is i

    If dε = ω → ∞there are no vertices of degree zero. Moreover, if dε = (i − 1 +θ) logd, where i is a fixed integer and θ ∈ (0, 1) constant, the minimum degree δ is i

  13. [21]

    If ε is constant then δ ≥ α0dε for some constant α0 ∈ (0, 1). Proof. Case 1. The expected number of vertices of degree zero is nqd which tends to zero for any dε = ω → ∞. Let Xj denote the number of vertices of degree j. Then EXj = n d j pjqd−j = d j (1 + ε)j(1 − ε)d−j (31) So...

  14. [22]

    No two vertices of degree at most L are within distance h of each other. 15

  15. [23]

    If ε ≤ 1/100, no two vertices of degree at most (101/100)dε are within distance h of each other. Proof. The probability there exist two vertices of SL are within distance ℓ ≤ h is P (h) ≤ n hX i=1 di X ℓ≤L d ℓ pℓqd−ℓ !2 = O(1)ndh d L pLqd−L 2 ≤ O(1) n dep Lq 2L dh(1 − ε)2d ≤ e...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.