Pith. sign in

REVIEW 2 major objections 5 minor 1 cited by

Minimum degree conditions for graph rigidity

T0 review · 2 major / 5 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 The paper proves that n-vertex graphs with minimum degree just above half the vertices are generically rigid in $\mathbb{R}^d$ for all $d$ up to about $n/\log^2 n$, with an exact threshold for $d$ up to about $\sqrt{n}$.

desk verdict Strong and honest progress on a known conjecture: tight small-d and near-tight large-d minimum-degree thresholds for rigidity, with the main vulnerability being its reliance on an imported lemma from Villányi's preprint. read the letter →

arxiv 2412.14364 v1 pith:JFT27E2E submitted 2024-12-18 math.CO

Michael Krivelevich , Alan Lew , Peleg Michaeli This is my paper · ORCID
classification math.CO MSC 52C2505C3505C40
keywords graphrigidityminimumdegreed-rigidrigidpartitionspseudoachromaticnumberregularitylemmad-closuregenericembeddings
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 establishes that a minimum degree just above half the vertex count makes a graph generically rigid in $\mathbb{R}^d$, for a wide range of $d$. For $d$ up to order $\sqrt{n}$, the threshold $\delta(G) \ge (n+d)/2 - 1$ is exactly what connectivity demands, and the paper proves it suffices for $d$-rigidity. For $d$ up to order $n/\log^2 n$, the slightly stronger threshold $\delta(G) \ge (n+2d)/2 - 1$ suffices, and this is tight up to a factor of two in the coefficient of $d$. A byproduct is a sharp lower bound on the pseudoachromatic number: every $n$-vertex graph with minimum degree at least $d$ has a partition of its vertices into $d+1$ parts with at least one edge between every pair of parts.

What carries the argument

The central object is the strong $d$-rigid partition: a partition of the vertex set into $d$ parts, each of size at least one, such that $G[V_i,V_j]$—the subgraph with all edges between $V_i$ and $V_j$—is connected for every $1 \le i \le j \le d$. The imported Theorem 2.3 says that any graph admitting such a partition is $d$-rigid, so the whole problem for large $d$ reduces to constructing these partitions. For small $d$, the paper uses the $d$-closure—the graph formed by adding every non-edge that does not increase the rigidity matrix rank—together with an imported lemma that any $d$-closed graph with minimum degree at least $d(d+1)$ contains a simplicial vertex; a short argument then forces the closure to be complete, which is equivalent to $d$-rigidity. For large $d$, the engine is the strong $d$-rigid partition, whose existence is obtained by two structural routes: random colourings with strong cross-connectivity in the near-bipartite case, and a Regularity-Lemma reduction to a super-regular tripartite graph in the far-from-bipartite case.

What would settle it

A concrete refutation would be a single $n$-vertex graph with $\delta(G) \ge (n+2d)/2 - 1$ for some $d \le cn/\log^2 n$ whose rigidity matrix at a generic embedding has rank below $dn - \binom{d+1}{2}$; such a graph would disprove Theorem 1.2. The analogous check with $\delta(G) \ge (n+d)/2 - 1$ and $d \le c\sqrt{n}$ would settle Theorem 1.1.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central claim is that the conjectural minimum-degree threshold for $d$-rigidity, $\max\{(n+d)/2 - 1,\ 2d - d(d+1)/n\}$, is correct for $d = O(\sqrt{n})$ (Theorem 1.1) and is correct up to a factor of two in the second term's coefficient for $d = O(n/\log^2 n)$ (Theorem 1.2). The proof works by showing that such graphs admit strong $d$-rigid partitions—partitions into $d$ parts such that every part and every pair of parts induces a connected cross-subgraph—when the graph is close to bipartite, and by showing $d$-rigidity directly for far-from-bipartite graphs via a regularity-lemma reduction to a super-regular tripartite subgraph. Since a strong $d$-rigid partition implies $d$-rigidity, the first case is immediate; the second uses a $0$-extension argument to grow a large $d$-rigid subgraph to the whole graph. The same random-colouring machinery yields the pseudoachromatic result (Theorem 1.3).

Load-bearing premise

The paper's main theorems rest on two imported black-box results—that a strong $d$-rigid partition implies $d$-rigidity, and that a $d$-closed graph with minimum degree at least $d(d+1)$ has a simplicial vertex—so if either imported theorem has a hidden restriction or gap, the corresponding minimum-degree result does not follow from the arguments given.

Editorial extensions

