Id: arxiv/2602.23713 Url: https://arxiv.org/abs/2602.23713 Tags: math.CO Score: 0 Title: Combinatorial sufficient conditions for graph rigidity and applications to random graphs Domain: math.CO Source: arxiv Authors: Michael Krivelevich, Alan Lew, Peleg Michaeli Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-27 Page: https://delphi.science/r/arxiv/2602.23713 A graph $G=(V,E)$ is called $d$-rigid if, for a generic embedding of its vertices in $\mathbb{R}^d$, every edge-length preserving continuous motion of the vertices preserves the distances between all pairs of non-adjacent vertices as well. In this paper, we present several new results on the rigidity of random graphs. In particular, we show that there exists $c>0$ such that, for $p\ge 2 \log{n}/n$, the binomial random graph $G(n,p)$ is with high probability (whp) $\lfloor c n p\rfloor$-rigid. This is sharp up to the constant $c$, and complements recent results of Peled and Peleg (in the…