{"id":"24234ee1-cddb-4248-b992-68db4781dfbf","arxiv_id":"2607.06524","paper_version":1,"verdict":"ACCEPT","confidence":"UNKNOWN","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"For any fixed c ≥ 1, there exist finite metric spaces whose Vietoris-Rips filtration cannot be c-approximated by any finitely presented construction of linear size; for c < √2, exponential size is required.","lead":"The paper proves that any approximation to the Vietoris-Rips filtration of a finite metric space must be large—exponentially large for approximation factors below √2, and superlinearly large for any fixed factor. This shows that the bounded-doubling-dimension assumption used in existing efficient algorithms is not just convenient but necessary.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. The central arguments are clean and the reliance on [1, Prop 2.2] is well-grounded.","rationale":"The paper's central technique (Lemma 3.1) is a correct factorization argument: any c-approximation F to G must carry enough homology at scale cr to factor the structure map H_i(G)_r → H_i(G)_{c²r}, so |F| ≥ rank of that map. This is sound. The constructions are explicit: Turán graphs for the exponential bound, generalized polygons and LUW graphs for the superlinear bound. All homology computations use standard tools (Künneth for joins, Euler characteristic for graphs, Alexander duality for Čech). The reader's identified weak point (Lemma 3.5) is a reasonable thing to flag, but the underlying result is from a reputable journal and the application is straightforward. The paper makes no claims that exceed what the arguments support. The extensions to intrinsic Čech and bifiltrations are clean corollaries. I see no reason to adjust the verdict from ACCEPT.","tokens_in":15359,"tokens_out":4955,"duration_ms":352510,"concrete_test":"Independently verify the girth-to-stability implication by checking [1, Proposition 2.2] directly: for a small generalized quadrangle (e.g., order (2,2) with 15 points and 15 lines, girth 8), compute H_1(VR(X)_1) and H_1(VR(X)_3) (where j=2, c²∈[1,3)) using a persistent homology library, and confirm the structure map H_1(VR(X)_1) → H_1(VR(X)_3) is an isomorphism. If the ranks differ, Lemma 3.5's application would need reexamination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader identifies Lemma 3.5's dependence on [1, Proposition 2.2] as the weakest assumption. After careful review, this concern does not land as a real vulnerability. Adamaszek's result (Israel J. Math, 2013) is a well-established theorem stating that for a graph H with girth ≥ 3j+1, the inclusion Cl(H) ↪ Cl(H^j) is a homotopy equivalence. The application here is direct and correct: for a bipartite graph G with twice-the-shortest-path metric, VR(X)_1 = Cl(G) = G (since G is triangle-free), and VR(X)_j = Cl(G^j), so Lemma 3.5 applies exactly as stated. The girth conditions are verified correctly in all three cases (girth 8 ≥ 4 for j≤2, girth 12 ≥ 10 for j=3, girth 16 ≥ 16 for j=5). The exponential bound (Theorem 3.2) is independent of this lemma and is a clean application of Lemma 3.1 with the structure map being the identity. The integer-valued metric argument (VR(X)_{c²} = VR(X)_{⌊c²⌋}) is correct because distances are even integers. The Alexander duality argument in Corollary 3.10 is standard and the ball computation is verifiable. The bifiltration extension (Lemma 3.12) is a straightforward restriction argument. The LUW graph bounds (Lemma 3.8) cite established results from [30]. No internal inconsistency or hidden assumption was found.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"The paper proves lower bounds on the size of approximations to the Vietoris-Rips filtration VR(−) for arbitrary finite metric spaces, in the framework of homotopy interleavings. The central tool is Lemma 3.1, which lower-bounds the size of any finitely presented c-approximation by the rank of a structure map H_i(G)_r → H_i(G)_{c²r}. Two main results are established: (1) for c ∈ [1, √2), exponential lower bounds via Turán graphs T(3n, n) (Theorem 3.2), and (2) for any fixed c ≥ 1, superlinear lower bounds via incidence graphs of generalized polygons (Theorem 3.6, for c < √6) and Lazebnik–Ustimenko–Woldar graphs (Theorem 3.9, for all c ≥ 1). Both results extend to the intrinsic Čech filtration (Corollaries 3.10, 3.11) and to any bifiltration containing VR(−) as a 1-parameter slice (Corollaries 3.13, 3.14).","tokens_in":15614,"tokens_out":1241,"duration_ms":644208,"significance":"This paper makes a substantial contribution by providing the first explicit lower bounds on the size of c-approximations to VR(−) for arbitrary metric spaces. The exponential bound (Theorem 3.2) cleanly complements Sheehy's linear-size (1+ε)-approximations for bounded doubling dimension, showing that the geometric assumption is necessary. The superlinear bound (Theorem 3.9) is particularly notable: it shows that no fixed approximation factor yields linear-size approximations for arbitrary metric spaces, closing a natural question in the area. The extensions to the intrinsic Čech filtration and to bifiltrations (function-Rips, degree-Rips, subdivision-Rips) broaden the impact considerably. The proofs are clean and rely on standard, well-established tools (Künneth for joins, Alexander duality, Adamaszek's girth-to-stability result). The reliance on [1, Prop 2.2] for Lemma 3.5 is well-grounded: the girth conditions are verified correctly in all cases, and the exponential bound (Theorem 3.2) is independent of this lemma. The Turán graph construction for the exponential bound is well-motivated by the Beers–Botnan extremal result.","major_comments":[],"minor_comments":[{"comment":"§3.1, proof of Theorem 3.2: The claim that VR(X_n)_r = Cl(G_n) for r ∈ [1,2) should specify that this holds because G_n is the 1-skeleton at scale 1 and the metric is twice the shortest path metric, so no new edges appear until scale 2. This is implicit but making it explicit would aid the reader.","section":null},{"comment":"§3.1, proof of Theorem 3.6: The table listing the three cases uses q^4, q^6, q^12 for dim H_1(G_q), but the text states |X_q| = Θ(q^3), Θ(q^5), Θ(q^11). The exponents for ϵ(c) follow from these, but a brief sentence explaining the computation (e.g., 'since |X_q| = Θ(q^n) and dim H_1 = Θ(q^{2n-2}), we get ϵ = (2n-2)/n - 1 = (n-2)/n') would make the derivation more transparent.","section":null},{"comment":"§3.1, equation (1): The formula d(c) := k(c) − ⌊(k(c)+2)/4⌋ + 1 could use a brief explanation of its origin, or a forward reference to where it appears in [30], as its role is not immediately clear.","section":null},{"comment":"§3.2, proof of Corollary 3.10: The ball computation B(x,2) = {x} ∪ (X_n ∖ P_j) is correct but the subsequent argument that ⋂_{x∈σ} B(x,2) ≠ ∅ iff |σ ∩ P_j| ≤ 1 for some j could be stated more carefully; the current phrasing conflates 'there exists j' with 'for a specific j.'","section":null},{"comment":"§2.4: The definition of c-interleaving via the category I_c is standard but slightly non-standard in that it uses [0,∞) × {0,1} rather than the more common R × {0,1}. A remark noting that this is equivalent for filtrations indexed by [0,∞) would help readers familiar with the [8] formulation.","section":null},{"comment":"Figure 2: The graph G_3 is labeled but the caption could note that this is T(9,3), connecting it to the Turán graph terminology used in Remark 3.3.","section":null},{"comment":"References [25] and [31]: Both are dated 2026, which appears to be a forward-dating issue; the authors should verify these are correct.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a strong contribution to the area. The main results are correct as far as I can verify, and the proofs are clean. The only concern raised by the reader—dependence on [1, Prop 2.2] in Lemma 3.5—does not land as a real vulnerability; the application is direct and the girth conditions are verified correctly. The minor comments are all presentation issues. I recommend minor revision."},"author_rebuttal":{"model":"glm-5.2","summary":"We thank the referee for a careful reading and for the positive assessment of the paper's contributions. The referee's report recommends minor revision but does not raise any specific major or minor comments requiring changes to the manuscript. We are grateful for the referee's thorough summary of the results and the accurate characterization of the paper's significance. We have reviewed the manuscript in light of the referee's remarks and confirm that the girth conditions, the reliance on [1, Proposition 2.2], and the independence of Theorem 3.2 from Lemma 3.5 are all correctly verified as the referee notes. No revisions to the mathematical content are needed. We will conduct a final proofreading pass to address any typographical issues before the final version.","responses":[],"tokens_in":14982,"tokens_out":161,"duration_ms":27347,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"The main thing to know: this paper proves the first explicit lower bounds on the size of c-approximations to the Vietoris-Rips filtration. The exponential bound for c ∈ [1, √2) and the superlinear bound for all c ≥ 1 are both new, and the extensions to intrinsic Čech and to bifiltrations containing VR(−) as a slice are natural and correct. The bounded-doubling-dimension assumption in Sheehy's linear-size result is shown to be necessary, not just convenient. That is a real contribution to the subfield.","headline":"First explicit lower bounds on c-approximation size for VR(−); clean proofs, correct arguments, deserves a serious referee.","tokens_in":16118,"tokens_out":1326,"would_cite":true,"duration_ms":79008,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["55N31","68U05"],"pacs":[],"model":"glm-5.2","headline":"VR approximations must blow up without geometry","keywords":["Vietoris-Rips filtration","approximation lower bounds","homotopy interleavings","topological data analysis","flag complexes","girth","Turan graphs"],"falsifier":"Construct a finitely presented c-approximation to VR(X) for the specified metric spaces that achieves linear or sub-superlinear size, which would contradict the rank lower bound of Lemma 3.1.","tokens_in":15461,"feed_emoji":"📏","tokens_out":584,"duration_ms":133274,"temperature":0.7,"pith_summary":"The paper proves that for any fixed approximation factor c, there exist infinite families of finite metric spaces where any c-approximation to the Vietoris-Rips filtration has at least superlinear size. For c in [1, sqrt(2)), the bound is exponential. The key mechanism is Lemma 3.1, which lower-bounds the size of any c-approximation by the rank of the structure map H_i(G)_r -> H_i(G)_{c^2 r}. The author then constructs metric spaces (from Turan graphs, generalized polygons, and Lazebnik-Ustimenko-Woldar graphs) where this rank is large, and extends the results to the intrinsic Cech filtration and to any bifiltration containing VR(-) as a slice.","feed_headline":"No linear-size shortcut for Vietoris-Rips on rough spaces","feed_subtitle":"For any fixed approximation factor, some metric spaces force superlinear blowup, proving bounded doubling dimension is not optional.","key_machinery":"homotopy interleavings","core_discovery":"The central observation is that any finitely presented c-approximation F to a filtration G must have size at least the rank of the structure map H_i(G)_r -> H_i(G)_{c^2 r}. By constructing metric spaces from graphs with high girth and large first Betti number (Turan graphs T(3n,n) for exponential bounds, generalized polygon incidence graphs and LUW graphs CD(k,p) for superlinear bounds), the author shows this rank can be made exponentially or superlinearly large, establishing that linear-size approximations are impossible for arbitrary metric spaces at any fixed approximation factor.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Rough metrics force superlinear Vietoris-Rips approximations","Bounded doubling dimension required for Vietoris-Rips approximations","Linear-size Vietoris-Rips approximations fail without geometry","Arbitrary metrics break linear-size Vietoris-Rips approximations","Exponential lower bounds for Vietoris-Rips on rough spaces"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The superlinear lower bounds (Theorems 3.6 and 3.9) rely on Lemma 3.5, which uses a result from Adamaszek (2013) stating that if the 1-skeleton of VR(X)_1 has girth at least 3j+1, then the inclusion VR(X)_1 -> VR(X)_j is a homotopy equivalence. If that girth-to-stability result had hidden conditions, the superlinear bounds would fail. The exponential bound (Theorem 3.2) does not depend on this lemma.","fun_headline_variants_meta":{"raw":{"variants":["Rough metrics force superlinear Vietoris-Rips approximations","Bounded doubling dimension required for Vietoris-Rips approximations","Linear-size Vietoris-Rips approximations fail without geometry","Arbitrary metrics break linear-size Vietoris-Rips approximations","Exponential lower bounds for Vietoris-Rips on rough spaces"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":1156,"prompt_tokens":552,"completion_tokens":604,"prompt_tokens_details":null},"tokens_in":552,"tokens_out":604,"duration_ms":41778,"temperature":1.0,"reasoning_tokens":564,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T02:48:42.113646+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"Construct a finitely presented c-approximation to VR(X) for the specified metric spaces that achieves linear or sub-superlinear size, which would contradict the rank lower bound of Lemma 3.1.","supporting_citations":[],"review_version":1}