pith. sign in

arxiv: 2605.18487 · v1 · pith:UNPHYMOOnew · submitted 2026-05-18 · 🧮 math.CO

The number of realisations of a random graph

Sean Dewar , Anthony Nixon , Ben Smith This is my paper

Pith reviewed 2026-05-20 09:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords realization numberErdős-Rényi random graphdiscrete geometryrigiditymatrix completionpolynomial-time algorithm
0
0 comments X

The pith

For an Erdős-Rényi random graph the d-dimensional realization number is either infinite or exactly a power of two whose exponent is computable in polynomial time.

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

This paper proves that when edge lengths are generic the number of realizations of an Erdős-Rényi random graph in d-dimensional space is either infinite or precisely a power of two. The exponent of that power can be found by a polynomial-time algorithm. A sympathetic reader would care because counting realizations is a fundamental task in discrete geometry that is otherwise computationally hard, and the result describes the typical case for random graphs. The same style of formula is given for the number of complex solutions to a related generic rank-d positive semidefinite matrix completion problem.

Core claim

The d-dimensional realisation number of an Erdős-Rényi random graph is either infinity or a power of 2 with exponent computable in polynomial time. We also determine a similar formula for the number of complex solutions to the generic rank-d PSD matrix completion problem with randomly-selected non-diagonal unknown entries.

What carries the argument

The d-dimensional realisation number, which counts the distinct embeddings of the graph vertices into Euclidean d-space that satisfy the given generic edge lengths.

If this is right

  • For typical random graphs the realization counting problem reduces to a fast combinatorial calculation of an exponent.
  • The infinite-versus-finite dichotomy occurs with high probability under the Erdős-Rényi model.
  • An analogous counting formula holds for complex solutions of the generic rank-d PSD matrix completion problem with random unknowns.

Where Pith is reading between the lines

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

  • In applications such as molecular modeling one could predict the number of distinct conformations without solving the full system of distance equations.
  • The result may extend to other random graph models used in rigidity and localization problems.
  • It suggests that algebraic degrees arising in generic realizations are typically powers of two for large random instances.

Load-bearing premise

The edge lengths are generic and the graph is an Erdős-Rényi random graph with parameters that make the dichotomy hold with high probability.

What would settle it

An explicit Erdős-Rényi graph with generic lengths whose finite realization count is not a power of two, or whose exponent requires superpolynomial time to compute.

Figures

Figures reproduced from arXiv: 2605.18487 by Anthony Nixon, Ben Smith, Sean Dewar.

