See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/222200193

Spectra of Regular Graphs and Hypergraphs and Orthogonal Polynomials

Article  in  European Journal of Combinatorics · July 1996

DOI: 10.1006/eujc.1996.0040 · Source: dx.doi.org

CITATIONS READS

65 314

2 authors:

Winnie Li Patrick Solé

Pennsylvania State University Aix-Marseille Université
123 PUBLICATIONS   1,760 CITATIONS    466 PUBLICATIONS   7,919 CITATIONS   

SEE PROFILE SEE PROFILE

Some of the authors of this publication are also working on these related projects:

pseudo random sequences over rings View project

Boolean functions over rings View project

All content following this page was uploaded by Patrick Solé on 14 January 2021.

The user has requested enhancement of the downloaded file.

Europ. J. Combinatorics (1996) 17 , 461 – 477

Spectra of Regular Graphs and Hypergraphs

and Orthogonal Polynomials
WEN-CH’ING WINNIE LI AND PATRICK SOLE´

In this paper we study the distribution of eigenvalues of regular graphs, regular hypergraphs,
and biregular bipartite graphs of given girth by considering the polynomials orthogonal with
respect to the measures attached to the spectra of such graphs and to the continuous spectra of
their ‘universal covers’. Our estimates are tight for Biggs graphs and generalized polygons. We
also give an application to the distribution of eigenvalues of Hecke operators acting on weight 2
cusp forms for certain congruence subgroups.

÷ 1996 Academic Press Limited

1. INTRODUCTION
The second largest eigenvalue (in modulus) L of a regular graph has deep
connections with many important measurements of the graph, such as the diameter [6],
the covering number [7] and the convergence properties of simple random walks on the
graph [9]. A well-known result, proved in [17, Proposition 4.2], asserts that,
asymptotically, a regular graph of fixed degree k and sufficiently large size has its L at
least 24k 2 1 (1 1 o (1)). This kind of eigenvalue estimate has also been extended
recently to hypergraphs [8]. In [20], more precise estimates for graphs are obtained
under the more stringent hypothesis of fixed girth.
In this paper, we recast the theme of [20] in greater detail and with more caution,
and also extend the results to regular hypergraphs and regular bigraphs. The central
idea is to approximate the distribution of the spectrum of such a (hyper-, bi-)graph by
the distribution of the continuous spectrum of its ‘universal cover’. This is made more
precise by considering polynomials orthogonal with respect to the measures arising
from both spectra. The zeroes of these polynomials are then used to estimate the
non-trivial extremal eigenvalues as well as the overall distribution of the spectrum of
the finite graph of given girth (cf. Theorems 3, 4, 7, 8, 11, 12, 14 and 15). An important
technical difference in contrast with [20] is the use of variations of the measures arising
from spectra; these are the usual measures multiplied by suitable factors designed to
eliminate trivial eigenvalues. The zeroes of polynomials orthogonal with respect to
these measures (adjacent polynomials in the terminology of Levenshtein [16]) enable
us to derive non-trivial bounds for extremal non-trivial eigenvalues. Our estimates of
eigenvalues are tight in some cases; for instance, they are satisfied by Biggs graphs in
the case of regular graphs (Theorem 6), and by generalized polygons in the case of
hypergraphs (Theorem 13). Our results on spectra of regular graphs with given girth
have an application to the distribution of eigenvalues of Hecke operators acting on the
space of weight 2 cusp forms for certain congruence subgroups (Theorem 16).
The material is organized as follows. In Section 2 we recall the basic results on
orthogonal polynomials, which are needed later. Section 3 deals with regular graphs,
while Section 4 deals with regular hypergraphs and bigraphs. In each case, we explain
the universal cover, measures and the orthogonal polynomials involved. Many classical
orthogonal polynomials, such as Chebyshev, Geronimus and Stieltjes polynomials, as
well as their adjacent polynomials, come into play. The universal cover of a regular
graph (resp. bigraph) is an infinite regular (resp. biregular) tree, with a well-studied
461
0195-6698 / 96 / 050461 1 17 $18.00 / 0 ÷ 1996 Academic Press Limited
462 W.-C. W. Li and P. Sole´

measure associated to its spectrum (cf. [19]). The universal cover of a regular
hypergraph, however, is not a universal cover in topological sense, it is a distance-
regular graph arising as a bipartite half of the infinite biregular tree; the measure
attached to its spectrum is computed in [8]. The relationship between bigraphs and
hypergraphs, and their eigenvalues, is explained in Section 4.1. After the analytic
preliminaries of Section 4.2, the bounds for bigraphs and hypergraphs spectra are
described in Section 4.3. The example of generalized polygons is treated in Section 4.4.
Finally, in Section 5 an application to number theory (modular forms) is given.
Part of the results of this paper were announced in [14]. Applications of the same
technique to coding theory can be found in [21].

2. PRELIMINARIES ON ORTHOGONAL POLYNOMIALS

2.1 . Orthogonal Polynomials

In this section we review some basic facts about orthogonal polynomials which will
be used in later sections. The reader is referred to [24] for details.
The basic measure we deal with is the Sato – Tate measure
2
m (x ) 5 41 2 x 2 dx
π
supported on the interval [21, 1]. Here dx denotes the Lebesgue measure on the real
line. The orthogonal polynomials with respect to m are known as the Chebychev
polynomials of the second kind, given by
sin ((n 1 1)θ )
PS jπ
D
n
Un (x ) 5 Un (cos θ ) 5 5 2n x 2 cos ,
sin θ j 51 n11
where x 5 cos θ . Hence U0(x ) 5 1 , U1(x ) 5 2x , and for n > 2 , Un (x ) is a polynomial of
degree n satisfying the recursive relation
Un (x ) 5 2xUn21(x ) 2 Un22(x ).
Other measures relevant to us are quotients of m (x ) by a real polynomial r (x ) of
degree at most 2, which is positive on the interval [21, 1]. Orthonormal polynomials
with respect to such a measure
m (x ) 2 41 2 x 2
… (x ) 5 5 dx
r (x ) π r (x )
are called the Bernstein – Szego¨ polynomials, which we now recall.
First write
r (cos θ ) 5 uh (eiθ )u2
for some complex polynomial h of the same degree as r . Denote by c (θ ) and s (θ ) the
real and imaginary parts of h (eiθ). The following result is extracted from Theorem 2.6
of [24].

