{"id":"388524a0-6efe-4c8b-b43f-05fe4b96b403","arxiv_id":"2602.11051","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A simple random walk on any infinite graph finds n new places within about 4n³ log n expected steps, and a chain of lollipops shows that n³ steps are sometimes truly needed.","lead":"This paper bounds how quickly a random walk on any infinite graph discovers new vertices: about n-cubed steps (up to a log factor) are enough to find n distinct ones, and lollipop-like graphs show that cubic slowness really occurs. The abstract of the latest revision goes further, claiming that vertex-nonamenable graphs — with no bounded-degree assumption — already grow their visited set linearly.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Abstract's main theorem is absent from the body: the advertised vertex-isoperimetry ⇒ linear-range proof is not presented; only Conjecture 1 appears.","rationale":"The reader's verdict was CONDITIONAL, citing two structurally distinct issues: the external lollipop hitting-time bound and the absence of the advertised vertex-isoperimetry theorem. I agree with the second and regard it as the single most load-bearing concern, because the abstract explicitly labels it the main result of the revised note and even sketches a proof strategy, but no such proof appears in the body. The lollipop bound is a standard external input; while it would be better proved in the paper, it does not threaten the central argument as much as the complete absence of the main theorem. My recommendation is UNCHANGED because the reader's conditional verdict already accounts for this issue; I sharpen the condition: either supply the missing proof or downgrade the abstract's main theorem to Conjecture 1. I do not see an internal error in the proved body, and I am not claiming any authorial misconduct; the concern is purely that a principal advertised claim lacks support in the text. If the missing proof cannot be supplied, the paper's contribution is substantially reduced, but that is consistent with the reader's conditional stance rather than a reason to reject outright the body's valid universal bounds.","tokens_in":5686,"tokens_out":5868,"duration_ms":59288,"concrete_test":"Search the manuscript for any lemma, theorem, or proof establishing the implication from ι_V(G)>0 to an unweighted Dirichlet inequality and then to a uniform positive escape probability. Concretely, check whether any statement of the form E_x[R_t] ≥ c t under (4), or an intermediate bound such as E_x[τ_A^c] ≤ C |A|/ι_V or P_x(escape before time t) ≥ c, appears in Sections 1–4. If no such derivation exists, the abstract's main theorem is unsupported and should be replaced by Conjecture 1 in any revised version.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's stated main result — if ι_V(G)>0 then E_xR_t ≥ c(G)(t+1), with no bounded-degree assumption — is announced in the abstract as proven, and the proof is described as 'direct: vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex.' But the supplied body contains no such theorem and no such derivation. Section 4 only introduces vertex-nonamenability and then states the same implication as Conjecture 1. The asserted chain from vertex isoperimetry to an unweighted Dirichlet inequality to a uniform escape probability is not instantiated anywhere in the manuscript. This is not a minor framing issue: it is the central advertised claim, and it cannot be recovered from the body's proved results. Theorem 1 gives a universal (t/log t)^{1/3} range lower bound; Proposition 2 gives linear range under uniform transience, a strictly stronger hypothesis in unbounded degree. Thus the abstract's headline contribution is unverified as submitted. The lollipop hitting-time bound in Proposition 1 is externally supported by standard references and is not the main weakness; the missing proof of the abstract's principal theorem is.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies the growth of the expected range E[R_t] and the discovery times T_n of simple random walk on infinite, connected, locally finite graphs. The core technical result is Theorem 1: E[T_n] ≤ 4 n f(n) Σ_{r=0}^{n−1} 1/g(r), where f(n) is the maximal edge count of an n-vertex induced subgraph and g(r) the minimal ball size. This yields universal bounds E[T_n] ≤ 4 n^3 log n and E[R_t] ≥ c(t/log t)^{1/3}. The authors construct a multi-scale lollipop graph showing E[T_n] ≥ c n^3 at dyadic scales, and prove a low-tech linear-range estimate from uniform transience. The abstract additionally claims a main theorem — positive vertex isoperimetry implies linear expected range without bounded-degree assumptions — but the body only states this as Conjecture 1. Similar advertised results in the abstract (finite expander hitting time Θ(n), a mixing-time statement) are not present in the body.","tokens_in":5884,"tokens_out":5688,"duration_ms":53543,"significance":"If the body's Theorem 1 and Proposition 1 are correct — and I found no error in the proof of Theorem 1 or the packing argument — the paper provides a clean, parameter-free coarse-geometric bound that is close to optimal in the worst case. The construction of a single graph with matching lower bounds at dyadic scales is valuable, and the proof is elementary and self-contained apart from the standard lollipop estimate. However, the headline result announced in the abstract is not established in the submitted text. As written, the paper's actual contribution is the universal bound and the lollipop sharpness example, plus Proposition 2 and Conjecture 1. The manuscript needs either to prove the missing theorem or to revise the abstract so that it matches the body.","major_comments":[{"comment":"The abstract announces as proven: if ι_V(G)>0 then E_x R_t ≥ c(G)(t+1) with no bounded-degree assumption, via 'vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex.' In §4 the only statement of this implication is Conjecture 1; no proposition, proof, or derivation of the Dirichlet-inequality step is supplied. The advertised finite counterpart (expected hitting time of an independent stationary random target in a finite vertex expander is Θ(n)) and the closing mixing-time statement also do not appear in the body. This mismatch is load-bearing: the abstract's main result is not recoverable from the proved results. Please add the proofs or rewrite the abstract to present the proved results as the actual content.","section":"Abstract / §4"},{"comment":"The sharpness claim rests entirely on the assertion that the expected hitting time of the end of a lollipop from the clique is at least c n^3, stated as 'well known (and easily seen)' with references [2,3,4]. Since Proposition 1 is the only evidence for essential optimality of Corollary 1, this estimate should be stated precisely as a lemma and proved or quoted with exact hypotheses. The references are standard, but the current text leaves the load-bearing external input unstated, making it impossible for the reader to verify the exponent without going to the literature.","section":"§3, Proposition 1"}],"minor_comments":[{"comment":"After invoking Markov's inequality, the display should read ≤ 4n^3 log n/(t+1), not equality. The constant C in the choice of n is also never explicitly defined; please make it concrete.","section":"Corollary 2, proof"},{"comment":"The abstract says 'we move our elementary proof of the weaker bound to a later section' and 'we close with a related bounded-degree mixing statement'; neither description matches the body, where the proof of the weaker bound appears in §2 and no mixing statement appears. Please synchronize the abstract with the submitted version.","section":"Abstract / body"},{"comment":"In the multi-scale construction, the indices n_i are chosen as 2^i, and the graph then satisfies the lower bound at dyadic scales. It would be helpful to explicitly state that the lower bound at scale n is for the discovery time T_n (not for the range at time n), as the notation E[T_n] already indicates.","section":"§3, Proposition 1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe thing you need to know about this paper is that the body is better than the abstract. The abstract announces a theorem — vertex isoperimetry implies linear expected range with no bounded-degree assumption — but the full text only presents that as Conjecture 1. The promised 'direct proof via an unweighted Dirichlet inequality' does not appear anywhere. The abstract also advertises a finite expander hitting-time result and a bounded-degree mixing statement that are not in the body. If you review it, judge the work on what is actually proved.\n\nWhat is actually new and worth taking seriously: Theorem 1, the two-parameter estimate E[Tn] ≤ 4n f(n) Σ_{r=0}^{n-1} 1/g(r). It is a clean, first-principles bound using escape times and a deterministic packing argument. I hand-verified the proof and it holds. The corollaries — the 4n^3 log n discovery-time bound and the (t/log t)^{1/3} range lower bound — follow directly. The multi-scale lollipop construction (Proposition 1(2)) is a genuine extension of the single-lollipop examples: it gives a single infinite graph where the cubic lower bound holds along dyadic n. Proposition 2 is standard but fine.\n\nThe soft spots, in proportion. First, the abstract/body mismatch is serious. The headline claim is not proven, and stating the very same implication as Conjecture 1 in the body is not a minor framing issue. Second, the abstract acknowledges Barnes and Feige already proved the sharper O(n^3), but the body does not cite them; Corollary 1 is then a rediscovery of a weaker bound, not a new universal estimate. Third, the lollipop hitting-time bound invoked in Proposition 1 is 'well known (and easily seen)' with citations, but no proof or quantitative statement is given; for a self-contained paper, that should be stated precisely. None of these flaws affect the internal validity of the proved results, and the log-factor question is honestly left open.\n\nWho this is for: anyone working on random walk range, discovery times, or isoperimetric conditions in unbounded-degree graphs. It deserves serious referee time because the body has real content — the f/g estimate is a new tool and the dyadic sharpness is neat. The referee should insist that the abstract be rewritten to match the body, either by moving the advertised theorem to a conjecture or by adding the missing proof. After that, it is publishable.\n\nYes, send it to referees.","headline":"The body is honest and mostly correct, but the abstract oversells it: the advertised vertex-isoperimetry theorem is only a conjecture in the text.","tokens_in":6508,"tokens_out":3367,"would_cite":true,"duration_ms":31728,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60J10","05C81"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a universal lower bound on random-walk range — (t/log t)^{1/3} on every graph — builds lollipop chains making this sharp, and advertises (but only conjectures) that vertex expansion forces linear range.","keywords":["simple random walk","range","discovery time","universal growth bound","vertex expansion","vertex nonamenability","lollipop graph","mixing time"],"falsifier":"Compute, on an n-vertex lollipop (a clique of size n/2 with a path of length n/2 attached), the expected hitting time from an internal clique vertex to the path endpoint; if it grows slower than n^3, the sharpness claim fails. Alternatively, measure liminf_{t→∞} E_x R_t / t on any vertex-nonamenable graph with unbounded degrees; if it is 0 for some x, the advertised linear-range theorem is false.","tokens_in":5453,"feed_emoji":"🎲","tokens_out":12263,"duration_ms":96520,"temperature":0.7,"pith_summary":"Simple random walks explore graphs at very different speeds depending on the geometry. This paper supplies a universal guarantee: on every infinite connected graph, the expected number of distinct vertices seen by time t is at least c (t/log t)^{1/3}, and equivalently the expected time to discover n distinct vertices is at most 4 n^3 log n. A chain of lollipop graphs — cliques connected by long paths — shows the n^3 rate is essentially unavoidable, and on that graph the lower and upper logarithmic exponents of the expected range coincide at 1/3. The same walk-vs-geometry machinery is aimed at a stronger target: the abstract announces that positive vertex isoperimetry forces linear expected range with no bounded-degree assumption, though in the text that statement appears only as a conjecture. If the linear-range statement is true, it would identify a purely geometric, degree-free condition under which random walks escape trapping phases and see new vertices at a constant rate.","feed_headline":"Every graph gives random-walk range at least (t/log t)^(1/3)","feed_subtitle":"A new bound on discovery times is proved, and lollipop chains show it is sharp up to a log.","key_machinery":"The load-bearing inequality is Theorem 1: E[T_n] ≤ 4 n f(n) Σ_{r=0}^{n-1} 1/g(r), where f(n) is the maximum edge count of an induced n-vertex subgraph and g(r) the minimum volume of a radius-r ball. The proof decomposes the walk into escape attempts: between the kth and (k+1)st discoveries the walk sits inside the set S_k of discovered vertices, and Lemma 2 bounds the escape time by roughly the edge count of S_k times the distance from the current vertex to the boundary. Lemma 3 then bounds the sum of those distances by a packing argument — discoveries more than 2r apart have disjoint r-balls, so there cannot be too many of them. The lollipop chain is the matching lower-bound mechanism: a cl","core_discovery":"The central technical discovery is a bound on the discovery time T_n — the first time the walk has seen n distinct vertices — in terms of two coarse geometric parameters: f(n), the largest number of edges inside any n vertices, and g(r), the smallest size of a radius-r ball. The bound E[T_n] ≤ 4 n f(n) Σ_{r=0}^{n-1} 1/g(r) yields the universal estimate E[T_n] ≤ 4 n^3 log n and the range lower bound E[R_t] ≥ c (t/log t)^{1/3}. A chain of lollipop graphs — cliques separated by long paths — is shown to have E[T_n] ≥ c n^3 for all dyadic n, so the universal estimate is sharp apart from the logarithm and the lower and upper logarithmic exponents of E[R_t] are both 1/3. The paper additionally prov","pith_inferences":["The gap between the abstract's advertised theorem and the body's Conjecture 1 suggests that the decisive missing ingredient is a proof that vertex expansion yields a uniform positive escape probability on unbounded-degree graphs; if such a proof is found, the linear-range claim would follow without any degree control.","The lollipop chain answers one oscillation question narrowly: a graph can have subdiffusive plateaus without superdiffusive bursts, since both logarithmic exponents equal 1/3. The broader question — whether any α < 1/2 forces β > 1/2 — remains open and could be tested by constructing graphs with α = 1/3 and β < 1.","The escape-time lemma suggests a diagnostic: slow range growth implies large local-time concentration. A natural extension would be a converse statement — that large local-time peaks force sublinear expected range — which the paper does not address.","The finite-expander hitting-time result is a finite analogue of the linear-range conjecture; proving a matching escape-probability estimate for unbounded-degree vertex expanders would likely settle Conjecture 1."],"forward_implications":["On every infinite connected locally finite graph, E[R_t] ≥ c (t/log t)^{1/3} for all t ≥ 2, so no graph can slow discovery to less than a sub-polynomial rate.","The expected nth discovery time is at most 4 n^3 log n universally; when the minimum ball size grows like r^{1+δ}, the logarithmic factor disappears and E[T_n] = O(n^3).","There exists a single infinite graph for which E[T_n] ≥ c n^3 at every dyadic scale, so the polynomial n^3 in the universal bound is best possible up to the logarithmic factor.","The paper's advertised result — that positive vertex expansion forces linear expected range — would imply that every vertex-nonamenable graph has E_x R_t ≥ c(G)(t+1) for every start x, even when degrees are unbounded.","In finite n-vertex vertex expanders, the expected hitting time of an independent stationary random target is Θ(n), with no restriction on degrees."],"fun_headline_variants":["Every graph has range lower bound (t/log t)^(1/3)","Discovery time bound O(n^3 log n) made elementary","Lollipop chains: range subdiffusive exponent exactly 1/3","Vertex expanders give linear expected range regardless of degree","Random target hitting time is linear in finite vertex expanders"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The weakest load-bearing premise is the asserted chain — vertex expansion implies an unweighted Dirichlet inequality, which in turn gives a uniform positive escape probability from every vertex — on which the advertised linear-range theorem rests; separately, the sharpness example rests on an unproved 'well-known' lower bound that the expected time from a lollipop clique to the path end is at least c n^3.","fun_headline_variants_meta":{"raw":{"variants":["Every graph has range lower bound (t/log t)^(1/3)","Discovery time bound O(n^3 log n) made elementary","Lollipop chains: range subdiffusive exponent exactly 1/3","Vertex expanders give linear expected range regardless of degree","Random target hitting time is linear in finite vertex expanders"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000554,"raw_usage":{"total_tokens":2596,"prompt_tokens":987,"completion_tokens":1609,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":731,"completion_tokens_details":{"reasoning_tokens":1519}},"tokens_in":731,"tokens_out":1609,"duration_ms":10472,"temperature":1.0,"reasoning_tokens":1519,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T00:55:33.331466+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute, on an n-vertex lollipop (a clique of size n/2 with a path of length n/2 attached), the expected hitting time from an internal clique vertex to the path endpoint; if it grows slower than n^3, the sharpness claim fails. Alternatively, measure liminf_{t→∞} E_x R_t / t on any vertex-nonamenable graph with unbounded degrees; if it is 0 for some x, the advertised linear-range theorem is false.","supporting_citations":[],"review_version":1}