Rigidity of expanders and pseudorandom graphs

Abstract

A graph $G=(V,E)$ is called $d$-rigid if, for a generic embedding of its vertices in ${\mathbb{R}}^d$, the only continuous motions of the vertices preserving the distances between all pairs of adjacent vertices are those induced from the isometries of ${\mathbb{R}}^d$ (that is, translations and rotations of the whole graph). In this paper, we study rigidity properties of pseudorandom graphs. First, we consider $C$-expander graphs, a class of graphs recently studied in the context of Hamiltonicity of pseudorandom graphs. These are $n$-vertex graphs for which every vertex set $A$ of size smaller than $n/(2C)$ has a neighbourhood of size at least $C|A|$, and for every pair of disjoint sets $A,B$ of size at least $n/(2C)$ each, there is at least one edge between $A$ and $B$. We show that for every $C\ge 8$ and every integer $n\ge 9C$, every $n$-vertex $C$-expander is $\lfloor C/8\rfloor$-rigid. Next, we study $(n,r,\lambda )$-graphs, which are $n$-vertex $r$-regular graphs whose non-trivial adjacency eigenvalues are bounded in absolute value by $\lambda$. This is a well-known family of graphs, known to possess various pseudorandom properties. We prove that there exist absolute constants $c_1,c_2>0$ such that every $(n,r,\lambda )$-graph $G$ with $\lambda \le c_{1}r$ is $\lfloor c_{2}r\rfloor$-rigid. Our results are sharp up to the value of the universal constants involved, and they improve and extend previous work by the authors on the rigidity of random and pseudorandom graphs.

13 pages