If this is right

  • Conjecture 1 is confirmed in the range $d = O(\sqrt{n})$, where the connectivity threshold $(n+d)/2 - 1$ is shown to be the exact minimum-degree threshold for $d$-rigidity.
  • For $d = O(n/\log^2 n)$, the threshold $(n+2d)/2 - 1$ guarantees $d$-rigidity, so the conjectured threshold is known within a factor of two in the coefficient of $d$.
  • Every $n$-vertex graph with minimum degree at least $d$ (for $d = O(n/\log^2 n)$) has a pseudocomplete colouring with $d+1$ colours, and this is best possible.
  • The proof's random-colouring construction (Lemma 4.3) yields, with high probability, a pseudocomplete colouring in which each of $d+1$ colour classes captures most vertices with probability at least $1/(2d)$, independently across vertices—a new structural tool.
  • The small-$d$ result extends the previously known rigidity range for this degree condition from $d = O(\sqrt{n}/\log n)$ to $d = O(\sqrt{n})$.

Reading between the lines

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

  • If the random-colouring lemma generalizes, the same method may give pseudocomplete colourings with $d+1$ colours for graphs of minimum degree $d$ in other sparse settings, such as random graphs with minimum degree constraints.
  • The factor-two gap in Theorem 1.2 is an invitation: the conjecture predicts the exact threshold, and the near-bipartite/far-bipartite split suggests the obstruction should be located in one of the two regimes rather than in a mixed regime.
  • The strong-rigid-partition reduction, combined with the regularity lemma, suggests that any graph containing a super-regular tripartite subgraph of linear size is $d$-rigid for $d$ up to order $n/\log n$; this could be a route to rigidity thresholds in dense random and quasirandom graphs.
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.

Referee Report

2 major / 5 minor

Summary. The paper studies minimum-degree sufficient conditions for generic rigidity in R^d. Theorem 1.1 gives a tight bound for small d: for d = O(sqrt n), every n-vertex graph with minimum degree at least (n+d)/2 - 1 is d-rigid. The proof passes through the d-closure of the graph and uses two lemmas of Vill\'anyi, one of which asserts that every d-closed graph with minimum degree at least d(d+1) has a simplicial vertex. Theorem 1.2 gives an approximate result for d = O(n/log^2 n): the same conclusion holds when the minimum degree is at least (n+2d)/2 - 1, which is tight up to a factor of two in the coefficient of d. The proof splits into a bipartite case (Proposition 4.1, via random pseudocomplete colourings and strong d-rigid partitions) and a non-bipartite case (Proposition 4.2, via the regularity lemma and super-regular triples). Theorem 1.3, a byproduct, states that every n-vertex graph with minimum degree at least d has pseudoachromatic number at least d+1 when d = O(n/log^2 n), and this is tight. The paper is clearly written and the internal proofs are carefully structured, but it relies on substantial unproved external results.

Significance. If the external lemmas are valid, this is a noteworthy advance on a natural conjecture about minimum degree and rigidity. Theorem 1.1 confirms the conjectured threshold in the range d = O(sqrt n), and Theorem 1.2 narrows the gap to within a factor of two in the linear-in-d term for a much wider range. Theorem 1.3 is a clean, tight byproduct. The paper's own contributions are strong: the probabilistic estimates in Lemmas 4.3 and 4.4 use explicit constants and correct Chernoff/Azuma bounds; the super-regular reduction in Lemma 4.8 and Corollary 4.15 is standard and correctly applied; Proposition 4.16's connectivity case analysis is complete; and Lemma 4.19's extension argument is elegant. The main caveat is that Theorem 1.1, one of the two headline results, rests entirely on Lemma 3.3, which is quoted from an unpublished preprint and not proved in the manuscript.

major comments (2)
  1. [3 (proof of Lemma 3.1)] Theorem 1.1 is conditional on Lemma 3.3, which is stated without proof and attributed to the unpublished preprint [25]. This lemma is load-bearing: the entire proof of Lemma 3.1, and hence of Theorem 1.1, collapses if Lemma 3.3 has a hidden restriction or an error. The manuscript does not reproduce or even sketch its proof. Please include a complete proof of Lemma 3.3, or replace the reference with a peer-reviewed version, so that the main small-d theorem is not contingent on an inaccessible black box.
  2. [4.1 (Lemma 4.3 and Proposition 4.1)] The first bullet of Lemma 4.3 guarantees P(v in V_i) >= 1/(2d) only for i in [d], omitting the (d+1)-st colour class, even though the proof of the lemma establishes the bound for all i in [d+1]. Proposition 4.1 applies Lemma 4.3 with parameter d-1 and then uses the probability bound for all d colour classes A_1,...,A_d, including the last one. As stated, the lemma does not formally cover that final class. Please restate the first bullet of Lemma 4.3 to cover all colour classes, or state the stronger consequence explicitly in Proposition 4.1.
