Expanding graphs, Ramanujan graphs, and $1$-factor perturbations

November 27, 2006

Abstract
We construct $\left(k±1\right)$  -regular graphs which provide sequences of expanders by adding or substracting appropriate $1$  -factors from given sequences of $k$  -regular graphs. We compute numerical examples in a few cases for which the given sequences are from the work of Lubotzky, Phillips, and Sarnak (with $k-1$  the order of a finite field). If $k+1=7$  , our construction results in a sequence of $7$  -regular expanders with all spectral gaps at least $6-2\sqrt{5}\approx 1.52$  ; the corresponding minoration for a sequence of Ramanujan $7$  -regular graphs (which is not known to exist) would be $7-2\sqrt{6}\approx 2.10$  .

1 Introduction

Let $X=\left(V,E\right)$  be a simple finite graph with $n$  vertices, where $V$  denotes the vertex set and $E$  the set of geometrical edges of $X$  . The adjacency matrix $A$  of $X$  , with rows and columns indexed by $V$  , is defined by ${A}_{v,w}=1$  if there exists an edge connecting $v$  and $w$  , and ${A}_{v,w}=0$  otherwise (in particular ${A}_{v,v}=0$  ). The eigenvalues of $X$  , which are those of $A$  , constitute a decreasing sequence ${\lambda }_{0}\left(X\right)\ge {\lambda }_{1}\left(X\right)\ge ...\ge {\lambda }_{n-1}\left(X\right)$  ; the spectral gap ${\lambda }_{0}\left(X\right)-{\lambda }_{1}\left(X\right)$  of $X$  is positive if and only if $X$  is connected. Let us assume from now on that $X$  is $k$  -regular for some $k\ge 3$  , namely that ${\sum }_{w}{A}_{v,w}=k$  for all $v\in V$  , so that ${\lambda }_{0}\left(X\right)=k$  .
Recall that, for any infinite sequence $\left({X}_{i}{\right)}_{i\in I}$  of connected $k$  -regular simple finite graphs with increasing vertex sizes, we have ${liminf}_{i\to \infty }{\lambda }_{1}\left({X}_{i}\right)\ge 2\sqrt{k-1}$  . A graph $X$  is said to be a Ramanujan graph if it is connected and if $|\mu |\le 2\sqrt{k-1}$  for any eigenvalue $\mu \ne ±k$  of $X$  . From elaborate arithmetic constructions, we know explicit infinite sequences of Ramanujan graphs for degree $k$  when $k-1$  is the order of a finite field; but the existence of such sequences is an open problem for other degrees, for example when $k=7$  . It is thus interesting to find sequences of expanders of degree $k$  , namely infinite sequences $\left({X}_{i}{\right)}_{i\in I}$  of $k$  -regular connected simple finite graphs with increasing vertex sizes such that ${inf}_{i\in I}\left(k-{\lambda }_{1}\left({X}_{i}\right)\right)$  is strictly positive, and indeed as large as possible (short of being equal to $k-2\sqrt{k-1}$  ).
For all this, see for example [Lubot–94], [Valet–97], [Colin–98], and [DaSaV–03].
The object of the present Note is to examine a procedure of construction of sequences of expanders $\left({X}_{i}{\right)}_{i\in I}$  of degree $k$  by perturbation of sequences of Ramanujan graphs. When $k-l$  is the order of a finite field, we obtain estimates ${\lambda }_{1}\left({X}_{i}\right)\le l-1+2\sqrt{\left(k-l\right)}$  ; for example, for $k=7$  and $l=1$  , this corresponds to a spectral gap $7-{\lambda }_{1}\left({X}_{i}\right)\ge 6-2\sqrt{5}\approx 1.52\text{for all}i\in I\text{,}$  to be compared with the Ramanujan minoration by $7-{liminf}_{i\in I}{\lambda }_{1}\left({X}_{i}\right)\le 7-2\sqrt{6}\approx 2.10$  of the spectral gap.
We insist on finding explicit constructions, but we record however the following results of J. Friedman (see [Fried–91], and later work) based on random techniques: for all $k\ge 3$  and all $\epsilon >0$  , there exists sequences ${\left({X}_{i}\right)}_{i\in I}$  of connected $k$  -regular simple finite graphs with increasing vertex sizes and with ${\lambda }_{1}\left({X}_{i}\right)\le 2\sqrt{k-1}+\epsilon$  for all $i\in I$  .
Let $X=\left(V,E\right)$  be a graph. If $X$  is not bipartite, we denote by $\overline{X}=\left(V,\overline{E}\right)$  the complement of $X$  ; two distinct vertices are adjacent in $\overline{X}$  if and only if they are not so in $X$  . If $X$  is bipartite, given with a bipartition $V={V}_{0}\bigsqcup {V}_{1}$  , we denote by $\overline{X}=\left(V,\overline{E}\right)$  the bipartite complement of $X$  ; two vertices $v\in {V}_{0}$  , $w\in {V}_{1}$  are adjacent in $\overline{X}$  if and only if they are not in $X$  .
A matching of a graph $X$  is a subset $M$  of $E$  such that any vertex $x\in V$  is incident with at most one edge of $M$  , and a perfect matching (also called $1$  -factor) is a subset $F$  of $E$  such that any vertex $x\in V$  is incident with exactly one edge of $F$  .
Let $X=\left(V,E\right)$  be a graph. If $F$  is a perfect matching of $X$  , we denote by $X-F$  the graph $\left(V,E\F\right)$  ; if $X$  is $k$  -regular, then $X-F$  is $\left(k-1\right)$  -regular. If $F$  is a perfect matching of $\overline{X}$  , we denote by $X+F$  the graph $\overline{\overline{X}-F}$  ; if $X$  is $k$  -regular, then $X+F$  is $\left(k+1\right)$  -regular.
The basic observation for the present Note is the set of inequalities $|{\lambda }_{j}\left(X±F\right)-{\lambda }_{j}\left(X\right)|\le 1$  for any perfect matching $F$  of $X$  (for $X-F$  ) or of $\overline{X}$  (for $X+F$  ), and for all $j\in \left\{0,...,n-1\right\}$  , where $n=|V|$  (Proposition 2). We can apply this to the Ramanujan graphs ${X}^{p,q}$  and their complements (notation of [DaSaV-03], see below). In Section 3, we describe an algorithm for finding perfect matchings in regular bipartite graphs (thus concentrating on pairs $\left(p,q\right)$  for which the graph ${X}^{p,q}$  is bipartite). In conclusion, we report some numerical computations.

