Preface
This monograp h i s an intertwine d tal e o f eigenvalues an d thei r us e i n unlock -
ing a thousand secret s abou t graphs . Th e storie s will b e tol d ho w the spectru m
reveals fundamenta l propertie s o f a graph , ho w spectra l grap h theor y link s th e
discrete univers e t o th e continuou s on e throug h geometric , analyti c an d algebrai c
techniques, an d how , throug h eigenvalues , theor y an d application s i n Communica -
tions an d Compute r scienc e com e togethe r i n symbioti c harmony . Sinc e spectra l
graph theor y ha s bee n evolvin g very rapidly , th e abov e goal s ca n onl y b e partiall y
fulfilled here . Fo r example , mor e advance d materia l o n th e hea t kerne l wil l b e
treated i n a later publication ,
This boo k i s base d o n te n lecture s give n a t th e CBM S Worksho p o n spectra l
graph theor y i n Jun e 1994 a t Fresn o Stat e University . Additiona l chapter s wer e
included o n subgraph s wit h boundar y condition s an d o n advance d technique s fo r
random walks . I wish t o thank S.T . Ya u fo r introducin g m e to powerfu l idea s fro m
spectral geometry . Th e las t fe w chapter s ar e mainl y base d o n ou r collaborativ e
work o n geometr y o f graphs . Specia l thank s ar e du e t o Ro n Graham , withou t
whose encouragement this book would never have existed. I n the course of writing, I
have greatly benefitte d fro m numerou s suggestion s an d valuabl e comments of Noga
Alon, And y Woldar , Feli x Lazebnik , Davi d Gillman , Elizabet h Wilmer , Prasa d
Tetali an d Her b Wilf . I woul d als o lik e t o acknowledg e th e suppor t o f Nationa l
Science Foundatio n throug h Gran t No . DM S 95-04834 .
Like al l authors , I woul d hop e tha t thes e lectur e note s ar e completel y error -
free. However , t o b e realistic , I pla n t o maintai n a n errat a lis t o n m y hom e pag e
http://www.math.upenn.edu/~chung. Naturally , I wil l b e gratefu l fo r an y contri -
bution t o thi s list .
Fan Chun g
September, 1996
XI
Previous Page Next Page