minor comments (5)
  1. [4.1 (proof of Proposition 4.1)] The notation A' and B' is overloaded: first they denote the two sides of the bipartition, and later they are reused for the unions A_1 cup ... cup A_d and B_1 cup ... cup B_d of the random colour classes. This makes the proof hard to follow and should be fixed, for example by using X and Y for the two sides.
  2. [3 (proof of Lemma 3.1)] The sentence 'G[H1 union H2 union {v}] is not complete, and hence not d-rigid' is not true for arbitrary graphs and should explicitly invoke that G is d-closed. In a d-closed graph, an induced subgraph that contains a d-rigid spanning subgraph would force the whole induced subgraph to be complete, but this reasoning is currently suppressed.
  3. [4.2.2 (proof of Proposition 4.2)] The proof uses the implication 'D-rigid implies d-rigid for d <= D' in order to pass from a strong D-rigid partition of H to d-rigidity of H. This is a standard fact, but it is not stated in the preliminaries. A one-sentence reference or proof would make the argument self-contained.
  4. [Abstract and Section 1] The phrase 'tight up to a factor of two in the coefficient of d' is used for Theorem 1.2, but no construction is given showing that the coefficient 2 cannot be improved. Please clarify whether this means tight only against the conjectured optimal bound in Conjecture 1, or whether a matching lower-bound construction is known.
  5. [1 (Introduction)] There is a typo: 'p reserves the distance' should read 'preserves the distance'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: proofs reduce to external lemmas, not to their own conclusions.

full rationale

The paper's central theorems are proved from external black boxes, not from the target statements. Theorem 1.1 reduces to Villányi's Lemmas 3.2–3.3 ([25]), which are technical lemmas about d-closed graphs and permutations; they do not state the minimum-degree rigidity threshold. Theorem 1.2 is built on Lew–Nevo–Peled–Raz Theorem 2.3 (a sufficient condition connecting strong d-rigid partitions to rigidity) and on internally proved Propositions 4.1 and 4.16, plus Lemma 4.19 and the 0-extension Lemma 2.2. The strong d-rigid partition is constructed, not assumed, and the subsequent rigidity conclusion is an imported but independent theorem. The pseudoachromatic bound is derived from Lemma 4.3, which is proved from Chernoff/Azuma estimates. No parameter is fitted to the target conclusion, and no step uses the theorem being proved as an assumption. The only author-overlapping citation, [19], supplies a general sufficient condition with stated assumptions that do not include the minimum-degree condition under study; it is therefore independent support, not a circular premise. The main correctness risk is the unverified external Lemma 3.3, but that is a dependency, not circularity.

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

No empirical fitting; constants c, beta, and n0 are existential proof constants. The central claim rests on standard rigidity theorems, concentration inequalities, and the regularity method, all imported as black boxes. No new entities are postulated.

assumptions (6)
  • standard math Generic rigidity is a graph property (Asimow-Roth): for generic p, rigidity equals infinitesimal rigidity and depends only on G.
    Used at the start of the paper to define d-rigidity and to justify working with the rigidity matrix; imported from [1].
  • standard math The rigidity matrix rank satisfies rank R(G,p) <= d|V| - binom(d+1,2) for all frameworks.
    Section 1, used to define infinitesimal rigidity and to derive the necessary edge condition |E| >= dn - binom(d+1,2).
  • standard math Theorem 2.3: if G admits a strong d-rigid partition, then G is d-rigid.
    Imported from [19, Theorem 1.3]; the central bridge from graph connectivity to rigidity in Section 4.
  • standard math Villanyi's edge-count lemmas: for a d-closed graph, G_sigma has at most dn - binom(d+1,2) edges (Lemma 3.2), and under no-simplicial-vertex conditions some permutation gives at least dn edges (Lemma 3.3).
    Imported from [25]; the engine for Theorem 1.1 via Lemma 3.1.
  • standard math Chernoff and Azuma concentration inequalities (Theorem 2.4 and Lemma 2.5).
    Used in Lemma 4.4 and Lemma 4.3 for random colouring bounds; standard.
  • standard math Degree-form Szemeredi Regularity Lemma (Lemma 4.9) and Erdos-Simonovits stability theorem (Theorem 4.13).
    Used in Section 4.2 to locate a super-regular triple in far-from-bipartite graphs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Minimum degree conditions for graph rigidity." pith.science (2026). https://pith.science/paper/JFT27E2E