THEOREM 1. With the aboy e notation , the polynomials p 0(x ) 5 1 , and , for n > 1 ,
sin((n 1 1)θ ) cos((n 1 1)θ )
pn (x ) 5 pn (cos θ ) 5 c (θ ) 2 s (θ ) , x 5 cos θ ,
sin θ sin θ
form a family of orthogonal polynomials with respect to … (x ).
 Spectra of graphs and orthogonal polynomials 463

Easily derived from the above theorem is the following special case, which will be
used repeatedly in this paper.

COROLLARY 1. With the same notation as aboy e , if h (x ) 5 a 1 bz 1 cz has real

2

coefficients a , b and c , then p0(x ) 5 1 , and p 1(x ) 5 aU1(x ) 1 bU0(x ) , and , for n > 2 ,
pn (x ) 5 aUn (x ) 1 bUn21(x ) 1 cUn22(x )
constitute a family of orthogonal polynomials with respect to … .

It is a general property of orthogonal polynomials pn (x ) with respect to a distribution

of … that pn (x ) has n distinct real roots, which are contained in the support of … , and
the roots of pn (x ) are separated by the roots of pn21(x ) [24, Theorem 3.3.1].

2.2. Christoffel Numbers

Let db be a measure supported within the interval [a , b ] , and let h pn j be a family of
orthogonal polynomials with respect to db . Given n > 1 , arrange the roots of pn (x ) in
increasing order:
x1 , x 2 , ? ? ? , xn .
The Christoffel numbers associated to n and db are defined as

E H(x 2px()xp)9(x)J db ,
b 2
n
ci :5 for i 5 1 , 2 , . . . , n.
a i n

These numbers are instrumental for Gauss – Jacobi mechanical quadrature. They occur
in this paper because of the celebrated Chebychev – Markov – Stieltjes inequalities. See
[24, Theorem 3.41.1] for a proof and other properties of Christoffel numbers.

THEOREM 2. (CMS inequality). With the aboy e notation , we hay e

E E O c ,E O c ,? ? ,E Oc
x1 x2 k 21 xk k xn n
0< db , c 1 , db , c 1 1 c 2 , ? ? ? , i db , i db < i
a a i 51 a i 51 a i51

5 E db .
b

We note the following corollary, which is essentially due to Bannai [1]. Let dg denote
another measure supported within [a , b ] such that the first t moments of the two
measures coincide:

E x db 5 E x dg
b b
i i
for i 5 1 , . . . , t.
a a

Set

r5 Ft 12 1G .
COROLLARY 2. Let C be the maximum of the Christoffel numbers c1 , . . . , cr
associated to r and db . Then , for x P [a , b ] , we hay e

UE db 2 E dg U < 2C.
x x

a a
464 W.-C. W. Li and P. Sole´

PROOF. In view of the CMS inequality, we have, for a < x < x 2 ,

E db < E
x x2
0< db , c1 1 c 2 < 2C
a a

and, for xk21 < x < xk , with 3 < k < r ,

E E db < E
xk21 x xk
c 1 1 ? ? ? 1 ck22 , db < db < c 1 1 ? ? ? 1 ck .
a a a

Since the moments of order up to t determine the orthogonal polynomials (up to a

constant multiple) up to degree r , the same inequality holds with db replaced by dg .
Hence the two integrals differ by at most 2C. h

3. SPECTRA OF GRAPHS

3.1 . Measures and Orthogonal Polynomials

The universal cover of a connected k -regular graph is the k -regular homogeneous

tree 7 , which is endowed with the measure

k 44q 2 x 2
da (x ) 5 dx ,
2π k 2 2 x 2

supported on its spectrum [224q , 24q] (cf., for instance, [19]). Here q 5 k 2 1 . Up to
a constant multiple, the measure da (24q x ) has the form

m (x )
… (x ) 5 .
k 2 4qx 2
2

Thus, r (x ) 5 k 2 2 4qx 2 , from which we find that h (x ) 5 q 2 z 2 . In view of Corollary 1,

we are led to define the degree n Geronimus polynomial as

Gn (x ) 5 qUn (x ) 2 Un22(x ) for n > 2 ,

G1(x ) 5 qU1(x ) , G0(x ) 5 1.

They form a family of orthogonal polynomials with respect to da (24q x ). These

polynomials are discussed in more detail in [20].
Another measure which will be used is

k 44q 2 x 2
(k 2 x ) da 5 dx .
2π k 1 x

Again, by a linear change of variable, the above measure can be transformed as a

constant multiple of m (x ) / r (x ) , with r (x ) 5 k 1 24q x. A straightforward calculation
yields h (z ) 5 4q 1 z . By Corollary 1, the polynomials

An ( y ) 5 4q Un ( y ) 1 Un21( y ) for n > 1 , and A0(x ) 5 1

form a family orthogonal with respect to (k 2 x ) da . Denote by

a 1 , a 2 , ? ? ? , an
 Spectra of graphs and orthogonal polynomials 465

the n distinct roots of An (x ) arranged in increasing order. By comparing the roots of Un

and Un21 we obtain an estimate for the roots of An :

cos Sjnπ D , a n 2j 11 , cos Sn j1π 1D, 1 < j < n. (1)

The third measure concerning us is

k 44q 2 x 2
(k 1 x ) da 5 dx .
2π k 2 x
Define the degree n polynomials
Bn ( y ) 5 4q Un ( y ) 2 Un21( y ) for n > 1 , and B 0(x ) 5 1 .
An argument similar to the above shows that the family hBn j is orthogonal to
m (x ) / r (x ) with r (x ) 5 k 2 24q x , which, up to a constant multiple, comes from
(k 1 x ) da (x ) by a linear change of variable. Arrange the n distinct roots of Bn in
increasing order:
b 1 , b 2 , ? ? ? , bn .
Then they satisfy

