{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-27","reactions":{}}