Pith. sign in

REVIEW 1 major objections 43 references

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.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

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

T0 review · grok-4.3

2026-06-29 21:46 UTC pith:KIGOWNM4

load-bearing objection The paper ties d-rigidity in sparse random graphs to the known d-orientability threshold and supplies explicit rank formulas for general degree sequences. the 1 major comments →

arxiv 2605.25711 v2 pith:KIGOWNM4 submitted 2026-05-25 math.CO math.PR

On the d-rigidity phase transition in random graphs

Yuval Peled This is my paper
classification math.CO math.PR
keywords d-rigidityrandom graphsphase transitionrigidity matroidlocal weak limitGalton-Watsonorientabilitydegree distribution
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

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.

Core claim

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.

What carries the argument

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.

Load-bearing premise

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.

What would settle it

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.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • 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).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • 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.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

1 major / 0 minor

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.

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 (1)
  1. [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.

Simulated Author's Rebuttal

1 responses · 0 unresolved

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.

read point-by-point responses

  1. Referee: [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.

    Authors: 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: yes

Circularity Check

0 steps flagged

No significant circularity; derivation relies on external orientability threshold and local weak limit analysis

full rationale

The paper cites the d-orientability threshold c_d as known from prior literature on orientability and introduces local flexibility as a new parameter to estimate rigidity rank from the Galton-Watson local weak limit. No quoted equations or steps reduce the phase transition claim, rank estimates, or closure properties to fitted inputs, self-definitions, or load-bearing self-citations by construction. The central results on independence below c_d, rank above c_d, and giant cliques are presented as following from the local-to-global estimation approach without visible reduction to the paper's own inputs. This is the expected self-contained case for a paper importing an external threshold and deriving new matroid properties from branching process limits.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Only abstract available, so ledger is necessarily incomplete; relies on standard matroid axioms and local weak convergence but details of local flexibility are not supplied.

axioms (1)
  • domain assumption The generic d-rigidity matroid is well-defined and behaves as expected on random graphs in d dimensions.
    Invoked when stating independence or rank in the matroid.

pith-pipeline@v0.9.1-grok · 5842 in / 1253 out tokens · 49327 ms · 2026-06-29T21:46:06.509846+00:00 · methodology

0 comments
read the original abstract

We study generic $d$-dimensional rigidity in sparse random graphs. Our main result is that for every $d\ge 2$, the Erd\H{o}s--R\'enyi random graph $G\sim G(n,c/n)$ undergoes a $d$-rigidity phase transition at the known, explicit, $d$-orientability threshold $c_d$: If $c<c_d$, then $G$ is asymptotically almost surely (a.a.s.) independent in the generic $d$-rigidity matroid. Moreover, in this regime $G$ has no linear-size rigidity components: it contains no induced $d$-rigid subgraphs with more than $3$ vertices, and the largest clique in its $d$-rigidity closure has size at most $o(\sqrt n)$. If $c>c_d$, then $G$ is a.a.s. not independent in the generic $d$-rigidity matroid, and we give a sharp asymptotic estimate for its rank. In addition, the $d$-rigidity closure of $G$ has a giant clique of linear size, which contains all but at most $o(n)$ vertices of the $((d+1)+d)$-core of the graph. More generally, we compute, up to a $1+o(1)$ factor, the generic $d$-rigidity rank of random graphs with a given degree distribution. For example, we show that the uniform $n$-vertex $k$-regular graph a.a.s. has rank $\min(k/2,d)n+o(n).$ Our approach is to estimate the rigidity rank of a random graph from its Galton--Watson local weak limit, using a parameter that we call {\em local flexibility}.

Figures

Figures reproduced from arXiv: 2605.25711 by Yuval Peled.

Figure 1
Figure 1. Figure 1: Illustration of Theorem 1.1 for d = 3. The blue curve is the asymptotic value of rk3(G)/n. The red curve is the trivial edge￾density bound c/2, and the purple curve is the second bound in (1.1) with the parameters of the 4-core. The vertical lines mark the thresholds γ3 ≈ 5.1494, and c3 ≈ 5.7549. In other words, the upper bound given by (1.1) is attained asymptotically. For c < γd, the first item of Theore… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of Theorem 1.2 for d = 3. The blue curve is the asymptotic density of the largest clique in the 3-rigidity closure of G. Note that a local heuristic suggests that the ((d+ 1) +d)-core of G(n, c/n) a.a.s. contains (ˆp + o(1))n vertices. While this was proved only for d = 2 in [5], it seems likely that the same arguments work for all d. Item (1a) was conjectured in [33], as was a stronger versio… view at source ↗
Figure 3
Figure 3. Figure 3: The function ϕ(p) for d = 3 and X = Poi(c), where c = 5.1, 5.5, 5.9. On the left, c < γ3, and p = 0 is the only solution of ϕ ′ (p) = 0. In the middle, γ3 < c < c3, two additional critical points appear, but the value at p = 0 is still larger than the value at ˆp. On the right, c > c3, and the maximum is attained at ˆp. • Let nd+1, md+1 denote the number of vertices and edges in the (d+ 1)-core of Gn. Then… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

43 extracted references · 6 canonical work pages · 2 internal anchors

  1. [1]

    10, 2111–2122

    Mikl´ os Ab´ ert, Andreas Thom, and B´ alint Vir´ ag,Benjamini–schramm convergence and point- wise convergence of the spectral measure , Journal of the European Mathematical Society 16 (2014), no. 10, 2111–2122

    2014

  2. [2]

    David Aldous and J. Michael Steele, The objective method: Probabilistic combinatorial opti- mization and local weak convergence, Probability on Discrete Structures (Harry Kesten, ed.), Encyclopaedia of Mathematical Sciences, vol. 110, Springer, Berlin, 2004, pp. 1–72

    2004

  3. [3]

    Leonard Asimow and Ben Roth, The rigidity of graphs , Transactions of the American Math- ematical Society 245 (1978), 279–289

    1978

  4. [4]

    II , Journal of Mathematical Analysis and Applications 68 (1979), no

    , The rigidity of graphs. II , Journal of Mathematical Analysis and Applications 68 (1979), no. 1, 171–190

    1979

  5. [5]

    3, 419–453

    Julien Barr´ e, Marc Lelarge, and Dieter Mitsche,On rigidity, orientability and cores of random graphs with sliders , Random Structures & Algorithms 52 (2018), no. 3, 419–453

    2018

  6. [6]

    Itai Benjamini and Oded Schramm, Recurrence of distributional limits of finite planar graphs, Electronic Journal of Probability 6 (2001), 1–13

    2001

  7. [7]

    Itai Benjamini and Elad Tzalik, Determining a points configuration on the line from a subset of the pairwise distances , 2022, arXiv:2208.13855

    work page internal anchor Pith review Pith/arXiv arXiv 2022

  8. [8]

    Gortler, Anthony Nixon, Meera Sitharam, and Louis Theran, Maximum likelihood thresholds via graph rigidity , The Annals of Applied Probability 34 (2024), no

    Daniel Irving Bernstein, Sean Dewar, Steven J. Gortler, Anthony Nixon, Meera Sitharam, and Louis Theran, Maximum likelihood thresholds via graph rigidity , The Annals of Applied Probability 34 (2024), no. 3, 3288–3319

    2024

  9. [9]

    73, Cambridge University Press, Cambridge, 2001

    B´ ela Bollob´ as,Random graphs, 2 ed., Cambridge Studies in Advanced Mathematics, vol. 73, Cambridge University Press, Cambridge, 2001

    2001

  10. [10]

    3, 332–352

    Charles Bordenave and Marc Lelarge, Resolvent of large random graphs , Random Structures & Algorithms 37 (2010), no. 3, 332–352

    2010

  11. [11]

    3, 1097–1121

    Charles Bordenave, Marc Lelarge, and Justin Salez, The rank of diluted random graphs , The Annals of Probability 39 (2011), no. 3, 1097–1121

    2011

  12. [12]

    J. A. Cain, P. Sanders, and N. C. Wormald, The random graph threshold for k-orientability and a fast algorithm for optimal multiple-choice allocation , Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2007, pp. 469–476

    2007

  13. [13]

    Katie Clinch, John Haslegrave, Tony Huynh, and Anthony Nixon, Sharp thresholds for NAC- colourings and stable cuts in random graphs , 2025, arXiv:2510.05838

    work page arXiv 2025

  14. [14]

    I , Publicationes Mathematicae Debrecen 6 (1959), 290–297

    Paul Erd˝ os and Alfr´ ed R´ enyi,On random graphs. I , Publicationes Mathematicae Debrecen 6 (1959), 290–297

    1959

  15. [15]

    , On the evolution of random graphs , Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17–61

    1960

  16. [16]

    Daniel Fernholz and Vijaya Ramachandran, The k-orientability thresholds for Gn,p, Proceed- ings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2007, pp. 459–468

    2007

  17. [17]

    32 YUV AL PELED

    Alan Frieze and Micha l Karo´ nski,Introduction to random graphs, Cambridge University Press, Cambridge, 2015. 32 YUV AL PELED

    2015

  18. [18]

    4, 2709–2720

    Ant´ onio Gir˜ ao, Freddie Illingworth, Lukas Michel, Emil Powierski, and Alex Scott, Recon- structing a point set from a random subset of its pairwise distances, SIAM Journal on Discrete Mathematics 38 (2024), no. 4, 2709–2720

    2024

  19. [19]

    2, American Mathematical Society, Providence, RI, 1993

    Jack Graver, Brigitte Servatius, and Herman Servatius, Combinatorial rigidity , Graduate Studies in Mathematics, vol. 2, American Mathematical Society, Providence, RI, 1993

    1993

  20. [20]

    1, 386–407

    Elizabeth Gross and Seth Sullivant, The maximum likelihood threshold of a graph , Bernoulli 24 (2018), no. 1, 386–407

    2018

  21. [21]

    2, 154–166

    Bill Jackson, Brigitte Servatius, and Herman Servatius, The 2-dimensional rigidity of certain families of graphs , Journal of Graph Theory 54 (2007), no. 2, 154–166

    2007

  22. [22]

    Luczak, A simple solution to the k-core problem, Random Structures & Algorithms 30 (2007), no

    Svante Janson and Malwina J. Luczak, A simple solution to the k-core problem, Random Structures & Algorithms 30 (2007), no. 1–2, 50–62

    2007

  23. [23]

    Svante Janson, Tomasz Luczak, and Andrzej Ruci´ nski,Random graphs, Wiley Series in Dis- crete Mathematics and Optimization, Wiley, New York, 2000

    2000

  24. [24]

    Tibor Jord´ an, Xuemei Liu, and Soma Vill´ anyi,Degree sum conditions for graph rigidity, 2025, arXiv:2510.25689

    work page arXiv 2025

  25. [25]

    3, 2367–2392

    Tibor Jord´ an and Shin-ichi Tanigawa,Rigidity of random subgraphs and eigenvalues of stiff- ness matrices, SIAM Journal on Discrete Mathematics 36 (2022), no. 3, 2367–2392

    2022

  26. [26]

    1237–1252

    Shiva Prasad Kasiviswanathan, Cristopher Moore, and Louis Theran, The rigidity transition in random graphs , Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2011, pp. 1237–1252

    2011

  27. [27]

    Coherence and sufficient sampling densities for reconstruction in compressed sensing

    Franz J. Kir´ aly and Louis Theran,Coherence and sufficient sampling densities for reconstruc- tion in compressed sensing , 2013, arXiv:1302.2767

    work page internal anchor Pith review Pith/arXiv arXiv 2013

  28. [28]

    Power, The rigidity of infinite graphs, Discrete & Computational Geometry 60 (2018), no

    Derek Kitson and Stephen C. Power, The rigidity of infinite graphs, Discrete & Computational Geometry 60 (2018), no. 3, 531–557

    2018

  29. [29]

    Michael Krivelevich, Alan Lew, and Peleg Michaeli, Rigid partitions: From high connectivity to random graphs, Journal of Combinatorial Theory, Series B 175 (2025), 126–170

    2025

  30. [30]

    , Combinatorial sufficient conditions for graph rigidity and applications to random graphs, 2026, arXiv:2602.23713

    work page arXiv 2026

  31. [31]

    1, e70279

    , Minimum degree conditions for graph rigidity , Bulletin of the London Mathematical Society 58 (2026), no. 1, e70279

    2026

  32. [32]

    4, 331–340

    Gerard Laman, On graphs and rigidity of plane skeletal structures , Journal of Engineering Mathematics 4 (1970), no. 4, 331–340

    1970

  33. [33]

    Raz, Sharp threshold for rigidity of random graphs, Bulletin of the London Mathematical Society 55 (2023), no

    Alan Lew, Eran Nevo, Yuval Peled, and Orit E. Raz, Sharp threshold for rigidity of random graphs, Bulletin of the London Mathematical Society 55 (2023), no. 1, 490–501

    2023

  34. [34]

    3, 745–773

    Nathan Linial and Yuval Peled, On the phase transition in random simplicial complexes , Annals of Mathematics 184 (2016), no. 3, 745–773

    2016

  35. [35]

    1, 61–68

    Tomasz Luczak, Size and connectivity of the k-core of a random graph, Discrete Mathematics 91 (1991), no. 1, 61–68

    1991

  36. [36]

    6, Springer, 2025, pp

    Richard Montgomery, Rajko Nenadov, and Tibor Szab´ o,Global rigidity of random graphs in R, 2023 MATRIX Annals, MATRIX Book Series, vol. 6, Springer, 2025, pp. 717–724

    2023

  37. [37]

    Owen and Stephen C

    John C. Owen and Stephen C. Power, Infinite bar-joint frameworks, crystals and operator theory, New York Journal of Mathematics 17 (2011), 445–490

    2011

  38. [38]

    Yuval Peled and Niv Peleg, On the rigidity of random graphs in high-dimensional spaces , 2024, arXiv:2412.13127

    work page arXiv 2024

  39. [39]

    1, 111–151

    Boris Pittel, Joel Spencer, and Nicholas Wormald, Sudden emergence of a giant k-core in a random graph, Journal of Combinatorial Theory, Series B 67 (1996), no. 1, 111–151

    1996

  40. [40]

    I: Functional analysis, revised and enlarged ed., Academic Press, New York, 1980

    Michael Reed and Barry Simon, Methods of modern mathematical physics. I: Functional analysis, revised and enlarged ed., Academic Press, New York, 1980

    1980

  41. [41]

    Louis Theran, Rigid components of random graphs , Proceedings of the 21st Canadian Con- ference on Computational Geometry, 2009, pp. 63–66

    2009

  42. [42]

    , Private communication, 2026, Private communication

    2026

  43. [43]

    1, 238–261

    Caroline Uhler, Geometry of maximum likelihood estimation in gaussian graphical models , The Annals of Statistics 40 (2012), no. 1, 238–261. Einstein Institute of Mathematics, The Hebrew University of Jerusalem, Jerusalem, Israel Email address: yuval.peled@mail.huji.ac.il

    2012