In many ways, working on graph theory problems over the years has always
seemed lik e fu n an d games . Recently , throug h example s o f larg e spars e graph s i n
realistic networks, research i n graph theory ha s been forgin g ahea d int o an excitin g
new dimension. Grap h theory has emerged as a primary tool for detecting numerou s
hidden structures i n various information networks , including Internet graphs , socia l
networks, biologica l networks , o r mor e generally , an y grap h representin g relation s
in massiv e dat a sets .
How will we explain from first principles the universal and ubiquitous coherenc e
in the structur e o f these realisti c bu t comple x networks ? I n orde r t o analyz e thes e
large spars e graph s w e wil l nee d t o us e al l th e tool s a t ou r disposal , includin g
combinatorial, probabilisti c an d spectra l methods . Tim e an d again , w e have bee n
pushed beyon d th e limi t o f the existin g techniques an d hav e had t o create new an d
better tool s to b e abl e to analyz e thes e networks . Th e example s o f these network s
have led u s to focu s o n new, genera l an d powerfu l way s to loo k a t grap h theory . I n
the other direction, we hope that thes e new perspectives on graph theory contribut e
to a sound scientifi c foundatio n fo r ou r understanding o f the discret e network s tha t
permeate thi s informatio n age .
This boo k i s based o n te n lecture s give n a t th e CBMS Workshop on the Com-
binatorics of Large Sparse Graphs in Jun e 200 4 a t th e Californi a Stat e Universit y
at Sa n Marcos . Variou s portion s o f the twelv e chapter s her e ar e base d o n severa l
papers coauthore d wit h man y collaborators . Indeed , t o dea l wit h th e numerou s
leads i n such a n emergin g are a i t i s crucial t o hav e partners t o soun d ou t th e righ t
approaches, t o separat e wha t ca n b e rigorousl y prove d an d unde r wha t condition s
from wha t canno t b e proved , t o fac e seemingl y overwhelmin g obstacle s an d ye t
still gather enoug h energ y t o overcome one more challenge . Specia l thanks ar e du e
to ou r coauthors , includin g Bil l Aiello , Rei d Andersen , Davi d Galas , Gre g Dewey ,
Shirin Handjani , Dou g Jungreis , an d Va n Vu .
We ar e particularl y gratefu l t o Ros s Richardso n an d Rei d Anderse n fo r man y
beautiful illustration s i n th e boo k an d t o th e student s i n Math26 1 sprin g 200 4 a t
UCSD fo r takin g valuabl e lectur e notes . I n th e cours e o f writing, w e hav e greatl y
benefitted fro m discussion s with Alan Frieze, Joe Buhler and Herb Wilf. Mos t of all,
we are indebted t o Steve Butler an d Ro n Graha m fo r thei r thoughtfu l reading s an d
invaluable comments without whic h this book would no t hav e so swiftly converged .
Fan Chun g an d Lincol n Lu , Ma y 200 6
Previous Page Next Page