Degree Sum Conditions for Graph Rigidity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917049459015680 |
|---|---|
| author | Jordán, Tibor Liu, Xuemei Villányi, Soma |
| author_facet | Jordán, Tibor Liu, Xuemei Villányi, Soma |
| contents | We study sufficient conditions for the generic rigidity of a graph $G$ expressed in terms of (i) its minimum degree $δ(G)$, or (ii) the parameter $η(G)=\min_{uv\notin E}(°(u)+°(v))$. For each case, we seek the smallest integers $f(n,d)$ (resp.\ $g(n,d)$) such that every $n$-vertex graph $G$ with $δ(G)\geq f(n,d)$ (resp.\ $η(G)\geq 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)\leq \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\geq 29d$, we obtain the exact result $f(n,d)=\lceil\frac{n+d-2}{2} \rceil$. Next, we prove that $g(n,d)\leq n+3d$ for all pairs $n,d$, and establish $g(n,d)=n+d-2$ when $n\geq 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_25689 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Degree Sum Conditions for Graph Rigidity Jordán, Tibor Liu, Xuemei Villányi, Soma Combinatorics 52C25, 05B35 We study sufficient conditions for the generic rigidity of a graph $G$ expressed in terms of (i) its minimum degree $δ(G)$, or (ii) the parameter $η(G)=\min_{uv\notin E}(°(u)+°(v))$. For each case, we seek the smallest integers $f(n,d)$ (resp.\ $g(n,d)$) such that every $n$-vertex graph $G$ with $δ(G)\geq f(n,d)$ (resp.\ $η(G)\geq 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)\leq \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\geq 29d$, we obtain the exact result $f(n,d)=\lceil\frac{n+d-2}{2} \rceil$. Next, we prove that $g(n,d)\leq n+3d$ for all pairs $n,d$, and establish $g(n,d)=n+d-2$ when $n\geq 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. |
| title | Degree Sum Conditions for Graph Rigidity |
| topic | Combinatorics 52C25, 05B35 |
| url | https://arxiv.org/abs/2510.25689 |