Figure 1
Figure 1. Figure 1: Two different choices of edge lengths for the same graph. The left choice gives [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A schematic of a 3-dimensional 0-extension. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: A graph with a 3-connected 3-core (highlighted in blue) which does not have a 3-connected [PITH_FULL_IMAGE:figures/full_fig_p016_3.png] view at source ↗
read the original abstract

Determining the number of realisations of a graph for a specific choice of edge lengths is a fundamental problem in discrete geometry. In this article we prove that the $d$-dimensional realisation number of an Erd\H{o}s-Renyi random graph is either infinity or a power of 2 with exponent computable in polynomial time. We also determine a similar formula for the number of complex solutions to the generic rank-$d$ PSD matrix completion problem with randomly-selected non-diagonal unknown entries.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper proves that the d-dimensional realization number of an Erdős-Rényi random graph G(n,p) with generic edge lengths is either infinite or exactly 2^k for a combinatorially defined k that can be computed in polynomial time. A parallel result is established for the number of complex solutions to the generic rank-d PSD matrix completion problem when non-diagonal entries are chosen randomly.

Significance. If the central claims hold, the work delivers a clean dichotomy for realization counts under the random-graph model, showing that the algebraic degree reduces to a 2-group via quadratic extensions tracked by a recursive decomposition. The polynomial-time computability of the exponent is a notable algorithmic contribution that distinguishes the result from purely existential statements in rigidity theory. The argument relies on standard generic rigidity thresholds and random-graph tools, which are applied in good faith without ad-hoc parameters.

minor comments (3)
  1. §1: The introduction would benefit from an explicit statement of the probability threshold on p (e.g., the range where the dichotomy holds with high probability) to make the random-graph hypothesis fully precise at the outset.
  2. §4.2, Algorithm 1: The pseudocode for computing the exponent k is clear, but the running-time analysis claims O(n^3) without detailing the data structures used for the recursive decomposition; a short complexity paragraph would strengthen the polynomial-time claim.
  3. Theorem 5.3: The statement for the PSD matrix completion problem uses 'randomly-selected' without specifying the distribution on the unknown entries; aligning the wording with the Erdős-Rényi model used earlier would improve consistency.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work and for recommending minor revision. The summary accurately captures the main results on the d-dimensional realization number for Erdős-Rényi graphs and the analogous count for generic rank-d PSD matrix completion.

Circularity Check

0 steps flagged

No significant circularity; derivation uses independent standard tools

full rationale

The paper establishes that for generic edge lengths, an Erdős-Rényi graph is either not d-rigid (infinitely many realizations) or d-rigid with exactly 2^k realizations where k is combinatorially defined and polynomial-time computable. This follows from standard generic rigidity thresholds in combinatorial rigidity theory together with a recursive decomposition that tracks quadratic field extensions in the algebraic degree of the realization variety. No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation whose content is unverified outside the paper; the cited rigidity results are external and the random-graph model supplies the probabilistic dichotomy without circular renaming or ansatz smuggling. The result is therefore self-contained against external benchmarks in rigidity theory.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The proof relies on the standard Erdős-Rényi model and generic length assumptions common to rigidity theory; no free parameters or new entities are introduced.

axioms (2)
  • domain assumption Edge lengths are generic (in general position).
    Required for the realization count to avoid degeneracies that would alter the number.
  • domain assumption The graph is drawn from the Erdős-Rényi model with suitable edge probability.
    The dichotomy is stated specifically for random graphs under this distribution.

pith-pipeline@v0.9.0 · 5595 in / 1233 out tokens · 34751 ms · 2026-05-20T09:07:24.677224+00:00 · methodology

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

29 extracted references · 29 canonical work pages

  1. [1]

    Asimow and B

    Leonard Asimow and Ben Roth. The rigidity of graphs.Transactions of the American Mathematical Society, 245:279–289, 1978.doi:10.2307/1998867

    work page doi:10.2307/1998867 1978

  2. [2]

    Emiris, Jan Legerský, and Elias Tsigaridas

    Evangelos Bartzos, Ioannis Z. Emiris, Jan Legerský, and Elias Tsigaridas. On the maximal number of real embeddings of minimally rigid graphs inR2,R 3 andS 2.Journal of Symbolic Computation, 102:189–208, 2021.doi:10.1016/j.jsc.2019.10.015

    work page doi:10.1016/j.jsc.2019.10.015 2021

  3. [3]

    Emiris, and Raimundas Vidunas

    Evangelos Bartzos, Ioannis Z. Emiris, and Raimundas Vidunas. New upper bounds for the number of embeddings of minimally rigid graphs.Discrete & Computational Geometry, 68(3):796–816, 2022. doi:10.1007/s00454-022-00370-3

    work page doi:10.1007/s00454-022-00370-3 2022

  4. [4]

    Active Positive Semidefinite Matrix Comple- tion: Algorithms, Theory and Applications

    Aniruddha Bhargava, Ravi Ganti, and Rob Nowak. Active Positive Semidefinite Matrix Comple- tion: Algorithms, Theory and Applications. In Aarti Singh and Jerry Zhu, editors,Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, volume 54 ofPro- ceedings of Machine Learning Research, pages 1349–1357. PMLR, 20–22 Apr 2017...

    work page 2017

  5. [5]

    Bishop and Byron M

    William E. Bishop and Byron M. Yu. Deterministic symmetric positive semidefinite ma- trix completion. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Wein- berger, editors,Advances in Neural Information Processing Systems, volume 27. Curran As- sociates, Inc., 2014. URL:https://proceedings.neurips.cc/paper_files/paper/2014/file/ a1abaccc942...

    work page 2014

  6. [6]

    Random graphs of small order

    Béla Bollobás and Andrew Thomason. Random graphs of small order. In Michał Karoński and Andrzej Ruciński, editors,Random Graphs ’83, volume 118 ofNorth-Holland Mathematics Studies, pages 47–97. North-Holland, 1985. URL:https://www.sciencedirect.com/science/article/pii/ S0304020808736120,doi:10.1016/S0304-0208(08)73612-0

    work page doi:10.1016/s0304-0208(08)73612-0 1985

  7. [7]

    The number of embeddings of minimally rigid graphs.Discrete & Computational Geometry, 31(2):287–303, 2004.doi:10.1007/s00454-003-2902-0

    Ciprian Borcea and Ileana Streinu. The number of embeddings of minimally rigid graphs.Discrete & Computational Geometry, 31(2):287–303, 2004.doi:10.1007/s00454-003-2902-0

    work page doi:10.1007/s00454-003-2902-0 2004

  8. [8]

    The number of realizations of a Laman graph.SIAM Journal on Applied Algebra and Geometry, 2(1):94– 125, 2018.doi:10.1137/17M1118312

    Jose Capco, Matteo Gallet, Georg Grasegger, Christoph Koutschan, Niels Lubbes, and Josef Schicho. The number of realizations of a Laman graph.SIAM Journal on Applied Algebra and Geometry, 2(1):94– 125, 2018.doi:10.1137/17M1118312

    work page doi:10.1137/17m1118312 2018

  9. [9]

    The number of realisations of a rigid graph in Euclidean and spherical geometries.Algebraic Combinatorics, 7(6):1615–1645, 2024.doi:10.5802/alco.390

    Sean Dewar and Georg Grasegger. The number of realisations of a rigid graph in Euclidean and spherical geometries.Algebraic Combinatorics, 7(6):1615–1645, 2024.doi:10.5802/alco.390. 14

    work page doi:10.5802/alco.390 2024

  10. [10]

    Computing the number of realisations of a rigid graph, 2025.arXiv:2510.02988

    Sean Dewar, Georg Grasegger, Josef Schicho, Ayush Kumar Tewari, and Audie Warren. Computing the number of realisations of a rigid graph, 2025.arXiv:2510.02988

    work page arXiv 2025

  11. [11]

    Thed-dimensional realisation number of a rigid graph, 2026.arXiv:2602.20766

    Sean Dewar, Anthony Nixon, and Ben Smith. Thed-dimensional realisation number of a rigid graph, 2026.arXiv:2602.20766

    work page arXiv 2026

  12. [12]

    Publicationes Mathematicae Debrecen , author =

    Paul Erdős and Alfréd Rényi. On random graphs. I.Publicationes Mathematicae Debrecen, 6:290–297, 1959.doi:10.5486/pmd.1959.6.3-4.12

    work page doi:10.5486/pmd.1959.6.3-4.12 1959

  13. [13]

    Cambridge University Press, 2015

    Alan Frieze and Michał Karoński.Introduction to Random Graphs. Cambridge University Press, 2015

    work page 2015

  14. [14]

    Gortler, Alexander D Healy, and Dylan P Thurston

    Steven J. Gortler, Alexander D Healy, and Dylan P Thurston. Characterizing generic global rigidity. American Journal of Mathematics, 132(4):897–939, 2010.doi:10.1353/ajm.0.0132

    work page doi:10.1353/ajm.0.0132 2010

  15. [15]

    Gortler and Dylan P

    Steven J. Gortler and Dylan P. Thurston. Generic global rigidity in complex and pseudo-Euclidean spaces. In Robert Connelly, Asia Ivić Weiss, and Walter Whiteley, editors,Rigidity and Symmetry, pages 131–154. Springer, New York, 2014.doi:10.1007/978-1-4939-0781-6_8

    work page doi:10.1007/978-1-4939-0781-6_8 2014

  16. [16]

    American Mathematical Society, Providence, RI, 1993.doi:10.1090/gsm/002

    Jack Graver, Brigitte Servatius, and Herman Servatius.Combinatorial rigidity. American Mathematical Society, Providence, RI, 1993.doi:10.1090/gsm/002

    work page doi:10.1090/gsm/002 1993

  17. [17]

    Conditionsforuniquegraphrealizations.SIAM Journal on Computing, 21(1):65–84, 1992.doi:10.1137/0221008

    BruceHendrickson. Conditionsforuniquegraphrealizations.SIAM Journal on Computing, 21(1):65–84, 1992.doi:10.1137/0221008

    work page doi:10.1137/0221008 1992

  18. [18]

    John Hewetson, Bill Jackson, Anthony Nixon, and Ben Smith.k-fold circuits and coning in rigidity matroids, 2025.arXiv:2508.18838

    work page arXiv 2025

  19. [19]

    Bill Jackson and John C. Owen. Equivalent realisations of a rigid graph.Discrete Applied Mathematics, 256:42–58, 2019. Distance Geometry Theory and Applications (DGTA 16).doi:10.1016/j.dam.2017. 12.009

    work page doi:10.1016/j.dam.2017 2019

  20. [20]

    Wiley-Interscience Series in Discrete Mathematics and Optimization

    Svante Janson, Tomasz Łuczak, and Andrzej Ruciński.Random graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, 2000

    work page 2000

  21. [21]

    Globally linked pairs of vertices in generic frameworks.Combinatorica, 44(4):817–838, 2024.doi:10.1007/s00493-024-00094-3

    Tibor Jordán and Soma Villányi. Globally linked pairs of vertices in generic frameworks.Combinatorica, 44(4):817–838, 2024.doi:10.1007/s00493-024-00094-3

    work page doi:10.1007/s00493-024-00094-3 2024

  22. [22]

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

    work page doi:10.1112/blms.12740 2023

  23. [23]

    Size and connectivity of the k-core of a random graph.Discrete Mathematics, 91(1):61– 68, 1991.doi:10.1016/0012-365X(91)90162-U

    Tomasz Łuczak. Size and connectivity of the k-core of a random graph.Discrete Mathematics, 91(1):61– 68, 1991.doi:10.1016/0012-365X(91)90162-U

    work page doi:10.1016/0012-365x(91)90162-u 1991

  24. [24]

    Uniqueness of low-rank matrix completion by rigidity theory.SIAM Journal on Matrix Analysis and Applications, 31(4):1621–1641, 2010.doi:10.1137/090750688

    Amit Singer and Mihai Cucuringu. Uniqueness of low-rank matrix completion by rigidity theory.SIAM Journal on Matrix Analysis and Applications, 31(4):1621–1641, 2010.doi:10.1137/090750688

    work page doi:10.1137/090750688 2010

  25. [25]

    Mixed volume techniques for embeddings of Laman graphs

    Reinhard Steffens and Thorsten Theobald. Mixed volume techniques for embeddings of Laman graphs. Computational Geometry, 43(2):84–93, 2010. Special Issue on the 24th European Workshop on Com- putational Geometry (EuroCG’08).doi:10.1016/j.comgeo.2009.04.004

    work page doi:10.1016/j.comgeo.2009.04.004 2010

  26. [26]

    Sufficient conditions for the global rigidity of graphs.Journal of Combinatorial Theory, Series B, 113:123–140, 2015.doi:10.1016/j.jctb.2015.01.003

    Shin-ichi Tanigawa. Sufficient conditions for the global rigidity of graphs.Journal of Combinatorial Theory, Series B, 113:123–140, 2015.doi:10.1016/j.jctb.2015.01.003

    work page doi:10.1016/j.jctb.2015.01.003 2015

  27. [27]

    Everyd(d+ 1)−connected graph is globally rigid inR d.Journal of Combinatorial Theory, Series B, 173:1–13, 2025.doi:10.1016/j.jctb.2025.01.005

    Soma Villányi. Everyd(d+ 1)−connected graph is globally rigid inR d.Journal of Combinatorial Theory, Series B, 173:1–13, 2025.doi:10.1016/j.jctb.2025.01.005

    work page doi:10.1016/j.jctb.2025.01.005 2025

  28. [28]

    Cones, infinity and 1-story buildings.Structural Topology, 8:53–70, 1983

    Walter Whiteley. Cones, infinity and 1-story buildings.Structural Topology, 8:53–70, 1983

    work page 1983

  29. [29]

    Gcontains ak-connectedk- core containing at least5n/9vertices

    John Wishart. The generalised product moment distribution in samples from a normal multivariate population.Biometrika, 20A(1-2):32–52, 1928.doi:10.1093/biomet/20A.1-2.32. 15 Figure 3: A graph with a 3-connected 3-core (highlighted in blue) which does not have a 3-connected 3-core when the final edge (dashed) is added. A Proof of Theorem 3.6 To prove Theor...

    work page doi:10.1093/biomet/20a.1-2.32 1928