Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 29 min ago
PreprintarXiv licencearXiv

Rigidity of complements of bounded-degree graphs

  • John Haslegrave
  • Peleg Michaeli
  • Anthony Nixon
Open at sourcePDFDOICite

Abstract

Maxwell observed that the graph of any rigid generic framework in ℝd on n vertices has at least dn−binomd+12 edges. In this article we prove that graphs whose complement has maximum degree at most two and no component isomorphic to a triangle or a square are rigid in the maximum dimension allowed by this observation. In particular, this determines the precise maximum dimension in which the graph obtained from a complete graph K2m by deleting a perfect matching is rigid, resolving a recent conjecture of Lew. We also deduce bounds on the rigidity of complements of bounded-degree graphs more generally, which significantly improve existing degree-based bounds.

Related

  1. Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs
    Lior Gishboliner, Xiangyu Li
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  2. A note on the injective edge coloring of graphs with bounded maximum degree
    Lin Tian, Runze Wang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The weak cylinder conjecture for polynomial graphs of bounded degree
    Daniele Bartoli, Alessandro Giannoni
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  4. Spatial Mixing and Deterministic Approximate Counting of Multi-spin Systems beyond Bounded Degree Graphs
    Zhidan Li, Kuan Yang
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  5. Sharp lower bounds for bisections of graphs with bounded maximum degree
    Qiwen Guo, Gregory Gutin
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{haslegrave2026rigidity,
  title = {{Rigidity of complements of bounded-degree graphs}},
  author = {John Haslegrave and Peleg Michaeli and Anthony Nixon},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.05058},
  eprint = {2609.05058},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.05058},
}
RIS
TY  - UNPB
TI  - Rigidity of complements of bounded-degree graphs
AU  - John Haslegrave
AU  - Peleg Michaeli
AU  - Anthony Nixon
PY  - 2026
DA  - 2026/09/04
PB  - arXiv
DO  - 10.48550/arxiv.2609.05058
UR  - https://arxiv.org/abs/2609.05058
AB  - Maxwell observed that the graph of any rigid generic framework in ℝ^d on n vertices has at least dn−binomd+12 edges. In this article we prove that graphs whose complement has maximum degree at most two and no component isomorphic to a triangle or a square are rigid in the maximum dimension allowed by this observation. In particular, this determines the precise maximum dimension in which the graph obtained from a complete graph K_2m by deleting a perfect matching is rigid, resolving a recent conjecture of Lew. We also deduce bounds on the rigidity of complements of bounded-degree graphs more generally, which significantly improve existing degree-based bounds.
ER  -