Rigidity Expander Graphs
Alan Lew, Eran Nevo, Yuval Peled, Orit E. Raz · COMBINATORICA · 2025
Abstract Jordán and Tanigawa recently introduced the d-dimensional algebraic connectivity $$a_d(G)$$ a d ( G ) of a graph G. This is a quantitative measure of the d-dimensional rigidity of G which generalizes the well-studied notion of spectral expansion of graphs. We present a new lower bound for $$a_d(G)$$ a d ( G ) defined in terms of the spectral expansion of certain subgraphs of G associated with a partition of its vertices into d parts. In particular, we obtain a new sufficient condition for the rigidity of a graph G. As a first application, we prove the existence of an infinite family of k-regular d-rigidity-expander graphs for every $$d\ge 2$$ d ≥ 2 and $$k\ge 2d+1$$ k ≥ 2 d + 1 . Conjecturally, no such family of 2d-regular graphs exists. Second, we show that $$a_d(K_n)\ge \frac{1}{2}\left\lfloor \frac{n}{d}\right\rfloor $$ a d ( K n ) ≥ 1 2 n d , which we conjecture to be essentially tight. In addition, we study the extremal values $$a_d(G)$$ a d ( G ) attains if G is a minimally d-rigid graph.