On the Rigidity of Random Graphs in high-dimensional spaces

Niv Peleg; Yuval Peled

REVIEW 2 major objections 3 minor 2 cited by

On the Rigidity of Random Graphs in high-dimensional spaces

T0 review · 2 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2412.13127 v1 pith:V4GQ4AUY submitted 2024-12-17 math.CO

Yuval Peled , Niv Peleg This is my paper · ORCID

classification math.CO MSC 05C8052C2505B35

keywords randomgraphsgenericrigiditymatroidminimumdegreeErdős–Rényiglobalthresholdhigh-dimensional

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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

What would settle it

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

Watch

Extended reading notes

Core claim

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

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

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

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

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

Referee Report

2 major / 3 minor

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.

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 (2)

[Section 2.1.1, Lemma 2.2] 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 4, open problem (1)] 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.

minor comments (3)

[Section 3.1, Lemma 3.4] 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.
[Throughout] 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 2.1.1, Lemma 2.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the main theorems are proved from in-paper lemmas and standard random-graph estimates; the principal gap is reliance on an external unpublished lemma, which is a completeness risk, not a circular reduction.

full rationale

The derivation chain is not circular. The thresholds in Theorems 1 and 2 are obtained from standard Chernoff and second-moment estimates on the minimum degree (Claim 2.7) and from the rank bound on d-rigid graphs; no parameter is fitted to the target quantity and then renamed a prediction. The large-clique machinery (Lemmas 3.1, 3.2, 3.4, Claims 2.5, 2.8, Fact 2.3) is proved in the paper, and the final bootstrap is a deterministic argument once the probabilistic events hold. The self-citation to [19] is not load-bearing: Theorem 1.1 is background, and Lemma 3.1, described as an extension of [19, Lemma 3.1], is proved in full here. The one flagged limitation is in Section 2.1.1, Lemma 2.2, whose proof invokes Lemmas 3.1 and 3.2 of Villányi's unpublished preprint [22] and states that the lemma is 'not explicitly stated in the paper in the exact form we require.' That is a real completeness and verification gap for the main theorems, but it is reliance on an external falsifiable source, not an equivalence of the results with their inputs by construction. Hence the circularity score is 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The proof relies on standard theorems (Asimow-Roth, Chernoff) and on two external results: the fixed-dimension threshold of [19] (used for context) and, critically, Villanyi's lemmas from [22] that underpin Lemma 2.2. No free parameters are fitted; the constant C* is solved from φ_C*(C*/2)=0. No new entities are introduced.

assumptions (5)

domain assumption Asimow-Roth theorem: a graph is d-rigid iff its generic rigidity matrix has rank d|V| - C(d+1,2).
Invoked in Section 2.1 to define d-rigid and the rigidity matroid.
domain assumption Villanyi's Lemmas 3.1 and 3.2 from arXiv:2312.02028, used to prove Lemma 2.2.
The authors note the lemma is not explicitly stated in [22] in the form required; the proof of Lemma 2.2 depends on it.
domain assumption Jordan's theorem: every (d+1)-rigid graph is globally d-rigid, used only for the global-rigidity corollaries (Theorems 1.2 and 1.3).
Cited in Section 1.1 to derive the global rigidity results from the main theorems.
domain assumption Sharp threshold for fixed d-rigidity, Theorem 1.1 of [19], used as background and to frame the conjecture.
Mentioned in the introduction; the paper's new results extend this to diverging dimensions.
standard math Chernoff bounds as stated in Fact 2.6.
Used throughout the probabilistic estimates.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On the Rigidity of Random Graphs in high-dimensional spaces." pith.science (2026). https://pith.science/paper/V4GQ4AUY

@misc{pith2026241213127,
  author       = {Pith},
  title        = {Pith review of: On the Rigidity of Random Graphs in high-dimensional spaces},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V4GQ4AUY}},
  note         = {Machine review of arXiv:2412.13127}
}

abstract