cos S( jn111)1π D , b n 2j , cos Sjnπ D, 0 < j < n 2 1. (2)

3.2 . Bounds on Extremal Non -triy ial Eigeny alues

For the remainder of Section 3, for a k -regular, connected, undirected graph G on y
vertices. The spectrum of G is, by definition, the eigenvalues of its adjacency matrix.
They are known [2] to be real and to satisfy
k 5 l 1 . l 2 > ? ? ? > l y > 2k.
Furthermore, ly 5 2k if G is bipartite, in which case l is an eigenvalue if 2l is. The
eigenvalues other than k and 2k are said to be non-trivial. Denote by g the girth of G ,
which is the length of a shortest cycle in G . The aim of this section is to give a lower
bound of the largest non-trivial eigenvalue and an upper bound of the smallest
non-trivial eigenvalue of G . The results here improve, and on some occasions correct,
those in [20].
First we recall some results established in [20]. For convenience, write q for k 2 1 .
The spectrum of G defines a measure m G by

mG 5
1
y
Od ,
l
l

where d l is the Dirac measure supported at l , and l runs through the spectrum of G .
Thus m G is a measure supported within the interval [2k , k ] , the value of which at any
function f on [2k , k ] is equal to

mG ( f ) 5
1 y
O
f (l i ).
y i51
As shown in [20], path counting in G yields, for an integer m 5 0 , 1 , . . . , g 2 1 ,
1 y m
n i51
Oli 5 E 24q

224q
x m da . (3)
466 W.-C. W. Li and P. Sole´

In other words, the measure m G attached to G agrees with the measure da attached to
its universal cover, the homogeneous tree 7 , on polynomials of degree less than g.
For » ,h P h0 , 1j we define the following variations of the measures m G and da ,
respectively:
m »G,h (x ) 5 (k 2 x )» (k 1 x )hm G (x ) ,
da » ,h (x ) 5 (k 2 x )» (k 1 x )h da (x ).
Let h p »n,hj be a family of orthogonal polynomials with respect to the measure da » ,h . As
discussed in previous sections, these polynomials may be chosen as p 1n,1(x ) 5
Un (x / (24q)) , p 0n,0(x ) 5 Gn (x / (24q)) , p 1n,0(x ) 5 An (x ) / (24q)) and p 0n,1(x ) 5
Bn (x / (2 q)). An immediate consequence of (3) is the following.
4

LEMMA 1. Let G be a k -regular graph of girth g. Then , for any polynomial f of degree
at most g 2 1 2 » 2 h , we hay e

E
m »G,h( f ) 5 da » ,h( f ) :5 f (x ) da » ,h(x ).

We will also need an estimate of the number of distinct eigenvalues of a graph with
known girth.

LEMMA 2. If s denotes the number of distinct eigeny alues of a graph with girth g , then
g 11
s> .
2

PROOF. This occurs because, for a graph with diameter d , its girth g is at most
2d 1 1 and it has at least d 1 1 distinct eigenvalues by [3, p. 12]. This fact was also
noted in [20]. h

Let
g 21 g 22
2 ,    
g
m9 5 n5 , m5 .
2 2
Our estimates are as follows.

THEOREM 3. Let G and n and m be as aboy e. Denote by an the largest zero of the
polynomial An . Suppose that n > 1. Then the second largest eigeny alue l 2 of G satisfies

H
l 2 > 24q max an , cos Sm π1 1DJ .
REMARK. Since

cos SπnD , a , cosSn 1π 1D

n

by (1), the second term is larger when the girth g is even (in which case n 5 m ) , while
the first term is larger for odd g (in which case n 5 m 1 1).

PROOF. Suppose otherwise. Then either l 2 , 24q a n or l 2 , 24q cos[π / (m 1 1)].

Define (» , h ) 5 (1 , 0) , f 5 p 1n,0 and h (x ) 5 f (x ) / (x 2 24q an ) in the first case, and
(» , h ) 5 (1 , 1) , f 5 p 1m,1 and h (x ) 5 f (x ) / hx 2 24q cos[π / (m 1 1)]j in the second case.
 Spectra of graphs and orthogonal polynomials 467

The degree of fh is at most g 2 1 2 » 2 h as seen from the definition of n and m. On the

other hand, f is orthogonal to polynomials of lower degree, in particular h , with respect
to da » ,h ; hence we obtain, by Lemma 1,
m »G,h( fh ) 5 da » ,h( fh ) 5 0.
It then follows from the assumption on l 2 and the definition of m »G,h that fh , and hence
f , vanish at all eigenvalues of G , except possibly at k , for the first case, and at k and 2k
for the second case. This in turn implies that the number s of distinct eigenvalues of G
is at most n in the first case, and m 1 1 in the second case. Consequently, s < g / 2 in
both cases, contradicting Lemma 2. h

THEOREM 4. Let m 9 , n and m be as aboy e. Denote by g 1 , a 1 and b 1 the smallest root

of Gm9 , An and Bn , respectiy ely . Then :
(i) if G is not bipartite , then its smallest non -triy ial eigeny alue l y satisfies
ly < 24q minhg1 , a1j;
(ii) if G is bipartite , then its smallest non -triy ial eigeny alue l y 21 satisfies

H
ly 21 < 24q min b 1 , 2cos Sm π1 1DJ .
PROOF. The argument is similar to the previous proof, with the following choices
of (» , h ) , f and h. When G is not bipartite, define (» , h ) 5 (0 , 0) , f 5 p 0n,0 and
h (x ) 5 f (x ) / (x 2 24q g 1) if l y . 24q g 1; and (» , h ) 5 (1 , 0) , f 5 p 1n,0 and h (x ) 5
f (x ) / (x 2 24q a 1) if ly , 24q a 1 . When G is bipartite, define (» , h ) 5 (0 , 1) , f 5
p 0n,1 , and h (x ) 5 f (x ) / (x 2 24q b1) if ly 21 . 24q b 1; and (» , h ) 5 (1 , 1) , f 5 p 1m,1 and
h (x ) 5 f (x ) / hx 1 24q cos[π / (m 1 1)]j if l y 21 . 224q cos[π / (m 1 1)]. h

