Degree Sum Conditions for Graph Rigidity

Abstract

We study sufficient conditions for the generic rigidity of a graph $G$ expressed in terms of (i) its minimum degree $\hat{I}´(G)$, or (ii) the parameter $\hat{I}\cdot (G)={\min }_{uv\notin E}(\hat{A}°(u)+\hat{A}°(v))$. For each case, we seek the smallest integers $f(n,d)$ (resp.\ $g(n,d)$) such that every $n$-vertex graph $G$ with $\hat{I}´(G)\ge f(n,d)$ (resp.\ $\hat{I}\cdot (G)\ge g(n,d)$) is rigid in ${\mathbb{R}}^d$. Krivelevich, Lew, and Michaeli conjectured that there is a constant $K>0$ such that $f(n,d)\le \frac{n}{2}+Kd$ for all pairs $n,d$. We give an affirmative answer to this conjecture by proving that $K=1$ suffices. For $n\ge 29d$, we obtain the exact result $f(n,d)=\lceil \frac{n+d-2}{2}\rceil$. Next, we prove that $g(n,d)\le n+3d$ for all pairs $n,d$, and establish $g(n,d)=n+d-2$ when $n\ge d(d+2)$. For $d=2,3,$ we determine the exact values of $f(n,d)$ and $g(n,d)$ for all $n$, confirming another conjecture of Krivelevich, Lew, and Michaeli in these low-dimensional special cases. As an application, we prove that the Erdős-Rényi random graph $G(n,1/2)$ is a.a.s.\ rigid in ${\mathbb{R}}^d$ for $d=d(n)\sim \frac{7}{32}n$. This result provides the first linear lower bound for $d(n)$, and it answers a question of Peled and Peleg.

23 pages