Combinatorial sufficient conditions for graph rigidity and applications to random graphs

Michael Krivelevich, Alan Lew, Peleg Michaeli · 2026

Read Combinatorial sufficient conditions for graph rigidity and applications to random graphs by Michael Krivelevich, Alan Lew, Peleg Michaeli (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-23713.txt.

Description

Michael Krivelevich and two co-authors give sufficient conditions for graph rigidity, with applications to random graphs. A graph is d-rigid if, for an embedding of its vertices in d-dimensional space, every edge-length preserving motion preserves distances between non-adjacent pairs.

The team shows a constant c exists such that, for p at least two log n over n, the binomial random graph is with high probability floor of c n p-rigid. That is sharp up to the constant c, complementing Peled and Peleg and Jordan, Liu, and Villanyi. For d at least 2 and r at least 501 d, an r-regular graph is with high probability d-rigid. For p between 100 over n and two log n over n, the random graph holds with high probability a floor of n p over 251-rigid subgraph. A sufficient condition for rigidity via codegree generalizes Whiteley's splitting lemmas.

Catalog record

CREATORMichael Krivelevich, Alan Lew, Peleg Michaeli
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-23713

Browse the full library · About the Tower of Babel