Expanding graphs, Ramanujan graphs, and 1 -factor perturbations, , November 27, 2006

1 Introduction

Let

X = (V, E)

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

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

λ_{0} (X) \geq λ_{1} (X) \geq . . . \geq λ_{n - 1} (X)

; the spectral gap

λ_{0} (X) - λ_{1} (X)

X

is positive if and only if

X

is connected. Let us assume from now on that

X

k

-regular for some

k \geq 3

, namely that

\sum_{w} A_{v, w} = k

for all

v \in V

, so that

λ_{0} (X) = k

Recall that, for any infinite sequence

(X_{i})_{i \in I}

of connected

k

-regular simple finite graphs with increasing vertex sizes, we have

{liminf}_{i \to \infty} λ_{1} (X_{i}) \geq 2 \sqrt{k - 1}

. A graph

X

is said to be a Ramanujan graph if it is connected and if

| μ | \leq 2 \sqrt{k - 1}

for any eigenvalue

μ \neq \pm k

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

(X_{i})_{i \in I}

k

-regular connected simple finite graphs with increasing vertex sizes such that

{inf}_{i \in I} (k - λ_{1} (X_{i}))

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

(X_{i})_{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

λ_{1} (X_{i}) \leq l - 1 + 2 \sqrt{(k - l)}

; for example, for

k = 7

and

l = 1

, this corresponds to a spectral gap

7 - λ_{1} (X_{i}) \geq 6 - 2 \sqrt{5} \approx 1.52 for all i \in I,

to be compared with the Ramanujan minoration by

7 - {liminf}_{i \in I} λ_{1} (X_{i}) \leq 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 \geq 3

and all

ε > 0

, there exists sequences

{(X_{i})}_{i \in I}

of connected

k

-regular simple finite graphs with increasing vertex sizes and with

λ_{1} (X_{i}) \leq 2 \sqrt{k - 1} + ε

for all

i \in I

Let

X = (V, E)

be a graph. If

X

is not bipartite, we denote by

\bar{X} = (V, \bar{E})

the complement of

X

; two distinct vertices are adjacent in

\bar{X}

if and only if they are not so in

X

. If

X

is bipartite, given with a bipartition

V = V_{0} ⊔ V_{1}

, we denote by

\bar{X} = (V, \bar{E})

the bipartite complement of

X

; two vertices

v \in V_{0}

w \in V_{1}

are adjacent in

\bar{X}

if and only if they are not in

X

A matching of a graph

X

is a subset

M

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

E

such that any vertex

x \in V

is incident with exactly one edge of

F

Let

X = (V, E)

be a graph. If

F

is a perfect matching of

X

, we denote by

X - F

the graph

(V, E \ F)

; if

X

k

-regular, then

X - F

(k - 1)

-regular. If

F

is a perfect matching of

\bar{X}

, we denote by

X + F

the graph

\bar{\bar{X} - F}

; if

X

k

-regular, then

X + F

(k + 1)

-regular.

The basic observation for the present Note is the set of inequalities

| λ_{j} (X \pm F) - λ_{j} (X) | \leq 1

for any perfect matching

F

X

(for

X - F

) or of

\bar{X}

(for

X + F

), and for all

j \in {0, . . ., n - 1}

, 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

(p, q)

for which the graph

X^{p, q}

is bipartite). In conclusion, we report some numerical computations.

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

Let us recall the definition of the graphs

X^{p, q}

R

is a commutative ring with unit, the Hamilton quaternion algebra

H (R)

over

R

is the free module

R^{4}

with basis

{1, i, j, k}

, where multiplication is defined by

i^{2} = j^{2} = k^{2} = - 1

, and

i j = - j i = 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

\bar{q} = a_{0} - a_{1} i - a_{2} j - a_{3} k

and a norm

N (q) = \bar{q} q = a_{0}^{2} + a_{1}^{2} + a_{2}^{2} + a_{3}^{2}

Let

p \in N

be an odd prime. If

p \equiv 1 (m o d 4)

, a theorem of Jacobi shows that there are exactly

p + 1

quaternions in

H (Z)

of norm

p

of the form

a_{0} + a_{1} i + a_{2} j + a_{3} k

with

a_{0} \equiv 1 (m o d 2)

, and

a_{0} \geq 1

. These occur in pairs

(α, \bar{α})

; we select arbitrarily one, say

α_{l}

, from each pair, and we set

S_{p} = {α_{1}, \bar{α_{1}}, . . ., α_{s}, \bar{α_{s}}} with 2 s = p + 1 .

p \equiv 3 (m o d 4)

, there are quaternions in

H (Z)

of norm

p

of the form

a_{0} + a_{1} i + a_{2} j + a_{3} k

with

a_{0} \equiv 0 (m o d 2)

, and

a_{0} \geq 0

. From those with