2 Graphs of the form ${X}^{p,q}±F$

Let us recall the definition of the graphs ${X}^{p,q}$  .
If $R$  is a commutative ring with unit, the Hamilton quaternion algebra $\mathbb{H}\left(R\right)$  over $R$  is the free module ${R}^{4}$  with basis $\left\{1,i,j,k\right\}$  , where multiplication is defined by ${i}^{2}={j}^{2}={k}^{2}=-1$  , and $ij=-ji=k$  , plus circular permutations of $i,j,k$  . A quaternion $q={a}_{0}+{a}_{1}i+{a}_{2}j+{a}_{3}k$  has a conjugate $\overline{q}={a}_{0}-{a}_{1}i-{a}_{2}j-{a}_{3}k$  and a norm $N\left(q\right)=\overline{q}q={a}_{0}^{2}+{a}_{1}^{2}+{a}_{2}^{2}+{a}_{3}^{2}$  .
Let $p\in \mathbb{N}$  be an odd prime. If $p\equiv 1\left(mod4\right)$  , a theorem of Jacobi shows that there are exactly $p+1$  quaternions in $\mathbb{H}\left(\mathbb{Z}\right)$  of norm $p$  of the form ${a}_{0}+{a}_{1}i+{a}_{2}j+{a}_{3}k$  with ${a}_{0}\equiv 1\left(mod2\right)$  , and ${a}_{0}\ge 1$  . These occur in pairs $\left(\alpha ,\overline{\alpha }\right)$  ; we select arbitrarily one, say ${\alpha }_{l}$  , from each pair, and we set ${S}_{p}=\left\{{\alpha }_{1},\overline{{\alpha }_{1}},...,{\alpha }_{s},\overline{{\alpha }_{s}}\right\}\text{with}2s=p+1.$  If $p\equiv 3\left(mod4\right)$  , there are quaternions in $\mathbb{H}\left(\mathbb{Z}\right)$  of norm $p$  of the form ${a}_{0}+{a}_{1}i+{a}_{2}j+{a}_{3}k$  with ${a}_{0}\equiv 0\left(mod2\right)$  , and ${a}_{0}\ge 0$  . From those with ${a}_{0}\ge 2$  , say $2s$  of them, we obtain ${\alpha }_{1},...,{\alpha }_{s}$  as above. Those of the form ${a}_{1}i+{a}_{2}j+{a}_{3}k$  , say $2t$  of them $\text{1}$  , occur in pairs $\left(\beta ,-\beta \right)$  ; we select arbitrarily one, say ${\beta }_{m}$  , from each pair, and we set ${S}_{p}=\left\{{\alpha }_{1},\overline{{\alpha }_{1}},...,{\alpha }_{s},\overline{{\alpha }_{s}},{\beta }_{1},...,{\beta }_{t}\right\}.$  Observe that $t/4$  is the number of solutions in $\mathbb{N}$  of the equation ${a}_{1}^{2}+{a}_{2}^{2}+{a}_{3}^{2}=p$  , and that we have again $|{S}_{p}|=2s+t=p+1$  by Jacobi's theorem. Observe also that we can have $s=0$  (case of $p=3$  ), as well as $t=0$  (case of $p\equiv 7\left(mod8\right)$  ), or both $s$  and $t$  positive (case of $p=19$  , with $s=4$  and $t=12$  ).
Let $q$  be another odd prime, $q\ne p$  , and let ${\tau }_{q}:\mathbb{H}\left(\mathbb{Z}\right)⟶\mathbb{H}\left({\mathbb{F}}_{q}\right)$  denote reduction modulo $q$  . The equation ${x}^{2}+{y}^{2}+1=0$  has solutions in ${\mathbb{F}}_{q}$  . We choose one solution; then the mapping ${\psi }_{q}:\mathbb{H}\left({\mathbb{F}}_{q}\right)⟶{M}_{2}\left({\mathbb{F}}_{q}\right)$  defined by ${\psi }_{q}\left({a}_{0}+{a}_{1}i+{a}_{2}j+{a}_{3}k\right)=\left(\begin{array}{cc}{a}_{0}+{a}_{1}x+{a}_{3}y& -{a}_{2}y+{a}_{1}+{a}_{3}x\\ -{a}_{1}y-{a}_{2}+{a}_{3}x& {a}_{0}-{a}_{1}x-{a}_{2}y\end{array}\right)$  is an algebra isomorphism and ${\psi }_{q}\left({\tau }_{q}\left({S}_{p}\right)\right)$  is in the group $G{L}_{2}\left(q\right)$  of invertible elements of ${M}_{2}\left({\mathbb{F}}_{q}\right)$  . We denote by $\phi :G{L}_{2}\left(q\right)⟶PG{L}_{2}\left(q\right)$  the reduction modulo the centre, and we set ${S}_{p,q}=\phi \left({\psi }_{q}\left({\tau }_{q}\left({S}_{p}\right)\right)\right)\subset PG{L}_{2}\left(q\right).$  It follows from the definitions that ${S}_{p,q}$  is symmetric: if $s\in {S}_{p,q}$  is the image of ${\alpha }_{l}\in {S}_{p}$  (notation as above), then ${s}^{-1}$  is the image of $\overline{{\alpha }_{l}}$  ; if $s$  is the image of ${\beta }_{m}\in {S}_{p}$  , then ${s}^{2}=1$  . Moreover, it is known that $|{S}_{p,q}|=p+1$  . There are now two cases to consider.
Either $p$  is a square modulo $q$  . Then ${S}_{p,q}\subset PS{L}_{2}\left(q\right)$  and indeed ${S}_{p,q}$  generates $PS{L}_{2}\left(q\right)$  . By definition, ${X}^{p,q}$  is the Cayley graph of $PS{L}_{2}\left(q\right)$  with respect to ${S}_{p,q}$  ; more precisely, ${X}^{p,q}=\left(V,E\right)$  with $V=PS{L}_{2}\left(q\right)$  and $\left\{v,w\right\}\in E$  if ${v}^{-1}w\in {S}^{p,q}$  . It is a $\left(p+1\right)$  -regular graph with $\frac{1}{2}q\left({q}^{2}-1\right)$  vertices which is connected, non-bipartite, and which is a Ramanujan graph.
Or $p$  is not a square modulo $q$  . Then ${S}_{p,q}\cap PS{L}_{2}\left(q\right)=\varnothing$  and ${S}_{p,q}$  generates $PG{L}_{2}\left(q\right)$  . By definition, ${X}^{p,q}$  is the Cayley graph of $PG{L}_{2}\left(q\right)$  with respect to ${S}_{p,q}$  . It is a $\left(p+1\right)$  -regular bipartite graph with $q\left({q}^{2}-1\right)$  vertices which is connected and which is a Ramanujan graph.
See [DaSaV–03] for proofs of a large part of the facts stated above, including the connectedness of the graphs ${X}^{p,q}$  when $p\ge 5$  and $q>{p}^{8}$  , and the expanding property of this family. For the proof that ${\left({X}^{p,q}\right)}_{q}$  is actually a family $\text{2}$  of Ramanujan graphs, see the original papers ([LuPhS–88], with a large part obtained independently in [Margu–88]), as well as [Sarna–90].
Table I shows the spectrum of ${X}^{3,q}$  for $q\in \left\{5,7,11\right\}$  and Table II that of ${X}^{5,q}$  for $q\in \left\{7,11\right\}$  . Numerical computations of eigenvalues reported in this paper have been computed with Mathlab.
Proposition 1 If the graph ${X}^{p,q}$  is bipartite, ${X}^{p,q}$  and its bipartite complement $\overline{{X}^{p,q}}$  have perfect matchings.
Proof This is a case of the “Marriage Theorem”; see for example Corollary 1.1.4 in [LovPl–86]. Here is another reason for ${X}^{p,q}$  (bipartite or not): any connected vertex-transitive graph of even order has a perfect matching (Section 3.5 in [GodRo–01]); this applies in particular to Cayley graphs of finite groups of even order, such as $PG{L}_{2}\left(q\right)$  and $PS{L}_{2}\left(q\right)$  . $\square$
Proposition 2 Let $X=\left(V,E\right)$  be a finite graph with $n$  vertices and with eigenvalues ${\lambda }_{0}\ge {\lambda }_{1}\ge ...\ge {\lambda }_{n-1}$  . Let $F$  be a matching of $X$  [respectively of the complement $\overline{X}$  ] and let ${\mu }_{0}\ge {\mu }_{1}...\ge {\mu }_{n-1}$  be the eigenvalues of $X-F$  [respectively $X+F$  ]. Then $|{\mu }_{j}-{\lambda }_{j}|\le 1$  for $j\in \left\{0,1,...,n-1\right\}$  .
Proof Outside diagonal entries, the adjacency matrix ${A}_{F}$  of $\left(V,F\right)$  coincides with a matrix of permutation (the permutation being a non-empty product of transpositions with disjoint supports, one transposition for each edge in $F$  ). Thus $\parallel {A}_{F}\parallel \le 1$  .
Here, the norm of a matrix acting on the Euclidean space ${\mathbb{R}}^{V}$  is the operator norm $\parallel {A}_{F}\parallel =sup\left\{\parallel Af{\parallel }_{2}|f\in {\mathbb{R}}^{V},\parallel f{\parallel }_{2}\le 1\right\}$  , where $\parallel f{\parallel }_{2}^{2}={\sum }_{v\in V}|f\left(v\right){|}^{2}$  .
Thus Proposition 1 follows from the classical Courant-Fischer-Weyl minimax principle, according to which eigenvalues of symmetric operators are norms of appropriate restrictions of these operators. See e.g. Chapter III in [Bhati–97]. $\square$

