Abstract:We study generic $d$-dimensional rigidity in sparse random graphs. Our main result is that for every $d\ge 2$, the Erdős--Rényi random graph $G\sim G(n,c/n)$ undergoes a $d$-rigidity phase transition at the known, explicit, $d$-orientability threshold $c_d$: If $c<c_d$, then $G$ is asymptotically almost surely (a.a.s.) independent in the generic $d$-rigidity matroid. Moreover, in this regime $G$ has no linear-size rigidity components: it contains no induced $d$-rigid subgraphs with more than $3$ vertices, and the largest clique in its $d$-rigidity closure has size at most $o(\sqrt n)$. If $c>c_d$, then the $d$-rigidity closure of $G$ a.a.s. has a giant clique of linear size, which contains all but at most $o(n)$ vertices of the $((d+1)+d)$-core of the graph. We also give a sharp asymptotic estimate for the generic $d$-rigidity rank of $G$ in the supercritical regime. More generally, we compute, up to a $1+o(1)$ factor, the generic $d$-rigidity rank of random graphs with a given degree distribution. For example, we show that the uniform $n$-vertex $k$-regular graph a.a.s. has rank $\min(k/2,d)n+o(n).$ Our approach is to estimate the rigidity rank of a random graph from its Galton--Watson local weak limit, using a parameter that we call {\em local flexibility}.
| Subjects: | Combinatorics (math.CO); Probability (math.PR) |
| Cite as: | arXiv:2605.25711 [math.CO] |
| (or arXiv:2605.25711v1 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2605.25711 arXiv-issued DOI via DataCite (pending registration) |
From: Yuval Peled [view email]
[v1]
Mon, 25 May 2026 11:12:42 UTC (49 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。