The ACO Seminar (2022–2023)

A d-dimensional framework is a pair $(G,p)$ consisting of a graph $G=(V,E)$ and an embedding $p$ of the vertex set $V$ into $\mathbb R^d$. The framework is said to be rigid if every continuous motion of the vertices that preserves the lengths of all edges in $G$, preserves in fact the distance between any pair of vertices in $G$.

Recently, Jordán and Tanigawa, building on previous work by Hu and Zhu, introduced the d-dimensional algebraic connectivity of a graph $G$, denoted by $a_d(G)$. This is defined as the supremum over all mappings $p:V\to\mathbb R^d$ of the smallest non-trivial eigenvalue of the stiffness matrix $L(G,p)$, which can be seen as a higher-dimensional analogue of the Laplacian matrix of $G$.

The $d$-dimensional algebraic connectivity of a graph is always non-negative, and satisfies $a_d(G)>0$ if and only if a generic embedding of $G$ into $\mathbb R^d$ is rigid. Therefore, we can think of $a_d(G)$ as a quantitative measure of the rigidity of $G$.

In this talk I will introduce the notion of "$d$-rigidity expander graphs"- a family of graphs with increasing number of vertices whose $d$-dimensional algebraic connectivity is bounded away from zero by some positive constant. Then I will present a construction of ($2d+1$)-regular $d$-rigidity expanders. This is conjectured to be optimal, in the sense that $2d$-regular $d$-rigidity expanders are not believed to exist. The main tool in our proof is a new lower bound on $a_d(G)$ defined in terms of the Laplacian spectral gaps of certain subgraphs of $G$ associated with a partition of its vertex set.

Based on joint work with Eran Nevo, Yuval Peled and Orit Raz.