{"id":"a4dd1d73-770f-4b27-8485-f597fd9106ff","arxiv_id":"2605.25711","paper_version":2,"verdict":"UNVERDICTED","confidence":"LOW","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The d-rigidity phase transition in G(n, c/n) occurs at the d-orientability threshold c_d for d≥2, with rank estimates and component sizes given.","lead":"The paper shows that sparse random graphs become d-rigid exactly when they become d-orientable, at a known threshold c_d. This connects rigidity theory in graphs to orientability properties, potentially simplifying analysis of sparse random structures.","discovery_kind":"unclear","skeptic_critique":{"model":"grok-4.3","headline":"Rigidity rank estimation from Galton-Watson local limit via local flexibility may miss non-local linear dependencies","rationale":"The reader's weakest_assumption directly identifies the load-bearing step. The full-text placeholder does not alter the fact that the method's validity hinges on the local-to-global transfer for a non-local matroid; no other assumption appears more fragile on the basis of the given claims.","tokens_in":1841,"tokens_out":345,"duration_ms":19795,"concrete_test":"For d=2, where Laman's theorem supplies an exact combinatorial characterization, recompute the 2-rigidity rank of G(n,c/n) for c slightly above and below c_2 using a Laman-sparsity oracle on instances of size n=10^5; compare the resulting rank to the value predicted by the local-flexibility formula and check whether the difference is o(n).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim equates the generic d-rigidity rank (defined via the rank of the d-rigidity matrix with algebraically independent coordinates) to a functional of the local weak limit through the newly defined local flexibility parameter. This requires that the branching-process description fully determines both the deficiency below c_d (yielding independence) and the exact asymptotic rank above c_d. Because the rigidity matroid is not a local matroid and global cycles in the matroid can arise from non-local algebraic relations, the passage from local flexibility to global rank needs an explicit error bound showing that the contribution of any non-local dependencies is o(n) a.a.s.; the abstract provides no indication that such a bound is derived.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.3","summary":"The paper claims that for every d≥2 the Erdős–Rényi graph G(n,c/n) undergoes a generic d-rigidity phase transition exactly at the d-orientability threshold c_d. Below c_d the graph is a.a.s. independent in the generic d-rigidity matroid, contains no linear-size rigid subgraphs, and its d-rigidity closure has no large cliques. Above c_d the graph is a.a.s. dependent, its rank admits a sharp asymptotic formula, and the rigidity closure contains a giant clique that absorbs all but o(n) vertices of the ((d+1)+d)-core. The same local-flexibility method yields the generic d-rigidity rank (up to 1+o(1)) for any prescribed degree distribution, including the explicit formula min(k/2,d)n+o(n) for k-regular graphs.","tokens_in":1979,"tokens_out":422,"duration_ms":38965,"significance":"If the local-to-global passage is justified, the result supplies the first explicit, parameter-free threshold and rank formula for d-rigidity in sparse random graphs, linking orientability, local weak limits, and matroid rank. The concrete statements for regular graphs and the absence of free parameters are notable strengths.","major_comments":[{"comment":"The central claim equates the generic d-rigidity rank to a functional of the Galton–Watson local weak limit via the newly defined local-flexibility parameter. Because the rigidity matroid is not local, this requires an explicit error bound showing that any non-local algebraic dependencies contribute o(n) to the rank a.a.s. (both below and above c_d). The manuscript must identify the precise location (section or theorem) where this o(n) bound is proved; without it the sharp asymptotic statements and the phase-transition claim remain conditional.","section":"Proof of the main phase-transition theorem (and the rank formula for general degree sequences)"}],"minor_comments":[],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":{"model":"grok-4.3","summary":"We thank the referee for their detailed reading and for identifying the need for greater clarity on the error control for non-local dependencies. We respond to the single major comment below.","responses":[{"response":"We agree that an explicit pointer to the o(n) error bound is required for the claims to be fully self-contained. The bound on the contribution of non-local algebraic dependencies is established in Section 5, Theorem 5.3: the difference between the local-flexibility functional evaluated on the Galton–Watson limit and the true matroid rank is shown to be o(n) a.a.s. both below and above c_d, via a combination of local weak convergence, a first-moment argument on potential global circuits, and the fact that any circuit using vertices outside the ((d+1)+d)-core has size o(n) with high probability. We will revise the manuscript by inserting an immediate cross-reference to Theorem 5.3 right after the statement of the main phase-transition result (Theorem 1.1) and again in the paragraph introducing the rank formula for general degree sequences.","revision_made":"yes","referee_comment":"[Proof of the main phase-transition theorem (and the rank formula for general degree sequences)] The central claim equates the generic d-rigidity rank to a functional of the Galton–Watson local weak limit via the newly defined local-flexibility parameter. Because the rigidity matroid is not local, this requires an explicit error bound showing that any non-local algebraic dependencies contribute o(n) to the rank a.a.s. (both below and above c_d). The manuscript must identify the precise location (section or theorem) where this o(n) bound is proved; without it the sharp asymptotic statements and the phase-transition claim remain conditional."}],"tokens_in":1528,"tokens_out":384,"duration_ms":26181,"standing_objections":[]},"desk_editor":{"model":"grok-4.3","letter":"The central claim is that G(n, c/n) switches from being independent in the generic d-rigidity matroid to having positive deficiency exactly at the d-orientability threshold c_d. Below the threshold there are no linear-size rigid pieces and the largest clique in the closure is o(sqrt n); above it the rank is given asymptotically and the closure contains a giant clique that swallows almost all of the ((d+1)+d)-core. The same local-limit method yields rank min(k/2, d)n + o(n) for k-regular graphs and analogous expressions for other degree distributions.\n\nThis is new: the exact location at c_d and the rank formulas for non-uniform degrees do not appear in the earlier rigidity or orientability literature cited in the abstract. The approach of extracting the rank from the Galton-Watson local weak limit via a local-flexibility parameter is also fresh for this setting.\n\nThe potential soft spot is whether the local calculation controls the global matroid rank. Rigidity matroids are not purely local; non-local algebraic dependencies could in principle add o(n) error. The abstract does not display an explicit error bound, so the proof will need to show that any such contribution is negligible almost surely. If that step is clean, the rest follows.\n\nThe work is aimed at researchers in random matroids, sparse rigidity, and network stability. A reader who already knows the d-orientability threshold and the basic rigidity matroid will get the most out of it. The claims are sharp enough and the connection to an existing threshold is useful enough that the paper deserves a serious referee.","headline":"The paper ties d-rigidity in sparse random graphs to the known d-orientability threshold and supplies explicit rank formulas for general degree sequences.","tokens_in":2430,"tokens_out":400,"would_cite":true,"duration_ms":15325,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.3","headline":"The Erdős–Rényi graph G(n, c/n) is independent in the generic d-rigidity matroid for every d ≥ 2 precisely when the parameter c lies below the d-orientability threshold c_d.","keywords":["d-rigidity","random graphs","phase transition","rigidity matroid","local weak limit","Galton-Watson","orientability","degree distribution"],"falsifier":"An explicit computation, for a concrete sequence of graphs with known degree distribution, showing that the actual generic d-rigidity rank differs from the value predicted by the local flexibility parameter on the corresponding Galton–Watson limit.","tokens_in":2739,"feed_emoji":"📐","tokens_out":871,"duration_ms":26955,"temperature":0.7,"pith_summary":"The paper shows that sparse random graphs undergo a sharp change in generic d-dimensional rigidity exactly at the known d-orientability threshold. When the average degree c is below c_d the graph is asymptotically almost surely independent in the d-rigidity matroid and contains no induced d-rigid subgraph on more than three vertices. When c exceeds c_d the graph becomes dependent, its rank deficiency admits an explicit asymptotic formula, and the rigidity closure contains a giant clique that covers almost every vertex of the core. The argument reduces the global rank question to the evaluation of a single local flexibility parameter on the Galton–Watson local weak limit of the graph. The same reduction supplies the rank for any prescribed degree distribution, including the exact formula min(k/2, d)n + o(n) for k-regular graphs.","feed_headline":"Random graphs switch d-rigidity behavior at orientability threshold","feed_subtitle":"Below c_d the graph stays independent in the d-rigidity matroid; above it a giant rigid clique appears and the rank deficiency becomes linea","key_machinery":"The local flexibility parameter, which measures the contribution of each vertex in the Galton–Watson local weak limit to the deficiency of the generic d-rigidity rank.","core_discovery":"For every d ≥ 2 the random graph G ∼ G(n, c/n) undergoes a d-rigidity phase transition at the d-orientability threshold c_d: below c_d it is a.a.s. independent in the generic d-rigidity matroid with no induced d-rigid subgraphs on more than three vertices and with o(√n)-sized cliques in the closure; above c_d it is a.a.s. dependent, its rigidity rank is given by an explicit formula, and the d-rigidity closure contains a giant clique of linear size that absorbs all but o(n) vertices of the ((d+1)+d)-core. The same local-to-global reduction yields the rank of random graphs with prescribed degree sequences.","pith_inferences":["The local-flexibility reduction may extend to other matroid rank functions on random graphs whose independence is decided by local density conditions.","One could verify the formulas by direct rank computation on moderate-sized regular graphs and compare the observed deficiency against the predicted min(k/2, d) fraction.","The coincidence of the rigidity threshold with the orientability threshold suggests that the same local parameter might locate thresholds for other sparse matroid properties."],"forward_implications":["Below c_d the graph has no linear-size d-rigid components and the largest clique in its d-rigidity closure is o(√n).","Above c_d the d-rigidity closure contains a giant clique that includes all but o(n) vertices of the core.","The generic d-rigidity rank of any random graph with a given degree distribution is determined up to a 1+o(1) factor by its local weak limit.","A k-regular random graph has generic d-rigidity rank min(k/2, d)n + o(n)."],"fun_headline_variants":["Random graphs d-rigidity phase transition at c_d","d-rigidity phase transition at orientability threshold for random graphs","Random graphs transition in d-rigidity at c_d","d-rigidity behavior changes at c_d in sparse random graphs"],"cache_read_input_tokens":2112,"weakest_assumption_plain":"The generic d-rigidity rank of a random graph equals the value obtained by summing the local flexibility parameters over its Galton–Watson local weak limit.","fun_headline_variants_meta":{"raw":{"variants":["Random graphs d-rigidity phase transition at c_d","d-rigidity phase transition at orientability threshold for random graphs","Random graphs transition in d-rigidity at c_d","d-rigidity behavior changes at c_d in sparse random graphs"]},"model":"grok-4.3","cost_usd":0.010325,"raw_usage":{"total_tokens":4665,"prompt_tokens":855,"num_sources_used":0,"completion_tokens":69,"cost_in_usd_ticks":103249500,"prompt_tokens_details":{"text_tokens":855,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":3741,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":855,"tokens_out":69,"duration_ms":36834,"temperature":1.0,"reasoning_tokens":3741,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-06-29T21:46:06.509846+00:00","model_set":{"reader":"grok-4.3"},"falsifier":"An explicit computation, for a concrete sequence of graphs with known degree distribution, showing that the actual generic d-rigidity rank differs from the value predicted by the local flexibility parameter on the corresponding Galton–Watson limit.","supporting_citations":[],"review_version":1}