$\text{1}$  Observe that $2t$  is a multiple of $8$  , since each of ${a}_{1},$  ${a}_{2}$  , ${a}_{3}$  is odd, in particular not $0$  , so that each sign change provides another writing of $p$  as a sum of three squares.

$\text{2}$  The family is indexed by the set of all odd primes $q$  , and $p$  is a fixed arbitrary odd prime.

3 Tables

There are several standard efficient algorithms to find a perfect matching $F$  in a graph $X$  ; see [LovPl–86] and [West–01], among others. We will not describe here the details of the algorithm we have used. Eigenvalues of $X-F$  can then be computed with Mathlab. The eigenvalues of a graph of the form ${X}^{p,q}-F$  depend on the choice of $F$  . Table III gives for each of three pairs $\left(p,q\right)$  the values of the spectral gaps $p-{\lambda }_{1}\left({X}^{p,q}-F\right)$  corresponding to four different $F$  . Table III shows that there are situations ( $p=5,q=7$  ) with ${\lambda }_{0}\left(X-F\right)=k-1<{\lambda }_{0}\left(X\right)=k$  and ${\lambda }_{1}\left(X-F\right)>{\lambda }_{1}\left(X\right)$  .
Table IV shows the full spectrum of ${X}^{3,5}-F$  for one specific $F$  . Tables V to VII show the ten largest eigenvalues of three graphs of the form ${X}^{p,q}+F$  . Observe that the multiplicities in Tables IV to VII are much less than those of the unperturbed graphs.
 Table I: spectra of ${X}^{3,q}$ q=5 q=7 q=11 eigenvalues multiplicities eigenvalues multiplicities eigenvalues multiplicities -4.0000 1 -4.0000 1 -3.2361 30 -3.0000 12 -3.0000 24 -3.0000 33 -2.0000 28 -2.8284 30 -2.7321 10 -1.0000 4 -2.0000 28 -2.6180 24 0.0000 30 -1.4142 24 -2.3723 10 1.0000 4 -1.0000 40 -2.0468 36 2.0000 28 0.0000 42 -2.0000 10 3.0000 12 1.0000 40 -1.6180 36 4.0000 1 1.4142 24 -1.5616 33 2.0000 28 -0.9191 36 2.8284 30 -0.7321 30 3.0000 24 -0.3820 24 4.0000 1 0.0000 30 0.3820 12 0.6180 36 0.7321 10 1.0000 52 1.2361 30 1.9191 36 2.0000 20 2.5616 33 2.6180 12 2.7321 30 3.0468 36 3.3723 10 4.0000 1
 Table II: spectra of ${X}^{5,q}$ q=7 q=11 eigenvalues multiplicities eigenvalues multiplicities -6.0000 1 -4.0243 36 -4.0000 21 -3.7321 30 -3.0000 16 -3.0000 65 -2.8284 42 -2.2361 30 -2.0000 21 -1.7321 10 -1.4142 12 -1.6180 60 -1.0000 48 -1.3723 10 0.0000 14 -1.2361 12 1.0000 48 -0.5616 33 1.4142 12 -0.2679 30 2.0000 21 -0.1638 36 2.8284 42 0.6180 60 3.0000 16 1.0000 30 4.0000 21 1.7321 10 6.0000 1 1.7818 36 2.2361 30 3.0000 50 3.2361 12 3.4063 36 3.5616 33 4.3723 10 6.0000 1
 Table III: spectral gaps for ${X}^{p,q}-F$ p=3,q=5 p=3,q=7 p=5,q=7 0.4457 0.2499 0.7910 0.3025 0.1862 0.7732 0.2993 0.1785 0.7367 0.2702 0.0272 0.7152
 Table IV: spectrum of ${X}^{3,5}-F$ eigenvalues multiplicities -3.0000 1 -2.5543 8 -2.5450 4 -2.1542 4 -2.0000 6 -1.8829 8 -1.2929 8 -1.0000 3 -0.8302 4 -0.5086 8 -0.4394 4 0.0000 4 0.4394 4 0.5086 8 0.8302 4 1.0000 3 1.2929 8 1.8829 8 2.0000 6 2.1542 4 2.5450 4 2.5543 8 3.0000 1
 Table V: largest eigenvalues for ${X}^{3,5}+F$ eigenvalues multiplicities eigenvalues multiplicities eigenvalues multiplicities 3.2578 1 3.2163 1 3.1707 1 3.3225 1 3.3208 1 3.1998 1 3.3425 1 3.3431 1 3.2214 1 3.4295 1 3.4417 1 3.2418 1 3.4859 1 3.4992 1 3.3046 1 3.5140 1 3.5358 1 3.5525 1 3.5687 1 3.6211 1 3.5653 1 3.5950 1 3.6822 1 3.5935 1 3.6758 1 3.8466 1 3.6547 1 5.0000 1 5.0000 1 5.0000 1
 Table VI: largest eigenvalues for ${X}^{3,7}+F$ eigenvalues multiplicities eigenvalues multiplicities eigenvalues multiplicities 3.6042 1 3.6199 1 3.6138 1 3.6130 1 3.6478 1 3.6431 1 3.6349 1 3.6594 1 3.6524 1 3.6728 1 3.6826 1 3.6726 1 3.6892 1 3.6996 1 3.6922 1 3.6971 1 3.7203 1 3.7131 1 3.7073 1 3.7468 1 3.7275 1 3.7505 1 3.7548 1 3.7461 1 3.7697 1 3.7752 1 3.7985 1 5.0000 1 5.0000 1 5.0000 1
 Table VII: largest eigenvalues for ${X}^{5,7}+F$ eigenvalues multiplicities eigenvalues multiplicities eigenvalues multiplicities 4.3702 1 4.3388 1 4.3229 1 4.4015 1 4.3738 1 4.3405 1 4.4271 1 4.4326 1 4.3882 1 4.4625 1 4.4790 1 4.4117 1 4.4888 1 4.5124 1 4.4671 1 4.4971 1 4.5618 1 4.5585 1 4.5819 1 4.5925 1 4.5875 1 4.5976 1 4.6417 1 4.6341 1 4.6512 1 4.6892 1 4.7260 1 7.0000 1 7.0000 1 7.0000 1