REMARK. From (2), we obtain that

2cos Sn 1π 1D , b , 2cosSπnD ;
1

hence b1 , 2cos[π / (m 1 1)] if g is odd, and b 1 . 2cos[π / (m 1 1)] if g is even.

An immediate consequence of the above theorem is as follows.

COROLLARY 3. Giy en the aboy e notation , the smallest eigeny alue of G satisfies

ly , 224q cos Sn 1π 1D .
PROOF. It follows from the definition of Gm9 , that g 1 , 2cos[π / (m 9 1 1)] , while (1)
gives a1 , 2cos[π / (n 1 1)]; hence the result. h

Concerning the behavior of non-trivial eigenvalues of connected k -regular graphs X ,

the celebrated Alon – Boppana theorem [17] says that the lim inf of the largest
non-trivial eigenvalue of X is at least 24q as the size of X tends to infinity. However,
the smallest non-trivial eigenvalue of X does not necessarily get close to or below
224q as the size of X tends to infinity, as seen from the fact that the line graph of a
regular graph has smallest eigenvalue 22. Nonetheless, the above theorem shows that
if the girth of X also tends to infinity, then the desired result holds.
468 W.-C. W. Li and P. Sole´

COROLLARY 4. Let hXr j be a family of connected k -regular graphs , the girth of which
approaches infinity as r tends to infinity. Then the lim sup of the smallest non -triy ial
eigeny alue of Xr is at most 224q as r 5 ` .

We conclude this subsection by a bound on the subdominant eigeny alue :

L 5 maxhul i u: ul i u , k j.
Note that if G is bipartite, then L 5 l 2 5 2ly 21.

THEOREM 5. With the same notation as before , we hay e the following :

(i) if G is not bipartite , then

H
L > 24q max an , cos Sm π1 1D, 2a , 2g J ;
1 1

(ii) if G is bipartite , then

L > 24q max an , cos H Sm π1 1D, 2b J. 1

3.3 . Biggs Graphs

The number y of a k -regular graph of girth g satisfies the inequality:
(i) for g odd
y > 1 1 k 1 k (k 2 1) 1 ? ? ? 1 k (k 2 1)(g23)/2 ,
(ii) for g even
y > 1 1 k 1 k (k 2 1) 1 ? ? ? 1 k (k 2 1)(g 24)/2 1 (k 2 1)(g /2)21.
When the equality holds, such a graph is called a Biggs graph. (In [3] such a graph is
called a cage, while in [4] cage has a different definition. Here we call it Biggs graph to
avoid confusion.) In this case, its diameter d is related to its girth g as follows:
(i) for g odd,
g 5 2d 1 1;
(ii) for g even,
g 5 2d.
The spectrum of Biggs graph is computed from first principles in [3, p. 157]. We restate
this result in our language.

THEOREM 6 (Biggs ). Let G be a k -regular Biggs graph with girth g and diameter d .
Then :
(i) if g 5 2d , its spectrum consists of Úk and the d 2 1 zeros of Ud21( y / 24q);
(ii) if g 5 2d 1 1 , its spectrum consists of k and the d zeros of Ad ( y / 24q).

Consequently, the l 2 of a Biggs graph, if it exists (see [4] Section 6.9 for existence
results), meets the bounds of Theorem 3 with equality.

3.4 . The Oy erall Distribution of the Spectrum

In this section, we study the overall distribution of the eigenvalues of G . We adopt
the notation of Section 3.2. Define, for 224q < x < 24q ,

B » ,h(x ) 5
1
y
O (k 2 l) (k 1 l)
l<x
» h
 Spectra of graphs and orthogonal polynomials 469

and

E
x
k
A» ,h(x ) 5 (k 2 t )» 21(k 1 t )h 1144q 2 t 2 dt.
2π 224q

By Lemma 1, m »G,h agrees with da » ,h on polynomials up to g 2 1 2 » 2 h . This implies

that m »G,h and da » ,h share the same orthogonal polynomials up to degree

r (» , h ) 5 Fg 2 »2 2 hG .
Hence, by Theorem 2, B » ,h(x ) changes values as x moves from one zero of p »r(,h» ,h ) to an
adjacent zero. This means that there is an eigenvalue l of G between two consecutive
zeros of p »r(,h» ,h ). We summarize this discussion in the following theorem.

THEOREM 7. With the aboy e notation , we hay e that between any two consecutiy e
zeros of p »r(,h» ,h ) there lies an eigeny alue of G.

Among the polynomials occurring in the above theorem, we know the roots of
p 1r(1
,0
,1)(x ) 5 Um (x / (24q)) explicitly; they are 24q cos[ jπ / (m 1 1)] , for 1 < j < m.
Here, as before, m 5 (g 2 2) / 2. These roots partition the real line into m 1 1
intervals, and, by Theorems 3, 4 and 7, there is at least one non-trivial eigenvalue of G
in each interval.
The accumulated distribution A0 ,0(x ) was explicitly computed by McKay in [18,
Theorem 1.1], where one also finds the estimate
24» 4q
uB 0 ,0(x ) 2 A0 ,0(x )u , .
π 2(g 1 2)
In view of Theorem 2, one can bound the difference B » ,h(x ) 2 A» ,h(x ) using the
Christoffel numbers associated to r (» , h ) and da » ,h . We exhibit one such bound where
the Christoffel numbers are known.

THEOREM 8. Let m 5 (a 2 2) / 2 as before. For x P [2k , k ] , we hay e

4kq
uB 1 ,1(x ) 2 A1 ,1(x )u < .
m11

PROOF. We apply Corollary 2 with db 5 da 1 ,1 , dg 5 m 1G,1 and r 5 m. The Christoffel

numbers associated to m and m arise from the Chebyshev polynomial Um ; they are
computed in [24, p. 353]:

π
m11
sin2
jπ
m 11
, S D for j 5 1 , . . . , m.

This in turn gives the Christoffel numbers associated to m and da 1 ,1 as

2kq
m 11
sin2
jπ
m11
, S D
which is at most 2kq / (m 1 1). h
1 ,1
Observe that the closed form of A (x ) can be easily computed.
470 W.-C. W. Li and P. Sole´

4. SPECTRA OF HYPERGRAPHS AND BIGRAPHS

4.1 . Hypergraphs and Bigraphs

A hypergraph H consists of a set V of hypery ertices and a set E of hyperedges such
that each hyperedge is a non-empty set of certain hypervertices and the union of sets in
E is V. Here hypervertices are all distinct, but hyperedges may repeat, and
hypervertices contained in a hyperedge may repeat. A hypervertex y in V is incident to
a hyperedge e in E if y is an element of e. A hypergraph is said to be (k , l )-regular if
every hypervertex is incident to k hyperedges and every hyperedge is incident to l
hypervertices, counting multiplicity. Denote such a hypergraph by Hk ,l. Typical
examples of regular hypergraphs are designs. Given a hypergraph H , it has a dual
hypergraph H * , the set of hypervertices of which is the set of hyperedges of H , and the
hyperedges en of which are parametrized by the hypervertices y of H such that ey is the
set of the hyperedges of H containing y . The reader is referred to [2] for more details
on hypergraphs.
A bipartite graph is called a (k , l )-regular bigraph, denoted by Bk ,l , if all vertices in
one colour class have k neighbours, while all vertices in the other colour class have l
neighbours. The incidence graph of a (k , l )-regular hypergraph H is a (k , l )-regular
bigraph, called the associated bigraph of H. Thus, H and H * have the same associated
bigraphs.
Two hypervertices of H are adjacent if they are incident to a common hyperedge.
Denote by A(H ) and A(B ) the adjacency matrices of H and B , respectively. (Given
two distinct hypervertices y ,y 9 of H , the y y 9 entry of A(H ) is the number of
hyperedges in H containing both y and y 9; the diagonal entries of A(H ) are zero.) As
A(H ) is symmetric, it is the adjacency matrix of a graph * , possibly with multiple
edges, which is simply a bipartite half of B. (This is because the number of hyperedges
containing both y and y 9 is also the number of paths from y to y 9 in B of length 2.)
Thus * and * * are the two bipartite halves of B , and they do not have multiple edges
iff B does not contain loops of size 4.
Write M 5 M (V , E ) for the incidence matrix of H. Assume that H is (k , l )-regular.
Then the adjacency matrixes A(H ) , A(H *) and A(B ) are related as follows:

S M0 M0 D ,
A(B ) 5 t

SM0M D 5S
A(H ) 1 kI
D
t
0 V 0
A(B )2 5 .
t
MM 0 A(H *) 1 lIE
Here IV and IE denote the identity matrices with rows and columns parametrized by V
and E , respectively. Let P (x ) , P *(x ) and Q (x ) denote the characteristic polynomials of
the matrices A(H ) , A(H *) and A(B )2 respectively. From the preceding matrix relation
we deduce that
Q (x ) 5 P (x 2 k )P *(x 2 l ). (3)
By [5, p. 61], the characteristic polynomials P (x ) and P *(x ) satisfy
x uV uP *(x 2 l ) 5 x uE uP (x 2 k ) , (4)
which gives the connection between the spectra of H and H *. As Q (x ) has
non-negative roots, we obtain immediately from (3) that the eigenvalues of H and H *
are at least 2k and 2l , respectively. Furthermore, we see from (3) that the eigenvalues
of B are the square roots of the eigenvalues of H plus k , and the eigenvalues of H *
 Spectra of graphs and orthogonal polynomials 471

plus l. In particular, in the case that k and l are unequal, comparing the powers of x in
both sides of (4) yields what we call the oby ious eigenvalue 2k of H with density
1 2 k / l or 2l of H * with density 1 2 l / k , depending upon whether k , l or k . l. Using
(3) we see then that B has the oby ious eigenvalue 0 with density uk 2 l u / (k 1 l ). The
remaining eigenvalues (which may possibly overlap with the preceding ones) are called
non -oby ious. In general, any information concerning the spectrum of one of the three
graphs will immediately yield results for the other two.
Here we discuss bounds for eigenvalues of H and of B. The largest eigenvalue of H is
k (l 2 1) , which is the trivial eigenvalue. Similar to the Alon – Boppana bound for
regular graphs, it was shown in [8] that the second largest eigenvalue l 2(H ) of H has
the following lower bound.

THEOREM 9. For (k , l )-regular hypergraphs H , one has

lim inf l 2(H ) > l 2 2 1 24(k 2 1)(l 2 1)
as the number of hypery ertices in H tends to infinity.

Since any (k , l )-regular bigraph B is the associated bigraph for some (k , l )-regular
hypergraph, we see that the trivial eigenvalues of B are 4kl and 24kl , which bound
the remaining eigenvalues of B. The above theorem translates as follows.

THEOREM 10. Among the (k , l )-regular graphs B , one has

lim inf l 2(B ) > 4k 2 1 1 4l 2 1
as the number of y ertices in B tends to infinity.

Since the eigenvalues of B are symmetric with respect to zero, it suffices to study the
square of its non-obvious spectrum, which then relates to the non-obvious specturm of
H in a simple way, as discussed above.

4.2 . Measures and Orthogonal Polynomials

The universal cover of a (k , l )-regular graph is the infinite (k , l )-regular bipartite tree
7k ,l. The square of its spectrum and the associated measure were computed in [10].
The measure consists of two parts: the discrete part, which occurs when k and l are
unequal, reflects the obvious eigenvalue zero of any (k , l )-regular bigraph; and the
continuous part is given by
kl dx
dc (x ) 5 42 (x 2 k 2 l 1 2 2 24q)(x 2 k 2 l 1 2 1 24q) ,
π (k 1 l )x (kl 2 x )
supported on the interval [k 1 l 2 2 2 24q , k 1 l 2 2 1 24q]. Here q 5 (k 2 1)(l 2 1).
Under the change of variable
x 2k 1l 12
y5 ,
24q
we may rewrite dc (x ) as a non-zero constant multiple of the measure m ( y ) / p ( y ) , with
r ( y ) 5 (k 1 l 2 2 1 24q y )((k 2 1)(l 2 1) 1 1 2 24q y ).
This yields, with the same notation as in Section 2.1,
h (z ) 5 (4l 2 1 1 4k 2 1 z )(4q 2 z ).
472 W.-C. W. Li and P. Sole´

In view of Corollary 1, we are led to define the following family of polynomials, which
play the same role as Geronimus polynomials:
H0(x ) 5 1 , H1(x ) 5 (l 2 1)4k 2 1 U1(x ) 1 (k 2 2)4l 2 1 ,
and, for n > 2 ,
Hn (x ) 5 (l 2 1)4k 2 1 Un (x ) 1 (k 2 2)4l 2 1 Un21(x ) 1 24k 2 1 Un22(x ).
Then hHn ((x 2 k 2 l 1 2) / 24q)j is orthogonal with respect to dc (x ).
These polynomials have appeared implicitly in the study of generalized polygons of
parameters (s , t ). See [4, eq. (19) p. 201], with the notations h 5 eiθ , s 5 k 2 1 , t 5 l 2 1 ,
st 5 q and cos(θ ) there corresponding to our x. They are also obtained in [22, Theorem
5.2] from the P -polynomials of the point scheme of generalized polygons by a limiting
process. It is easy to check by using the relations
Tj (x ) 5 1–2 (Uj (x ) 2 Uj22(x )) , xUj21(x ) 5 1–2 (Uj (x ) 1 Uj22(x ))
that in the notations of [22] we have that rj (x ) 5 4k 2 1 Hj (x ) , again with the dictionary
s 5 k 2 1 , t 5 l 2 1 and st 5 q.
Another measure on 7 k,l which will be used is dg (x ) 5 (kl 2 x ) dc (x ). It turns out
that the continued fraction expansion of the moment generating function associated to
this measure was already computed by Stieltjes in 1894 [23]. The denominator of the
measure is x , and with the preceding change of variable we obtain
r ( y ) 5 (k 1 l 2 2 1 2qy ) ,
with the associated polynomial h being h (x ) 5 4k 2 1 1 z 4l 2 1 . Applying Corollary 1,
we obtain a family of polynomials, called the Stieltjes polynomials, which are
orthogonal with respect to dg (x 2 k 1 l 1 2) / 24q):
S0(x ) 5 1 ,
and
Sn (x ) 5 4k 2 1 Un (x ) 1 4l 2 1 Un21(x ) , n > 1.

4.3 . Bounds on Eigeny alues of Bigraphs and Hypergraphs

Fix a (k , l )-regular bigraph B. Analogous to what we did for regular graphs, to B we
attach the measure

mB 5
1
uB u l
dl , O
where l runs through the square of the non-obvious eigenvalues of B and uB u denotes
the number of vertices in B. The girth of B is an even integer 2g . By comparing the
measures m B and dc as well as their variations, in a similar manner to what we did in
Section 3.2, we arrive at the following estimates of the non-trivial eigenvalues of B. Put
m 9 5 g / 2 , n 5 (g 2 1) / 2 and m 5 (g 2 2) / 2 , as before.

THEOREM 11. Let B , m 9 , n and m be as aboy e. Denote by sn the largest root of Sn

and by s1 and h1 the smallest roots of Sn and Hm9 , respectiy ely. Suppose that n > 1 . Then
the second largest eigeny alue l 2(B ) of B satisfies

l 2(B )2 > k 1 l 2 2 1 24q max sn , cos H Sm π1 1DJ

 Spectra of graphs and orthogonal polynomials 473

and the smallest non -negatiy e non -oby ious eigeny alue l 9(B ) satisfies
l 9(B )2 < k 1 l 2 2 1 24q minhh 1 , s1j.

When k 5 l , the graph B is k -regular and bipartite (its eigenvalues were discussed in
Section 3); hence the above theorem is interesting for the case k ? l.
The above theorem yields an estimate for the eigenvalues of a (k , l )-regular
hypergraph H for which B is the associated bigraph. We define the girth of H to be g ,
half of the girth of B. Then we have the following.

THEOREM 12. Let H be a (k , l )-regular hypergraph with girth g . Let m 9 , n , m , sn , s 1

and h1 be as aboy e. Then the second largest eigeny alue l 2(H ) of H satisfies

H
l 2(H ) > l 2 2 1 24q max sn , cos Sm π1 1DJ
and the smallest non -negatiy e non -oby ious eigeny alue l 9(H ) satisfies
l 9(H ) < l 2 2 1 24q minhh 1 , s1j.

From the spectral viewpoint (cf. Theorems 10, 11 and the continuous spectrum of the
universal cover of (k , l )-regular bigraphs), we propose to call a (k , l )-regular bigraph B
a Ramanujan bigraph if any non-trivial non-obvious eigenvalue l of B satisfies
u4k 2 1 2 4l 2 1u < ul u < 4k 2 1 1 4l 2 1 .

This definition coincides with the one given in [11], which arises from zeta-function
considerations. In [11], the concept of a weak Ramanujan bigraph is also introduced,
which simply means that 0 is not a non-obvious eigenvalue of the bigraph. In the same
vein, a (k , l )-regular hypergraph H is called a Ramanujan hypergraph if any non-trivial
non-obvious eigenvalue l of H satisfies
ul 2 l 1 2u < 24(k 2 1)(l 2 1).

Then H is a Ramanujan hypergraph if the associated bigraph B is Ramanujan. Note

that in the case k ? l , a Ramanujan (k , l )-regular hypergraph has its smallest
eigenvalue greater than 2k. Explicit and systematic constructions of Ramanujan graphs
are known; see [14], [15] and papers referred to therein for details. It would be
interesting and highly desirable to construct Ramanujan hypergraphs; they may have
important applications to computational complexity.

4.4 . Generalized Polygons

A generalized n -gon of parameters (s , t ) is a (t 1 1 , s 1 1)-regular bigraph (with the two
vertex sets viewed as sets of ‘points’ and ‘lines’, respectively) with diameter n and girth
2n. The reader is referred to [4] for more details and properties of such graphs. As in
the case of Bigg’s graphs, the eigenvalues of these graphs are known (cf. [4, p. 201]),
and they meet the bound given in the above theorem with equality.

THEOREM 13. Let B be a generalized n -gon of parameters (s , t ) with the point graph
H , which is a (t 1 1 , s 1 1)-regular hypergraph. Let d denote the diameter of the
hypergraph.
(i) if n 5 2d is ey en , then the spectrum of H consists of s (t 1 1) , 2t 2 1 , and the d 2 1
zeros of Ud21[( y 2 s 1 1) / 24st].
474 W.-C. W. Li and P. Sole´

(ii) if n 5 2d 1 1 is odd , then s 5 t and the spectrum of H consists of s (t 1 1) and the d

zeros of Sd [( y 2 s 1 1) / 2s ].

In particular, a generalized n -gon with n odd is a Ramanujan graph, which is also a

Ramanujan hypergraph. As discussed in [4, Table 6.5], this happens only for the case
n 5 3 , with the 3-gon being the incidence graph of a projective plane.
In general, a (k , l )-regular hypergraph with girth g has the number of hypervertices y
satisfying the Kuich and Sauer bound [12]:
(i) for g odd

O
(g 23)/2
y > 1 1 k (l 2 1) (k 2 1)i (l 2 1)i ;
i 50

(ii) for g even,

O (k 2 1) (l 2 1) .
g /221
y >l i i

i 50

Similar to Biggs graphs, the hypergraphs arising from generalized n -gons meet the
above bounds with equality.

4.5 . The Oy erall Distribution of Spectra of Hypergraphs and Bigraphs

We keep the same notation as in the previous section. Using the same argument as in
Section 3.4, we can show that between any two consecutive roots of Hm9((x 2 k 1 l 1
2) / 24q) there lies a square of some eigenvalue of B , and the same is true between any
two consecutive roots of Sn ((x 2 k 1 l 1 2) / 24q) and of Um ((x 2 k 2 l 1 2) / 24q). The
corresponding statement for a hypergraph is as follows.

THEOREM 14. Let H be a (k , l )-regular hypergraph with girth g. Let m 9 , n and m be

as in the prey ious theorem . Then there lies an eigeny alue of H between any two
consecutiy e roots of Hm9((x 2 l 1 2) / 24q) , Sn ((x 2 l 1 2) / 24q) and Um ((x 2 l 1 2)
/ 24q) , respectiy ely.

To a (k , l )-regular hypergraph H we attach the measure

mH 5
1
uV u
Od ,
l
l

where l runs through the non-obvious eigenvalues of H , and uV u denotes the number
of hypervertices of H. It is supported on [2k (l 2 1) , k (l 2 1)]. As shown in Theorem 4
of [8], for any infinite family of (k , l )-regular hypergraphs the girth of which tends to
infinity, the sequence of the attached measures converges weakly to the measure
k 1l
df (x ) 5 dc (x 1 k )
l
supported on the interval [l 2 2 2 24q , l 2 2 1 24q]; hence it plays the role of the
continuous part of the measure of the ‘universal cover’ of (k , l )-regular hypergraphs. In
fact, df (x ) is the measure attached to one of the bipartite halves, denoted by $k ,l , of
the tree 7k ,l. Note also that it reduces to the measure da (x ) when l 5 2 .
We summarize below the universal covers, measures and orthogonal polynomials
used in this paper for regular graphs, bigraphs and hypergraphs.
 Spectra of graphs and orthogonal polynomials 475

I. For k -regular graphs:

(1) universal cover 7k ;
(2) measures da (x ) , (k 2 x ) da (x ) and (k 1 x ) da (x );
(3) support [224q , 24q] , where q 5 k 2 1;
(4) corresponding orthogonal polynomials Gn (x / 24q) (Geronimus polynomials),
An (x / 24q) and Bn (x / 24q).
II. For (k , l )-regular bigraphs:
(1) universal cover 7k ,l;
(2) measures (of the square of the spectrum) dc (x ) and (kl 2 x ) dc (x );
(3) support [k 1 l 2 2 2 24q , k 1 l 2 2 1 24q] , where q 5 (k 2 1)(l 2 1);
(4) corresponding orthogonal polynomials Hn (x 2 k 2 l 1 2) / 24q) and Sn ((x 2 k 2 l 1 2)
/ 24q) (Stieltjes polynomials).
III. For (k , l )-regular hypergraphs:
(1) universal cover $k,l;
(2) measures df (x ) and (k (l 2 1) 2 x ) df (x );
(3) support [l 2 2 2 24q , l 2 2 1 24q] , where q 5 (k 2 1)(l 2 1);
(4) corresponding orthogonal polynomials Hn ((x 2 l 1 2) / 24q) and Sn ((x 2 l 1 2)
/ 24q) (Stieltjes polynomials).
Extend df (x ) to [2k (l 2 1) , k (l 2 1)] , so that it is zero outside its support. Just as we
did for regular graphs in Section 3.4, we may study the cumulative distribution of m H as
well as its variations and compare them with those of df (x ). Here we state one of such
estimates for the hypergraph H. Define the distributions, for x P [2k (l 2 1) , k (l 2 1)] ,
as

E (x ) 5
1
uV u l<x
O
(k (l 2 1) 2 l )(k 1 l ) ,

where l runs through the non-obvious eigenvalues of H , and

E
x
k
F (x ) 5 44q 2 (t 2 l 1 2)2 dt.
2π l 22224q

An argument similar to the proof of Theorem 8 yields the following.

THEOREM 15. Let H be a (k , l )-regular hypergraph with girth g . Let m 5 (g 2 2) / 2

as before. Then , for x P [2k (l 2 1) , k (l 2 1)] , we hay e
4kq
uE (x ) 2 F (x )u < .
m11

5. AN APPLICATION TO NUMBER THEORY

In the paper [17], an infinite family of Ramanujan graphs hX p ,qj was constructed,
where p and q are odd primes congruent to 1 mod 4. The degree of these graphs is
p 1 1 , and their size of order Ω(g 3). The girth of the graph hX p ,qj was shown ([17,
Theorem 3.4]) to be at least g p ,q , where

SpqD 5 21,
5
4 logp q 2 logp 4 if
g p ,q 5
if S D 5 1 .
(5)
p
2 logp q
q
On the other hand, the functions on the vertices of the graph hX p ,qj can be interpreted
as modular forms of weight 2 for the congruence subgroup G (16q 2) , and the non-trivial
eigenvalues of hX p ,qj are among the eigenvalues of the Hecke operator Tp acting on
476 W.-C. W. Li and P. Sole´

cusp forms of weight 2 for the group G (16q 2). Hence the resutls of Sections 3.2 and 3.4
give us information on the distribution of eigenvalues of the Hecke operator Tp on such
forms, and consequently on any space containing such forms. In particular, we have the
following.

THEOREM 16. Let p and q be two odd primes congruent to 1 mod 4. Let g 5 g p ,q be
defined by (5) and let m 5 (g 2 2) / 2. Then the m y alues 24p cos[iπ / (m 1 1)] ,
1 < j < m , diy ide the intery al [2242 , 24p] into m 1 1 sub -intery als , each containing at
least one eigeny alue of the Hecke operator Tp on the space of cusp forms of weight 2 for
any congruence group containing G (16q 2). Furthermore , the discrepancy between the
distribution B 1 ,1 attached to the graph X p ,q and the Sato – Tate distribution A1 ,1 (using the
notation of Section 3.4) is bounded by
4( p 1 1)4p
uB1 ,1(x ) 2 A1 ,1(x )u < .
m11

ACKNOWLEDGEMENTS
We thank the anonymous referee for helpful remarks. The Research of the first
author was supported in part by NSA grants MDA904-92-H-3054 and MDA904-95-H-
1006. The research of the second author was supported in part by a joint CNRS-NSF
grant. The second author is on leave of absence from CNRS-I3S, France, and would
like to thank the Mathematics Department of Pennsylvania State University for its
hospitality.

REFERENCES
1. E. Bannai, On the weight distribution of spherical t -designs, Europ. J. Combin. , 1 (1980), 19 – 26.
2. C. Berge, Hypergraphes , Gauthier – Villars, Paris, 1987.
3. N. Biggs, Algebraic Graph Theory , Cambridge University Press, Cambridge, 1974.
4. A. E. Brouwer, A. M. Cohen and A. Neumaier, Distance -regular graphs , Springer-Verlag, Berlin, 1989.
5. D. M. Cvetkovic´ , M. Doob and H. Sachs, Spectra of Graphs , Academic Press, London, 1979.
6. F. R. K. Chung, Diameters and eigenvalues, J. Am. Math. Soc. , 2(2) (1989), 187 – 196.
7. C. Delorme and P. Sole´ , Diameter, covering number, covering radius, and eigenvalues, Europ. J.
Combin. , 12 (1991), 95 – 108.
8. K. Feng and W.-C. W. Li, Spectra of hypergraphs and applications, J. of Number Theory , to appear.
9. J. Friedman, On the second eigenvalue and random walks in random regular d -graphs, Technical Report
CS-TR-172-88, Princeton University, 1988.
10. C. D. Godsil and B. Mohar, Walk generating functions and spectral measures of infinite graphs, Lin. Alg.
Applics , 107 (1988), 191 – 206.
11. K. Hashimoto, Zeta functions of finite graphs and representations of p -adic groups. In: Automorphic
Forms and Geometry of Arithmetic Varieties , K. Hashimoto and Y. Namikawa (eds), Advanced Studies
In Pure Mathematics 15, Academic Press, New York (1989), pp. 211 – 280.
12. W. Kuich and N. Sauer, On the existence of certain minimial regular n -systems with given girth, In:
Proofs and Techniques in Graph Theory , F. Harary (ed.), Academic Press, New York, 1963, pp. 93 – 101.
13. V. I. Levenshtein, Designs as maximal codes in polynomial metric spaces, Acta Appl. Math. , 29 (1992),
1 – 82.
14. W.-C. W. Li, A survey of Ramanujan graphs, Proceedings of AGCT -4 , Luminy 93 , Arithmetic , Geometry
and Coding Theory , R. Pellikaan, M. Perret, S. Vladut, eds, de Gruyter (1996).
15. W.-C. W. Li, Number-theoretic constructions of Ramanujan graphs, Aste´ ristique , (1995), Columbia
University Number Theory Seminar, NY 1992, Aste´ risque , 228 (1995), SMF, 101 – 120.
16. R. A. Liebler, Tactical configurations and their generic ring, Europ. J. Combin. , 9 (1988), 581 – 592.
17. A. Lubotzky, R. Phillips and P. Sarnak, Ramanujan graphs, Combinatorica , 8 (1988), 261 – 277.
18. B. D. McKay, The expected eigenvalue distribution of a large regular graph, Lin. Alg. Applics , 40
(1981), 203 – 216.
19. B. Mohar and W. Woess, A survey on spectra of infinite graphs, Bull. Lond. Math. Soc. , 21 (1989),
209 – 234.
 Spectra of graphs and orthogonal polynomials 477

20. P. Sole´ , The second eigenvalue of regular graphs of given girth, J. Combin. Theory , Ser. B. , 56(2) (1992),
239 – 249.
21. P. Sole´ , Packing radius, covering radius, and dual distance, IEEE Trans. Inform. Theory , 41 (1995),
268 – 272.
22. D. Stanton, Generalized n -gons and Chebychev polynomials, J. Combin. Theory , Ser. A , 34 (1983),
15 – 27.
23. T. J. Stieltjes, Recherches sur les fractions continues, Oeuy res Comple` tes , vol. 2, pp. 405 – 566, Ann. Fac.
Sci. Toulouse , 9 (1894), 1 – 47.
24. G. Szego¨ , Orthogonal Polynomials , AMS Colloquium Publications 23, fourth edition, 1975, reprinted
1985.
Receiy ed 20 March 1995 and in rey ised form 6 June 1995

WEN-CH’ING WINNIE LI
Department of Mathematics ,
Pennsyly ania State Uniy ersity ,
Uniy ersity Partk , PA 16802 , U .S.A.

PATRICK SOLE´
Macquarie Uniy ersity ,
School of MCPE ,
NSW 2109 , Australia

View publication stats