The ACO Seminar (2024–2025)

A \emph{$d$-dimensional framework} is a pair $(G,p)$, where $G=(V,E)$ is a graph, and $p: V \to \mathbb{R}^d$ is an embedding of the vertex set $V$ in $d$-dimensional space. The framework $(G,p)$ is called \emph{rigid} if there is no continuous motion of the vertices, starting from the positions prescribed by $p$, that preserves the distance between all pairs of adjacent vertices, except for trivial motions --- translations and rotations of the entire graph. The graph $G=(V,E)$ is called \emph{$d$-rigid} if the framework $(G,p)$ is rigid for a \emph{generic} embedding $p: V \to \mathbb{R}^d$.

In this talk, we discuss minimum degree conditions for the rigidity of graphs. In particular, we show that for $d=O(\sqrt{n})$, every $n$-vertex graph with minimum degree at least $(n+d)/2-1$ is $d$-rigid. Moreover, for $d=O(n/\log^2{n})$, we show that for large enough $n$, every $n$-vertex graph with minimum degree at least $(n+2d)/2-1$ is $d$-rigid. The former bound is optimal, while the latter is tight within a factor of two in the coefficient of $d$.

The proof in the case of small $d$ relies on the recent resolution by Villányi of the Lovász-Yemini conjecture, which relates the rigidity of a graph to its vertex-connectivity. For larger $d$, our arguments rely on the method of ``rigid partitions," developed in previous work with Nevo, Peled, and Raz, which provides a useful sufficient condition for the rigidity of a graph.

Based on joint work with Michael Krivelevich and Peleg Michaeli.