We study the maximum dimension $d=d(n,p)$ for which an Erd\H{o}s-R\'enyi $G(n,p)$ random graph is $d$-rigid. Our main results reveal two different regimes of rigidity in $G(n,p)$ separated at $p_c=C_*\log n/n,~C_*=2/(1-\log 2)$ -- the point where the graph's minimum degree exceeds half its average degree. We show that if $p < (1-\varepsilon)p_c $, then $d(n,p)$ is asymptotically almost surely (a.a.s.) equal to the minimum degree of $G(n,p)$. In contrast, if $p_c \leq p = o(n^{-1/2}) $ then $d(n,p) $ is a.a.s. equal to $(1/2 + o(1))np$. The second result confirms, in this regime, a conjecture of Krivelevich, Lew, and Michaeli.

Figures

Figures reproduced from arXiv: 2412.13127 by the authors.

**Figure 1.** Rigidity of G(n, p) where p = c log n/n. The shaded area illustrates the values of (c, d) for which G(n, p) is a.a.s. d-rigid (note that the Y -axis is normalized by log n). If c < C∗ the minimum-degree is the bottleneck for rigidity and otherwise the edge number is the bottleneck. The flexibility statements in both our theorems are immediate and follow directly from a dimension counting argument. The proofs of the … view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Minimum degree conditions for graph rigidity
math.CO 2024-12 accept novelty 7.0 of 10

The paper proves that minimum degree (n+d)/2 - 1 forces d-rigidity for d=O(sqrt n), and (n+2d)/2 - 1 forces d-rigidity for d=O(n/log^2 n), plus a matching pseudoachromatic-number bound.
Explosive connectivity and mechanical rigidity in cubic lattice structures
cond-mat.stat-mech 2025-11 reject novelty 5.0 of 10

For 3D cubic lattices, the paper claims first-order finite-size signatures of explosive percolation for k≥2 and monotone rigidification efficiency with k, but the proof of the central theorem is arithmetically impossi...

Reference graph

Works this paper leans on

22 extracted references · 17 canonical work pages · cited by 2 Pith papers

[22]

Vill´ anyi

S. Vill´ anyi. Every d(d + 1)-connected graph is globally rigid in Rd. arXiv preprint , arXiv:2312.02028, 2023. Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel. Email address : yuval.peled@mail.huji.ac.il Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel. Email address : niv.peleg@mail.huji.ac.il

arXiv 2023
[1]

Asimow and B

L. Asimow and B. Roth. The rigidity of graphs. Transactions of the American Mathematical Society, 245:279–289, 1978

work page 1978
[2]

Asimow and B

L. Asimow and B. Roth. The rigidity of graphs. II. Journal of Mathematical Analysis and Applications, 68(1):171–190, 1979

work page 1979
[3]

Benjamini and E

I. Benjamini and E. Tzalik. Determining a points configuration on the line from a subset of the pairwise distances. arXiv preprint arXiv:2208.13855 , 2022

arXiv 2022
[4]

Bollob´ as and B

B. Bollob´ as and B. Bollob´ as.Random graphs. Springer, 1998

work page 1998
[5]

Connelly and S

R. Connelly and S. D. Guest. Frameworks, tensegrities, and symmetry. Cambridge University Press, Cambridge, 2022

work page 2022
[6]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi. On random graphs. I.Publ. Math. Debrecen, 6:290–297, 1959

work page 1959
[7]

Frieze and M

A. Frieze and M. Karo´ nski. Introduction to random graphs . Cambridge University Press, 2015

work page 2015

Show all 22 references

[8]

Gir˜ ao, F

A. Gir˜ ao, F. Illingworth, L. Michel, E. Powierski, and A. Scott. Reconstructing a point set from a random subset of its pairwise distances. SIAM Journal on Discrete Mathematics , 38(4):2709–2720, 2024

2024
[9]

Graver, B

J. Graver, B. Servatius, and H. Servatius. Combinatorial rigidity , volume 2 of Graduate Studies in Mathematics . American Mathematical Society, Providence, RI, 1993

1993
[10]

Hendrickson

B. Hendrickson. Conditions for unique graph realizations. SIAM journal on computing , 21(1):65–84, 1992

