Rigidity expander graphs

Abstract: Jord'an and Tanigawa recently introduced the

d

-dimensional algebraic connectivity

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)

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 g e 2

and

k g e 2 d + 1

. Conjecturally, no such family of

2 d

-regular graphs exists. Second, we show that

a_{d} (K_{n}) g e q f r a c 12 l e f t l f l o o r f r a c n d i g h t f l o o r

, which we conjecture to be essentially tight. In addition, we study the extremal values

a_{d} (G)

attained if

G

is a minimally

d

-rigid graph.

This page was built for publication: Rigidity expander graphs