Rigidity Expander Graphs

Abstract Jordán and Tanigawa recently introduced the d -dimensional algebraic connectivity $$a_d(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>d</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>d</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> </mml:mrow> </mml:math> and $$k\ge 2d+1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>2</mml:mn> <mml:mi>d</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> . Conjecturally, no such family of 2 d -regular graphs exists. Second, we show that $$a_d(K_n)\ge \frac{1}{2}\left\lfloor \frac{n}{d}\right\rfloor $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>d</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>K</mml:mi> <mml:mi>n</mml:mi> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≥</mml:mo> <mml:mfrac> <mml:mn>1</mml:mn> <mml:mn>2</mml:mn> </mml:mfrac> <mml:mfenced> <mml:mfrac> <mml:mi>n</mml:mi> <mml:mi>d</mml:mi> </mml:mfrac> </mml:mfenced> </mml:mrow> </mml:math> , which we conjecture to be essentially tight. In addition, we study the extremal values $$a_d(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>a</mml:mi> <mml:mi>d</mml:mi> </mml:msub> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> attains if G is a minimally d -rigid graph.