@misc{pith2026241214364,
  author       = {Pith},
  title        = {Pith review of: Minimum degree conditions for graph rigidity},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JFT27E2E}},
  note         = {Machine review of arXiv:2412.14364}
}
abstract

We study minimum degree conditions that guarantee that an $n$-vertex graph is rigid in $\mathbb{R}^d$. For small values of $d$, we obtain a tight bound: for $d = O(\sqrt{n})$, every $n$-vertex graph with minimum degree at least $(n+d)/2 - 1$ is rigid in $\mathbb{R}^d$. For larger values of $d$, we achieve an approximate result: for $d = O(n/{\log^2}{n})$, every $n$-vertex graph with minimum degree at least $(n+2d)/2 - 1$ is rigid in $\mathbb{R}^d$. This bound is tight up to a factor of two in the coefficient of $d$. As a byproduct of our proof, we also obtain the following result, which may be of independent interest: for $d = O(n/{\log^2}{n})$, every $n$-vertex graph with minimum degree at least $d$ has pseudoachromatic number at least $d+1$; namely, the vertex set of such a graph can be partitioned into $d+1$ subsets such that there is at least one edge between each pair of subsets. This is tight.

Figures

Figures reproduced from arXiv: 2412.14364 by the authors.

Figure 1
Figure 1. We define the rigidity of a graph G = (V, E) to be the maximal d for which G is d-rigid. In the above diagram, the x-axis shows the minimum degree, while the y-axis displays the rigidity of the graph. The red solid line represents the bound δ(G) ≥ 2d − d(d + 1)/n, determined by the necessary condition |E| ≥ dn − [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

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

25 extracted references · 23 canonical work pages · cited by 1 Pith paper

  1. [18]

    ↑2, 3, 5

    Michael Krivelevich, Alan Lew and Peleg Michaeli, Rigid partitions: from high connectivity to random graphs , arXiv e-prints (November 2023), available at arXiv:2311.14451. ↑2, 3, 5

    arXiv 2023

  2. [19]

    Rigidity expander graphs

    Alan Lew, Eran Nevo, Yuval Peled and Orit E. Raz, Rigidity expander graphs , arXiv e-prints (April 2023), available at arXiv:2304.01306. ↑3, 5

    work page Pith review arXiv 2023

  3. [25]

    Every $d(d+1)$-connected graph is globally rigid in $\mathbb{R}^d$

    Soma Vill´ anyi,Every d(d + 1)-connected graph is globally rigid in Rd, arXiv e-prints (December 2023), available at arXiv:2312.02028. ↑3, 6 18

    work page Pith review arXiv 2023

  4. [1]

    MR 511410 ↑1, 2

    Leonard Asimow and Ben Roth, The rigidity of graphs , Transactions of the American Mathematical Society 245 (1978), 279–289. MR 511410 ↑1, 2

    work page 1978

  5. [2]

    Catlin and Paul Erd˝ os,Hadwiger’s conjecture is true for almost every graph , European Journal of Combinatorics 1 (1980), no

    B´ ela Bollob´ as, Paul A. Catlin and Paul Erd˝ os,Hadwiger’s conjecture is true for almost every graph , European Journal of Combinatorics 1 (1980), no. 3, 195–199. MR 593989 ↑4

    work page 1980

  6. [3]

    103699, 9

    Maria Chudnovsky and Eran Nevo, Stable sets in flag spheres , European Journal of Combinatorics 110 (2023), Paper No. 103699, 9. MR 4549512 ↑2

    work page 2023

  7. [4]

    MR 205876 ↑13

    Paul Erd˝ os and Mikl´ os Simonovits,A limit theorem in graph theory , Studia Scientiarum Mathematicarum Hun- garica 1 (1966), 51–57. MR 205876 ↑13

    work page 1966

  8. [5]

    III, Birkh¨ auser, Basel, 2004, pp

    Alan Frieze and Boris Pittel, Perfect matchings in random graphs with prescribed minimal degree, Mathematics and computer science. III, Birkh¨ auser, Basel, 2004, pp. 95–132. MR 2090500 ↑5

    work page 2004

Show all 25 references
  1. [6]

    MR 3383250 ↑13

    Zolt´ an F¨ uredi,A proof of the stability of extremal graphs, Simonovits’ sta bility from Szemer´ edi’s regularity, Journal of Combinatorial Theory, Series B 115 (2015), 66–71. MR 3383250 ↑13

    2015

  2. [7]

    Conf., Park City, Utah, 1974), Springer, Berlin-New York, 1975, pp

    Herman Gluck, Almost all simply connected closed surfaces are rigid , Geometric topology (Proc. Conf., Park City, Utah, 1974), Springer, Berlin-New York, 1975, pp. 225 –239. MR 400239 ↑2

    1974

  3. [8]

    2, American Mathematical Society, Providence , RI, 1993

    Jack Graver, Brigitte Servatius and Herman Servatius, Combinatorial rigidity , Graduate Studies in Mathe- matics, vol. 2, American Mathematical Society, Providence , RI, 1993. MR 1251062 ↑2

    1993

  4. [9]

    Third Waterloo Conf

    Ram Prakash Gupta, Bounds on the chromatic and achromatic numbers of complemen tary graphs , Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Co mbinatorics, 1968), Academic Press, New York- London, 1969, pp. 229–235. MR 256930 ↑4

    1968

  5. [10]

    Halld´ orsson, Guy Kortsarz, Jaikumar Radhakrishnan and Sivaramakrishnan Sivasubramanian, Com- plete partitions of graphs , Combinatorica 27 (2007), no

    Magn´ us M. Halld´ orsson, Guy Kortsarz, Jaikumar Radhakrishnan and Sivaramakrishnan Sivasubramanian, Com- plete partitions of graphs , Combinatorica 27 (2007), no. 5, 519–550. MR 2375716 ↑4

    2007

  6. [11]

    John Haslegrave, Peleg Michaeli and Anthony Nixon, Rigidity of some special graphs (In preperation). ↑2

  7. [12]

    4, 1797–1819

    Bill Jackson, Tibor Jord´ an and Shin-ichi Tanigawa, Combinatorial conditions for the unique completability of low-rank matrices, SIAM Journal on Discrete Mathematics 28 (2014), no. 4, 1797–1819. MR 3268605 ↑2

    2014

  8. [13]

    MR 3548301 ↑2, 16

    Bill Jackson, Tibor Jord´ an and Shin-ichi Tanigawa, Unique low rank completability of partially filled matrices , Journal of Combinatorial Theory, Series B 121 (2016), 432–462. MR 3548301 ↑2, 16

    2016

  9. [14]

    MR 1782847 ↑5 17

    Svante Janson, Tomasz /suppress Luczak and Andrzej Rucinski,Random graphs , Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New Yo rk, 2000. MR 1782847 ↑5 17

    2000

  10. [15]

    Tibor Jord´ an,Combinatorial rigidity: graphs and matroids in the theory o f rigid frameworks , Discrete geometric analysis, Math. Soc. Japan, Tokyo, 2016, pp. 33–112. MR 3525848 ↑2

    2016

  11. [16]

    2 (Keszthely, 1993), J´ anos Bolyai Math

    J´ anos Koml´ os and Mikl´ os Simonovits,Szemer´ edi’s regularity lemma and its applications in graph theory, Combi- natorics, Paul Erd˝ os is eighty, Vol. 2 (Keszthely, 1993), J´ anos Bolyai Math. Soc., Budapest, 1996, pp. 295–352. MR1395865 ↑11, 12

    1993

  12. [17]

    Kostochka, The minimum Hadwiger number for graphs with a given mean degr ee of vertices, Metody Diskretnogo Analiza 38 (1982), 37–58

    Alexandr V. Kostochka, The minimum Hadwiger number for graphs with a given mean degr ee of vertices, Metody Diskretnogo Analiza 38 (1982), 37–58. MR 713722 ↑4

    1982

  13. [20]

    Raz, Sharp threshold for rigidity of random graphs , Bull

    Alan Lew, Eran Nevo, Yuval Peled and Orit E. Raz, Sharp threshold for rigidity of random graphs , Bull. Lond. Math. Soc. 55 (2023), no. 1, 490–501. MR 4568355 ↑4

    2023

  14. [21]

    Yuval Peled and Niv Peleg,On the rigidity of random graphs in high-dimensional spaces , arXiv e-prints (December 2024), available at arXiv:2412.13127. ↑6

    2024 arXiv

  15. [22]

    Bernd Schulze and Walter Whiteley, Rigidity and scene analysis , Handbook of discrete and computational geometry (3rd edition), CRC Press, 2018, pp. 893–916. ↑2

    2018

  16. [23]

    Dual French-English text

    Tiong-Seng Tay and Walter Whiteley, Generating isostatic frameworks , Structural Topology 11 (1985), 21–69. Dual French-English text. MR 804977 ↑5

    1985

  17. [24]

    2, 318–338

    Andrew Thomason, The extremal function for complete minors , Journal of Combinatorial Theory, Series B 81 (2001), no. 2, 318–338. MR 1814910 ↑4

    2001

Pith tools

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