Preface

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

vii