References
• [Bhati–97 ] R. Bhatia, Matrix analysis, Graduate Texts in Mathematics 169, Springer 1997
• [Colin–98 ] Y. Colin de Verdière, Spectres de graphes, Cours spécialisés 4, Soc. Math. France 1998.
• [DaSaV–03 ] G. Davidoff, P. Sarnak, and A. Valette, Elementary number theory, group theory, and Ramanujan graphs, London Math. Soc. Student Texts 55, Cambridge Univ. Press 2003.
• [Fried–91 ] J. Friedman, On the second eigenvalue and random walks in random $d$  -regular graphs, Combinatorica 11 (1991) 331–362.
• [GodRo–01 ] C. Godsil and G. Royle, Algebraic graph theory, Graduate Texts in Mathematics 207, Springer 2001.
• [LovPl–86 ] L. Lovász and M.D. Plummer, Matching theory, Annals Discrete Math. 29, North Holland, 1986.
• [Lubot–94 ] A. Lubotzky, Discrete groups, expanding graphs and invariant measure, Birkhäuser 1994.
• [LuPhS–88 ] A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica 8, 1988, pages 261–277.
• [Margu–88 ] G.A. Margulis, Explicit group-theoretical constructions of combinatorial schemes and their application to the design of expanders and concentrators, J. Probl. Inf. Transm 24, 1988, pages 39–46.
• [Sarna–90 ] P. Sarnak, Some applications of modular forms, Cambridge University Press 1990.
• [Valet–97 ] A. Valette, Graphes de Ramanujan et applications, Séminaire Bourbaki, exposé 829, Astérisque, 245, Soc. Math. France 1997, pages 247–296.
• [West–01 ] D.B. West, Introduction to graph theory, second edition, Prentice Hall 2001.