{"id":"69b53b5c-c07e-4841-bf8a-858dd6a0780c","arxiv_id":"2412.13127","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For G(n,p), the largest rigidity dimension equals the minimum degree below p = C* log n/n, and equals (1/2 + o(1))np above it, up to p = o(n^{-1/2}).","lead":"This paper determines the largest dimension in which a sparse random graph is generically rigid, and it confirms a conjecture for a broad range of edge probabilities. The answer is governed by the graph's minimum degree below one threshold and by its number of edges above it.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2.2 relies on an unpublished preprint; if it fails, the 0.9n-clique bootstrap in Lemma 3.4 and both main theorems collapse.","rationale":"The reader's verdict of CONDITIONAL is appropriate. The probabilistic machinery (Chernoff bounds, union bounds, the projection argument in Lemma 3.1, and the expansion/matching arguments) appears sound and internally consistent. However, the central proof depends on a structural lemma about closed graphs in the rigidity matroid whose proof is a citation to an unpublished preprint. The paper itself flags that the lemma is not stated in the exact form required, and the provided proof sketch is too terse to verify. This is directly load-bearing: Lemma 3.4 uses Lemma 2.2 to guarantee a clique inside Ac, which is then merged with the main clique via Claim 2.4. Without that clique, the bootstrap to a 0.9n clique fails, and both main theorems collapse. I examined other potential weaknesses: the cross-edge counting in Lemma 3.4 ('less than d|A|') seems to use an incorrect pigeonhole bound, but the argument can likely be repaired by replacing d|A| with dn, so it is not a fatal flaw. Similarly, the restriction p = o(n^{-1/2}) is openly stated as a limitation, not an error. Therefore, the unverified Lemma 2.2 is the single most load-bearing concern, and the CONDITIONAL verdict is the right call until the external lemma is substantiated or replaced.","tokens_in":13241,"tokens_out":13361,"duration_ms":113543,"concrete_test":"Obtain Villányi's preprint arXiv:2312.02028 and produce a complete, self-contained derivation of Lemma 2.2 from its Lemmas 3.1 and 3.2, or prove Lemma 2.2 directly using the Lovász–Yemini theorem or other published rigidity results. If such a derivation cannot be provided, the conditional status is justified. Additionally, as a computational falsification check for small dimensions, enumerate all closed graphs on n ≤ 8 vertices in the d-rigidity matroid for d = 2 (and d = 3 if feasible) with minimum degree at least d(d+1) via a rigidity matroid oracle (e.g., SageMath or a custom rank computation) and test whether every such graph has a vertex whose neighbors form a clique; a counterexample would decisively refute Lemma 2.2 and the main theorems.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central proof hinges on Lemma 2.2 (Section 2.1.1): every closed graph in the d-rigidity matroid with minimum degree at least d(d+1) has a vertex whose neighbors induce a clique. This lemma is used in Lemma 3.4 to produce a large clique B inside the complement of the largest clique A, which is then merged with A via Claim 2.4 and the matching property of Claim 2.8. Without Lemma 2.2, Lemma 3.4 fails, and with it both Theorems 1 and 2, since both depend on obtaining a 0.9n-clique in the rigidity closure. The proof of Lemma 2.2 is not self-contained: it invokes Lemmas 3.1 and 3.2 from Villányi's unpublished preprint [22] and states that the lemma is 'not explicitly stated in the paper in the exact form we require.' No statement or verification of these external lemmas is given, and the argument in the paper merely says that otherwise a random subgraph Gπ has a 'contradictory property' without a demonstration. Thus the main theorems rest on an unverified external claim. The concern is not that the lemma is known to be false, but that the proof as written is incomplete and the correctness of both central results depends on it. A separate issue in the proof of Lemma 3.4 (cross-edge counting via 'less than d|A|') appears to be a repairable typo, not a fundamental gap.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the largest dimension d(n,p) for which an Erdős–Rényi graph G(n,p) is generically rigid in R^d. Theorem 1 shows that δ(G)-rigidity has a sharp threshold at p_c = C_* log n/n with C_* = 2/(1−log 2): for p < (1−ε)p_c the graph is a.a.s. δ(G)-rigid, and for p > (1+ε)p_c it is not. Theorem 2 shows that for C_* log n/n ≤ p = o(n^{-1/2}), G is a.a.s. d-rigid for d < (1/2−ε)np and not d-rigid for d > (1/2+ε)np, confirming a conjecture of Krivelevich, Lew, and Michaeli in this regime. The proof approach is to show that the d-rigidity closure of G(n,p) is dense and uniformly dense across vertex subsets, to use a structural lemma of Villányi to obtain a clique of linear size in the closure, and then to bootstrap this clique to the whole vertex set using matching and expansion properties. The paper also derives analogous global-rigidity corollaries.","tokens_in":13482,"tokens_out":7382,"duration_ms":65492,"significance":"If the proof can be completed, the results are significant: they give the first determination of the rigidity dimension for random graphs in a diverging-dimension regime, and they confirm a conjecture of Krivelevich, Lew, and Michaeli when p = o(n^{-1/2}), complementing the fixed-dimensional sharp threshold of Lew–Nevo–Peled–Raz. The probabilistic arguments (Lemmas 3.1 and 3.2, Claim 2.7, and the union-bound estimates in the proofs of Theorems 1 and 2) are carefully executed, and the explicit constant C_* is derived correctly. The main caveat is that the proof of a key structural lemma (Lemma 2.2) is imported from Villányi's unpublished preprint and is not reproduced, so the main theorems are conditional on an external unrefereed claim.","major_comments":[{"comment":"Lemma 2.2 is load-bearing: it is used in Lemma 3.4 to produce a clique B disjoint from the largest clique A, and both Theorems 1 and 2 depend on Lemma 3.4. The proof of Lemma 2.2, however, is not self-contained. It invokes Lemmas 3.1 and 3.2 from Villányi's unpublished preprint [22] without stating them or verifying their hypotheses, and the authors themselves note that the lemma is 'not explicitly stated in the paper in the exact form we require.' The argument that otherwise the random subgraph G_π has a 'contradictory property' is not demonstrated. This is not a minor omission: if the external lemmas fail or do not apply at the required generality, the large-clique bootstrap collapses. The authors should either provide a complete proof of Lemma 2.2 or include the precise statements and proofs of the needed results from [22].","section":"Section 2.1.1, Lemma 2.2"},{"comment":"The paper itself acknowledges that the assumption p = o(n^{-1/2}) is used critically in two places, one being 'using Villányi's Lemma 2.2.' This confirms that the dependence of Theorems 1 and 2 on Lemma 2.2 is essential rather than cosmetic. Consequently, the unverified status of Lemma 2.2 affects the central claims of the paper and must be resolved before the results can be accepted as rigorous.","section":"Section 4, open problem (1)"}],"minor_comments":[{"comment":"The sentence 'We claim that less than d|A| of these edges connect a vertex from A to a vertex from A^c' is logically valid but unusual: the pigeonhole principle gives that if there are at least d|A^c| cross-edges, then some vertex of A^c has at least d neighbors in A. The bound d|A| is weaker yet still sufficient for the later o(n^{3/2}) subtraction. Replacing 'd|A|' with 'd|A^c|' would make the argument clearer.","section":"Section 3.1, Lemma 3.4"},{"comment":"There are several typographical issues: the title contains 'SP ACES', 'F act 2.3' has an unwanted space, 'Y UVAL PELED' has spacing errors, and 'between A, B in G' should read 'between A and B in G.' These should be corrected in the final version.","section":"Throughout"},{"comment":"Since [22] is an unpublished arXiv preprint (arXiv:2312.02028), it would be helpful for the reader if the paper at least quoted Lemmas 3.1 and 3.2 of [22] in an appendix, even if full proofs are not included.","section":"Section 2.1.1, Lemma 2.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is likely correct in its probabilistic parts, but the central structural lemma is taken from an unreviewed preprint. I would encourage the editor to ask the authors to either prove Lemma 2.2 in full or coordinate with Villányi to include the necessary statements. The paper fits the journal's scope, but the current dependence on an unpublished source makes a verdict of acceptance premature."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper has a real result and a real presentation gap. The real result is a two-regime description of the largest dimension d for which G(n,p) is generically rigid: below p_c = C_* log n/n the bottleneck is minimum degree, above it up to o(n^{-1/2}) the bottleneck is edge count, giving d = (1/2+o(1))np. That confirms the Krivelevich–Lew–Michaeli conjecture in that range and gives the first diverging-dimension threshold. The probabilistic machinery—Lemmas 3.1, 3.2, and the well-spread closure argument—is careful and appears correct. The Chernoff/union-bound estimates in Claim 3.6 and Theorem 2 are executed cleanly. The global rigidity corollaries are a nice bonus.\n\nThe soft spot is exactly where the stress-test points: Lemma 2.2. It is load-bearing for both main theorems through Lemma 3.4's 0.9n-clique bootstrap, and its proof is not self-contained. The paper says the lemma is \"not explicitly stated\" in Villányi's preprint and then refers to Lemmas 3.1 and 3.2 of that preprint without stating or proving them. The 'contradictory property' of the random subgraph Gπ is asserted, not demonstrated. If Villányi's lemmas don't apply at the stated generality, the bootstrap collapses. This is not a manufactured concern; it is the one place where the logic is genuinely dependent on an external, unpublished source.\n\nTwo smaller notes. In Lemma 3.4 the line about 'less than d|A|' cross-edges is wrong as written—the correct bound from maximality is d|Ac|—but the error is harmless since both are o(n^{3/2}) under d = o(n^{1/2}). Also, Theorem 2 is explicitly restricted to p = o(n^{-1/2}); Conjecture 1 remains open beyond that, which the paper says plainly.\n\nBottom line: if Villányi's lemma checks out, the paper is solid and publishable. The right move is to send it to a competent referee with a specific request to verify Lemma 2.2, or ask the authors to reproduce the required lemmas or prove them in an appendix. This is a paper worth engaging with, not a desk reject.","headline":"Two clean threshold results for high-dimensional rigidity of G(n,p), built on careful probabilistic work—but the central large-clique lemma relies on an unpublished preprint and needs verification.","tokens_in":14091,"tokens_out":4143,"would_cite":true,"duration_ms":36105,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C80","52C25","05B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper determines the largest dimension in which a random graph is rigid, up to a sharp crossover from the minimum-degree bottleneck to the edge-count bottleneck.","keywords":["random graphs","generic rigidity","rigidity matroid","minimum degree","Erdős–Rényi","global rigidity","threshold","high-dimensional rigidity"],"falsifier":"Find a closed graph in the $d$-rigidity matroid with minimum degree at least $d(d+1)$ and no vertex whose neighborhood is a clique; such a graph for any $d$ would falsify Lemma 2.2 and hence the proof of both theorems. Concretely, one could verify Lemmas 3.1 and 3.2 of Villányi's preprint arXiv:2312.02028 and check whether they imply the lemma as stated for all $d \\geq 1$, or search computationally for a counterexample at small $d$.","tokens_in":12978,"feed_emoji":"📐","tokens_out":8119,"duration_ms":61062,"temperature":0.7,"pith_summary":"The paper determines the largest dimension $d$ in which an Erdős–Rényi random graph $G(n,p)$ is generically rigid, for all $p$ up to $o(n^{-1/2})$. Below the critical probability $p_c = C_* \\log n / n$ with $C_* = 2/(1-\\log 2) \\approx 6.52$, the graph is a.a.s. rigid exactly up to its minimum degree $\\delta(G)$; above $p_c$, the graph is a.a.s. $d$-rigid precisely for $d < (1/2 + o(1))np$. The second result confirms a conjecture of Krivelevich, Lew, and Michaeli in this range. The point $p_c$ is where the minimum degree ceases to be smaller than half the average degree, so the bottleneck switches from the sparsest vertex to the total number of edges.","feed_headline":"Random graph rigidity pinned to minimum degree and edge count","feed_subtitle":"Below a critical density the minimum degree rules; above it, the edge count does","key_machinery":"The central objects are the $d$-rigidity matroid and its closure $C_d(G)$, the graph of all edges whose rigidity-matrix rows lie in the span of the rows of $G$. The proof shows this closure is dense using a vector-sampling lemma (Lemma 3.1) applied simultaneously to projections $C_{d,A}(G)$ for every $A$ of size at most $0.9n$, giving uniformity across subsets. A structural lemma of Villányi — that a closed graph with minimum degree at least $d(d+1)$ has a vertex whose neighbors form a clique — then produces a $0.9n$-clique in the closure. The final bootstrap uses Fact 2.3 (a vertex outside a clique with at least $d$ neighbors in it can be added to the clique in the closure) and Claim 2.4 (a matching of $\\binom{d+1}{2}$ edges between two cliques merges them), driven by the expansion of $G(n,p)$.","core_discovery":"For $G \\sim G(n,p)$, the paper proves that the $d$-rigidity closure $C_d(G)$ is dense and evenly distributed across vertex subsets, which yields a clique of $0.9n$ vertices in the closure. Using the expansion of $G$, the clique is then bootstrapped to the entire vertex set, showing $C_d(G)$ is complete and $G$ is $d$-rigid. Theorem 1 states that for $p < (1-\\varepsilon) C_* \\log n / n$, $\\mathrm{P}(G \\text{ is } \\delta(G)\\text{-rigid}) \\to 1$, and for $p > (1+\\varepsilon) C_* \\log n / n$ it tends to $0$. Theorem 2 states that for $C_* \\log n / n \\leq p = o(n^{-1/2})$, $\\mathrm{P}(G \\text{ is } d\\text{-rigid}) \\to 1$ for $d < (1/2 - \\varepsilon)np$ and $\\to 0$ for $d > (1/2 + \\varepsilon)np$. These statements also imply that a.a.s. $G$ is globally $(\\delta(G)-1)$-rigid below $p_c$ and globally $d$-rigid for $d < (1/2 - \\varepsilon)np$ above $p_c$.","pith_inferences":["The authors' method suggests that the rigidity threshold for $p$ bounded away from $0$ is tied to the edge-count condition $|E(G)| \\geq dn - \\binom{d+1}{2}$; they conjecture this is the exact criterion, and it is verified by numerical experiments.","A consequence the authors leave implicit: the same proof structure may apply to any 1-extendable abstract rigidity matroid, since the closure and clique-bootstrap steps are matroid-theoretic.","The assumption $p = o(n^{-1/2})$ is not intrinsic: the bottleneck is the size of the matching needed between two cliques, which grows like $d^2 \\sim n^2 p^2$; removing it would require a different way to merge cliques or a stronger expansion argument."],"forward_implications":["For $p$ below $(1-\\varepsilon)p_c$, a.a.s. the largest dimension in which $G(n,p)$ is rigid equals the minimum degree $\\delta(G)$.","For $C_* \\log n / n \\leq p = o(n^{-1/2})$, a.a.s. the largest rigid dimension is $(1/2 + o(1))np$, confirming the edge-count bottleneck is sharp in this range.","Below $p_c$ the graph is a.a.s. globally $(\\delta(G)-1)$-rigid; above $p_c$ it is a.a.s. globally $d$-rigid for $d < (1/2 - \\varepsilon)np$.","The critical constant $C_* = 2/(1-\\log 2) \\approx 6.52$ marks the crossover where the minimum-degree bottleneck is replaced by the edge-count bottleneck."],"supporting_citations":[{"why":"Supplies Lemma 2.2, the structural lemma that a closed graph with minimum degree at least $d(d+1)$ has a vertex whose neighbors form a clique; this is the load-bearing external input.","marker":"[22]"},{"why":"Provides the overall strategy (dense closure, large clique, bootstrap) and the fixed-dimensional sharp threshold result that this paper extends to diverging $d$.","marker":"[19]"},{"why":"States the conjecture that Theorem 2 confirms in the range $p = o(n^{-1/2})$, and supplies the weaker rigid-partition bound the paper improves.","marker":"[17]"},{"why":"The Asimow–Roth theorem that generic rigidity is equivalent to rank of the rigidity matrix, on which the definition of $d$-rigidity and the matroid rest.","marker":"[1]"},{"why":"Jordán's result that every $(d+1)$-rigid graph is globally $d$-rigid, used to derive the global rigidity corollaries.","marker":"[13]"},{"why":"Supplies the standard random graph facts for the minimum-degree asymptotics and the small-$p$ connectivity regime used in Theorem 1.","marker":"[4]"}],"fun_headline_variants":["Rigidity of random graphs flips at critical density","Min degree rules below, edge count above in random graphs","Critical density separates two regimes of random graph rigidity","Random graph rigidity: min degree vs edge count at threshold"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument rests on Villányi's lemma that every closed graph in the $d$-rigidity matroid with minimum degree at least $d(d+1)$ has a vertex whose neighbors induce a clique; the authors note this lemma is not stated in the exact form they require and is drawn from an unpublished preprint. If that lemma fails in the needed generality, the construction of the $0.9n$-clique in the closure collapses, and with it both main theorems.","fun_headline_variants_meta":{"raw":{"variants":["Rigidity of random graphs flips at critical density","Min degree rules below, edge count above in random graphs","Critical density separates two regimes of random graph rigidity","Random graph rigidity: min degree vs edge count at threshold"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000345,"raw_usage":{"total_tokens":1921,"prompt_tokens":1000,"completion_tokens":921,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":616,"completion_tokens_details":{"reasoning_tokens":856}},"tokens_in":616,"tokens_out":921,"duration_ms":7107,"temperature":1.0,"reasoning_tokens":856,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T13:24:24.743771+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a closed graph in the $d$-rigidity matroid with minimum degree at least $d(d+1)$ and no vertex whose neighborhood is a clique; such a graph for any $d$ would falsify Lemma 2.2 and hence the proof of both theorems. Concretely, one could verify Lemmas 3.1 and 3.2 of Villányi's preprint arXiv:2312.02028 and check whether they imply the lemma as stated for all $d \\geq 1$, or search computationally for a counterexample at small $d$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the overall strategy (dense closure, large clique, bootstrap) and the fixed-dimensional sharp threshold result that this paper extends to diverging $d$."},{"cited_title":"Asimow and B","cited_arxiv_id":null,"evidence_quote":"The Asimow–Roth theorem that generic rigidity is equivalent to rank of the rigidity matrix, on which the definition of $d$-rigidity and the matroid rest."},{"cited_title":"Jord´ an","cited_arxiv_id":null,"evidence_quote":"Jordán's result that every $(d+1)$-rigid graph is globally $d$-rigid, used to derive the global rigidity corollaries."},{"cited_title":"Bollob´ as and B","cited_arxiv_id":null,"evidence_quote":"Supplies the standard random graph facts for the minimum-degree asymptotics and the small-$p$ connectivity regime used in Theorem 1."}],"review_version":1}