a_{0} \geq 2

, say

2 s

of them, we obtain

α_{1}, . . ., α_{s}

as above. Those of the form

a_{1} i + a_{2} j + a_{3} k

, say

2 t

of them ^$1$ , occur in pairs

(β, - β)

; we select arbitrarily one, say

β_{m}

, from each pair, and we set

S_{p} = {α_{1}, \bar{α_{1}}, . . ., α_{s}, \bar{α_{s}}, β_{1}, . . ., β_{t}} .

Observe that

t / 4

is the number of solutions in

N

of the equation

a_{1}^{2} + a_{2}^{2} + a_{3}^{2} = p

, and that we have again

| S_{p} | = 2 s + 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 (m o d 8)

), or both

s

and

t

positive (case of

p = 19

, with

s = 4

and

t = 12

Let

q

be another odd prime,

q \neq p

, and let

τ_{q} : H (Z) ⟶ H (F_{q})

denote reduction modulo

q

. The equation

x^{2} + y^{2} + 1 = 0

has solutions in

F_{q}

. We choose one solution; then the mapping

ψ_{q} : H (F_{q}) ⟶ M_{2} (F_{q})

defined by

ψ_{q} (a_{0} + a_{1} i + a_{2} j + a_{3} k) = (\begin{matrix} 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{matrix})

is an algebra isomorphism and

ψ_{q} (τ_{q} (S_{p}))

is in the group

G L_{2} (q)

of invertible elements of

M_{2} (F_{q})

. We denote by

φ : G L_{2} (q) ⟶ P G L_{2} (q)

the reduction modulo the centre, and we set

S_{p, q} = φ (ψ_{q} (τ_{q} (S_{p}))) \subset P G L_{2} (q) .

It follows from the definitions that

S_{p, q}

is symmetric: if

s \in S_{p, q}

is the image of

α_{l} \in S_{p}

(notation as above), then

s^{- 1}

is the image of

\bar{α_{l}}

; if

s

is the image of

β_{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 P S L_{2} (q)

and indeed

S_{p, q}

generates

P S L_{2} (q)

. By definition,

X^{p, q}

is the Cayley graph of

P S L_{2} (q)

with respect to

S_{p, q}

; more precisely,

X^{p, q} = (V, E)

with

V = P S L_{2} (q)

and

{v, w} \in E

v^{- 1} w \in S^{p, q}

. It is a

(p + 1)

-regular graph with

\frac{1}{2} q (q^{2} - 1)

vertices which is connected, non-bipartite, and which is a Ramanujan graph.

p

is not a square modulo

q

. Then

S_{p, q} \cap P S L_{2} (q) = \emptyset

and

S_{p, q}

generates

P G L_{2} (q)

. By definition,

X^{p, q}

is the Cayley graph of

P G L_{2} (q)

with respect to

S_{p, q}

. It is a

(p + 1)

-regular bipartite graph with

q (q^{2} - 1)

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 \geq 5

and

q > p^{8}

, and the expanding property of this family. For the proof that

{(X^{p, q})}_{q}

is actually a family ^$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 {5, 7, 11}

and Table II that of

X^{5, q}

for

q \in {7, 11}

. 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

\bar{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

P G L_{2} (q)

and

P S L_{2} (q)

□

Proposition 2 Let

X = (V, E)

be a finite graph with

n

vertices and with eigenvalues

λ_{0} \geq λ_{1} \geq . . . \geq λ_{n - 1}

. Let

F

be a matching of

X

[respectively of the complement

\bar{X}

] and let

μ_{0} \geq μ_{1} . . . \geq μ_{n - 1}

be the eigenvalues of

X - F

[respectively

X + F

]. Then

| μ_{j} - λ_{j} | \leq 1

for

j \in {0, 1, . . ., n - 1}

Proof Outside diagonal entries, the adjacency matrix

A_{F}

(V, F)

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

∥ A_{F} ∥ \leq 1

Here, the norm of a matrix acting on the Euclidean space

R^{V}

is the operator norm

∥ A_{F} ∥ = sup {∥ A f ∥_{2} | f \in R^{V}, ∥ f ∥_{2} \leq 1}

, where

∥ f ∥_{2}^{2} = \sum_{v \in V} | f (v) |^{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].

□

^$1$ Observe that $2 t$ 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.

^$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

(p, q)

the values of the spectral gaps

p - λ_{1} (X^{p, q} - F)

corresponding to four different

F

. Table III shows that there are situations (

p = 5, q = 7

) with

λ_{0} (X - F) = k - 1 < λ_{0} (X) = k

and

λ_{1} (X - F) > λ_{1} (X)

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.

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

Pierre de la Harpe and Antoine Musitelli adress email: Pierre.delaHarpe@math.unige.ch and musitel0@math.unige.ch

November 27, 2006