Skip to content
DraconiticResearch
Search Sources API
201,818 studies31 sourcesUpdated 8 min ago
PreprintarXiv licencearXiv

The number of realisations of a random graph

  • Sean Dewar
  • Anthony Nixon
  • Ben Smith
Open at sourcePDFDOICite

Abstract

Determining the number of realisations, up to isometries, of a graph for a specific choice of edge lengths is a fundamental problem in discrete geometry. In this article we prove that, asymptotically almost surely, the d-dimensional complex realisation number for each n-vertex graph in an Erdős-Rényi random graph process is either infinite or equal to 2n−t where t is the size of the (d+1)-core; moreover this number coincides exactly with the real realisation number for such graphs. We also determine a similar formula for the number of complex solutions to the generic rank-d positive semi-definite matrix completion problem with randomly selected non-diagonal unknown entries.

Related

  1. The chromatic number of a random graph with o(n3/2) edges
    Amin Coja-Oghlan, Mikhail Isaev, Mihyun Kang +1
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv
  2. Selecting the number of components in PCA via random signflips
    David Ke Hong, Yue Sheng, Edgar Dobriban
    Journal of the American Statistical AssociationPeer-reviewedLicence not statedFull text21 citedStatisticsOpenAlex
  3. Quasi-Fuchsian groups and complex realisations of q-deformed real numbers
    Alex Elzenaar
    arXivPreprintarXiv licenceFull textAlgebra & number theoryAnalysis & PDEsarXiv
  4. The domination number of the 2-token graph of the complete bipartite graph
    E. Acosta Troncoso, I. Caldera Caldera, L. M. Rivera
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Quadratic differentials and random walks on the dual graph of a pants decomposition
    Charles Bordenave, Xinlong Dong, Dragomir Šarić
    HALPreprintLicence not statedGeneral mathematicsHAL

Cite

BibTeXRIS
BibTeX
@misc{dewar2026number,
  title = {{The number of realisations of a random graph}},
  author = {Sean Dewar and Anthony Nixon and Ben Smith},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.18487},
  eprint = {2605.18487},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.18487},
}
RIS
TY  - UNPB
TI  - The number of realisations of a random graph
AU  - Sean Dewar
AU  - Anthony Nixon
AU  - Ben Smith
PY  - 2026
DA  - 2026/09/01
PB  - arXiv
DO  - 10.48550/arxiv.2605.18487
UR  - https://arxiv.org/abs/2605.18487
AB  - Determining the number of realisations, up to isometries, of a graph for a specific choice of edge lengths is a fundamental problem in discrete geometry. In this article we prove that, asymptotically almost surely, the d-dimensional complex realisation number for each n-vertex graph in an Erdős-Rényi random graph process is either infinite or equal to 2^n−t where t is the size of the (d+1)-core; moreover this number coincides exactly with the real realisation number for such graphs. We also determine a similar formula for the number of complex solutions to the generic rank-d positive semi-definite matrix completion problem with randomly selected non-diagonal unknown entries.
ER  -