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
| CREATOR | Michael Krivelevich, Alan Lew, Peleg Michaeli |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 69 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2602-23713