1992
[11]

Jackson, B

B. Jackson, B. Servatius, and H. Servatius. The 2-dimensional rigidity of certain families of graphs. J. Graph Theory , 54(2):154–166, 2007

2007
[12]

Jord´ an

T. Jord´ an. Combinatorial rigidity: graphs and matroids in the theory of rigid frameworks. In Discrete geometric analysis , volume 34 of MSJ Mem. , pages 33–112. Math. Soc. Japan, Tokyo, 2016

2016
[13]

Jord´ an

T. Jord´ an. Extremal problems and results in combinatorial rigidity. In Proc. Hungarian Japanese Symposium on Discrete Mathematics and Its Applications , pages 297–304, 2017

2017
[14]

Jord´ an and S

T. Jord´ an and S. Tanigawa. Rigidity of random subgraphs and eigenvalues of stiffness matri- ces. Egerv´ ary Research Group, www.cs.elte.hu/egres, TR-2020-08, 2020

2020
[15]

Jord´ an and W

T. Jord´ an and W. Whiteley. Global rigidity. In Handbook of Discrete and Computational Geometry, pages 1661–1694. Chapman and Hall/CRC, 2017

2017
[16]

F. J. Kir´ aly and L. Theran. Coherence and sufficient sampling densities for reconstruction in compressed sensing. arXiv:1302.2767, 2013

2013 arXiv
[17]

Krivelevich, A

M. Krivelevich, A. Lew, and P. Michaeli. Rigid partitions: from high connectivity to random graphs. arXiv preprint arXiv:2311.14451 , 2023

2023 arXiv
[18]

G. Laman. On graphs and rigidity of plane skeletal structures. Journal of Engineering Math- ematics, 4:331–340, 1970

1970
[19]

A. Lew, E. Nevo, Y. Peled, and O. E. Raz. Sharp threshold for rigidity of random graphs. Bulletin of the London Mathematical Society , 55(1):490–501, 2023

2023
[20]

Montgomery, R

R. Montgomery, R. Nenadov, and T. Szab´ o. Global rigidity of random graphs in R. arXiv preprint arXiv:2401.10803, 2024

2024 arXiv
[21]

Tanigawa

S. Tanigawa. Sufficient conditions for the global rigidity of graphs. Journal of Combinatorial Theory, Series B , 113:123–140, 2015

2015

Pith tools

Reviewed August 11, 2026 · model on record in the stance chip above.

[1] [22]

Vill´ anyi

S. Vill´ anyi. Every d(d + 1)-connected graph is globally rigid in Rd. arXiv preprint , arXiv:2312.02028, 2023. Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel. Email address : yuval.peled@mail.huji.ac.il Einstein Institute of Mathematics, Hebrew University, Jerusalem 91904, Israel. Email address : niv.peleg@mail.huji.ac.il

arXiv 2023

[2] [1]

Asimow and B

L. Asimow and B. Roth. The rigidity of graphs. Transactions of the American Mathematical Society, 245:279–289, 1978

work page 1978

[3] [2]

Asimow and B

L. Asimow and B. Roth. The rigidity of graphs. II. Journal of Mathematical Analysis and Applications, 68(1):171–190, 1979

work page 1979

[4] [3]

Benjamini and E

I. Benjamini and E. Tzalik. Determining a points configuration on the line from a subset of the pairwise distances. arXiv preprint arXiv:2208.13855 , 2022

arXiv 2022

[5] [4]

Bollob´ as and B

B. Bollob´ as and B. Bollob´ as.Random graphs. Springer, 1998

work page 1998

[6] [5]

Connelly and S

R. Connelly and S. D. Guest. Frameworks, tensegrities, and symmetry. Cambridge University Press, Cambridge, 2022

work page 2022

[7] [6]

Erd˝ os and A

P. Erd˝ os and A. R´ enyi. On random graphs. I.Publ. Math. Debrecen, 6:290–297, 1959

work page 1959

[8] [7]

Frieze and M

A. Frieze and M. Karo´ nski. Introduction to random graphs . Cambridge University Press, 2015

work page 2015