GRAPH THEORY
CONTENTS I INTRODUCTION AND BACKGROUND INTRODUCTION GRAPHS MATRICES FOR GRAPHS A SPREADSHEET AN OPERATOR A QUADRATIC FORM SPECTRAL THEORY SOME EXAMPLES PATHS HIGHLIGHTS SPECTRAL GRAPH DRAWING GRAPH ISOMORPHISM PLATONIC SOLIDS THE FIEDLER VALUE BOUNDING EIGENVALUES PLANAR GRAPHS RANDOM WALKS ON GRAPHS EXPANDERS APPROXIMATIONS OF GRAPHS 1510 SOLVING EQUATIONS IN AND COMPUTING EIGENVALUES OF LAPLACIANS EXERCISES EIGENVALUES AND OPTIMIZATION: THE COURANT-FISCHER THEOREM THE FIRST PROOF PROOF OF THE SPECTRAL THEOREM NOTES EXERCISE THE LAPLACIAN AND GRAPH DRAWING THE LAPLACIAN MATRIX DRAWING WITH LAPLACIAN EIGENVALUES ADJACENCY MATRICES, EIGENVALUE INTERLACING, AND THE PERRON-FROBENIUS THEOREM THE ADJACENCY MATRIX EIGENVALUE INTERLACING WILF’S THEOREM PERRON-FROBENIUS THEORY FOR SYMMETRIC MATRICES COMPARING GRAPHS OVERVIEW THE LOEWNER ORDER THE PATH INEQUALITY BOUNDING ?2 OF A PATH GRAPH THE COMPLETE BINARY TREE THE WEIGHTED PATH II THE ZOO OF GRAPHS FUNDAMENTAL GRAPHS THE COMPLETE GRAPH THE STAR GRAPHS PRODUCTS OF GRAPHS THE HYPERCUBE BOUNDS ON ?2 BY TEST VECTORS THE RING GRAPH THE PATH GRAPH CAYLEY GRAPHS PALEY GRAPHS EIGENVALUES OF THE PALEY GRAPHS GENERALIZING HYPERCUBES A RANDOM SET OF GENERATORS CONCLUSION NON-ABELIAN GROUPS EIGENVECTORS OF CAYLEY GRAPHS OF ABELIAN GROUPS EIGENVALUES OF RANDOM GRAPHS TRANSFORMATION AND MOMENTS THE EXTREME EIGENVALUES EXPECTATION OF THE TRACE OF A POWER THE NUMBER OF WALKS STRONGLY REGULAR GRAPHS DE?NITIONS THE PENTAGON LATTICE GRAPHS LATIN SQUARE GRAPHS THE EIGENVALUES OF STRONGLY REGULAR GRAPHS REGULAR GRAPHS WITH THREE EIGENVALUES INTEGRALITY OF THE EIGENVALUES THE EIGENSPACES OF STRONGLY REGULAR GRAPHS 910 TRIANGULAR GRAPHS 911 PALEY GRAPHS 912 TWO-DISTANCE POINT SETS III PHYSICAL METAPHORS 10 RANDOM WALKS ON GRAPHS 101 RANDOM WALKS 102 SPECTRA OF WALK MATRICES 103 THE STABLE DISTRIBUTION 104 THE RATE OF CONVERGENCE 105 RELATION TO THE NORMALIZED LAPLACIAN 106 EXAMPLES 1061 THE PATH 1062 THE COMPLETE BINARY TREE 1063 THE DUMBBELL 1064 THE BOLAS GRAPH 107 DI?USION 108 FINAL NOTES 11 WALKS, SPRINGS, AND RESISTOR NETWORKS 111 OVERVIEW 112 HARMONIC FUNCTIONS 113 RANDOM WALKS ON GRAPHS 114 SPRING NETWORKS 115 LAPLACIAN LINEAR EQUATIONS 116 ENERGY 117 RESISTOR NETWORKS 118 SOLVING FOR CURRENTS 119 EXERCISE 12 E?ECTIVE RESISTANCE AND SCHUR COMPLEMENTS 121 ELECTRICAL FLOWS AND E?ECTIVE RESISTANCE 122 E?ECTIVE RESISTANCE THROUGH ENERGY MINIMIZATION 123 MONOTONICITY 124 EXAMPLES: SERIES AND PARALLEL 125 EQUIVALENT NETWORKS, ELIMINATION, AND SCHUR COMPLEMENTS 1251 IN MATRIX FORM BY ENERGY 126 ELIMINATING MANY VERTICES 127 AN INTERPRETATION OF GAUSSIAN ELIMINATION 128 E?ECTIVE RESISTANCE IS A DISTANCE 13 RANDOM SPANNING TREES 131 INTRODUCTION 132 DETERMINANTS 133 CHARACTERISTIC POLYNOMIALS 134 THE MATRIX TREE THEOREM 135 LEVERAGE SCORES AND MARGINAL PROBABILITIES 14 APPROXIMATING E?ECTIVE RESISTANCES 141 REPRESENTING E?ECTIVE RESISTANCES 142 COMPUTING E?ECTIVE RESISTANCES 143 PROPERTIES OF GAUSSIAN RANDOM VARIABLES 144 PROOF OF JOHNSON-LINDENSTRAUSS 15 TUTTE’S THEOREM: HOW TO DRAW A GRAPH 151 3-CONNECTED, PLANAR GRAPHS 152 STRICTLY CONVEX POLYGONS 153 POSSIBLE DEGENERACIES 154 ALL FACES ARE CONVEX 155 NOTES 16 THE LOV`ASZ - SIMONOVITS APPROACH TO RANDOM WALKS 161 INTRODUCTION 162 DE?NITIONS AND ELEMENTARY OBSERVATIONS 163 WARM UP 164 THE PROOF 165 ANDERSEN’S PROOF OF CHEEGER’S INEQUALITY 17 MONOTONICITY AND ITS FAILURES 171 DISCLAIMER 172 OVERVIEW 173 E?ECTIVE SPRING CONSTANTS 174 MONOTONICITY 175 E?ECTIVE RESISTANCE 176 EXAMPLES 177 BREAKDOWN OF MONOTONICITY 178 TRA?C NETWORKS 179 BRAES’S PARADOX 1710THE PRICE OF ANARCHY 1711NASH OPTIMUM 1712SOCIAL OPTIMUM 18 DYNAMIC AND NONLINEAR NETWORKS 181 DISCLAIMER 182 OVERVIEW 183 NON-LINEAR NETWORKS 184 ENERGY 185 USES IN SEMI-SUPERVISED LEARNING 186 DUAL ENERGY 187 THERMISTOR NETWORKS 188 LOW TEMPERATURES IV SPECTRA AND GRAPH STRUCTURE 19 INDEPENDENT SETS AND COLORING 191 OVERVIEW 192 GRAPH COLORING AND INDEPENDENT SETS 193 HO?MAN’S BOUND 194 APPLICATION TO PALEY GRAPHS 195 LOWER BOUND ON THE CHROMATIC NUMBER 196 PROOFS FOR HO?MAN’S LOWER BOUND ON CHROMATIC NUMBER 20 GRAPH PARTITIONING 202 CONDUCTANCE 203 THE NORMALIZED LAPLACIAN 204 NOTES 21 CHEEGER’S INEQUALITY 211 CHEEGER’S INEQUALITY 22 LOCAL GRAPH CLUSTERING 221 THE ALGORITHM 222 GOOD CHOICES FOR A 223 BOUNDING THE D-NORM 224 BOUNDING THE GENERALIZED RAYLEIGH QUOTIENT 225 ROUNDING 226 NOTES 23 SPECTRAL PARTITIONING IN A STOCHASTIC BLOCK MODEL 231 THE PERTURBATION APPROACH 232 PERTURBATION THEORY FOR EIGENVECTORS 233 PARTITIONING 234 PROOF OF THE DAVIS-KAHAN THEOREM 235 FURTHER READING 24 NODAL DOMAINS 241 OVERVIEW 242 SYLVERTER’S LAW OF INTERIA 243 WEIGHTED TREES 244 MORE LINEAR ALGEBRA 2441 THE PERRON-FROBENIUS THEOREM FOR LAPLACIANS 2442 EIGENVALUE INTERLACING 245 FIEDLER’S NODAL DOMAIN THEOREM 25 THE SECOND EIGENVALUE OF PLANAR GRAPHS 251 OVERVIEW 252 GEOMETRIC EMBEDDINGS 253 THE CENTER OF GRAVITY 254 FURTHER PROGRESS 26 PLANAR GRAPHS 2, THE COLIN DE VERDI`ERE NUMBER 261 INTRODUCTION 262 COLIN DE VERDI`ERE INVARIANT 263 POLYTOPES AND PLANAR GRAPHS 264 THE COLIN DE VERDI`ERE MATRIX 265 MINORS OF PLANAR GRAPHS V EXPANDER GRAPHS 27 PROPERTIES OF EXPANDER GRAPHS 271 OVERVIEW 272 EXPANDERS AS APPROXIMATIONS OF THE COMPLETE GRAPH 273 QUASI-RANDOM PROPERTIES OF EXPANDERS 274 VERTEX EXPANSION 275 HOW WELL CAN A GRAPH APPROXIMATE THE COMPLETE GRAPH? 276 OPEN PROBLEMS 28 A BRIEF INTRODUCTION TO CODING THEORY 281 CODING 282 NOTATION 283 CONNECTION WITH GENERALIZED HYPERCUBES 284 HAMMING CODES 285 TERMINOLOGY AND LINEAR CODES 286 RANDOM LINEAR CODES 287 REED-SOLOMON CODES 288 CAUTION 29 EXPANDER CODES 291 BIPARTITE EXPANDER GRAPHS 292 BUILDING CODES 293 ENCODING 294 MINIMUM DISTANCE 295 DECODING 296 HISTORICAL NOTES 30 A SIMPLE CONSTRUCTION OF EXPANDER GRAPHS 301 OVERVIEW 302 SQUARING GRAPHS 303 THE RELATIVE SPECTRAL GAP 304 LINE GRAPHS 305 THE SPECTRUM OF THE LINE GRAPH 306 APPROXIMATIONS OF LINE GRAPHS 307 THE WHOLE CONSTRUCTION 308 BETTER CONSTRUCTIONS 31 PSRGS VIA RANDOM WALKS ON GRAPHS 311 OVERVIEW 312 WHY STUDY PSRGS? 313 EXPANDER GRAPHS 314 TODAY’S APPLICATION : REPEATING AN EXPERIMENT 315 THE RANDOM WALK GENERATOR 316 FORMALIZING THE PROBLEM 317 MATRIX NORMS 318 THE NORM OF DXW 319 CONCLUSION 3110NOTES VI ALGORITHMS 32 SPARSI?CATION BY RANDOM SAMPLING 321 OVERVIEW 322 SPARSI?CATION 323 MATRIX CHERNO?BOUNDS 324 THE KEY TRANSFORMATION 325 THE PROBABILITIES 326 THE ANALYSIS 327 OPEN PROBLEM 33 LINEAR SIZED SPARSI?ERS 331 OVERVIEW 332 TURNING EDGES INTO VECTORS 333 THE MAIN THEOREM 334 RANK-1 UPDATES 335 BARRIER FUNCTION ARGUMENTS 336 BARRIER FUNCTION UPDATES 337 THE INDUCTIVE ARGUMENT 338 PROGRESS AND OPEN PROBLEMS 34 ITERATIVE SOLVERS FOR LINEAR EQUATIONS 341 WHY ITERATIVE METHODS? 342 FIRST-ORDER RICHARDSON ITERATION 343 EXPANDERS 344 THE NORM OF THE RESIDUAL 345 A POLYNOMIAL APPROXIMATION OF THE INVERSE 346 BETTER POLYNOMIALS 347 CHEBYSHEV POLYNOMIALS 348 PROOF OF THEOREM 3461 349 LAPLACIAN SYSTEMS 3410WARNING 35 THE CONJUGATE GRADIENT AND DIAMETER 351 THE MATRIX NORM 352 APPLICATION: APPROXIMATING FIEDLER VECTORS 353 OPTIMALITY IN THE A-NORM 354 HOW GOOD IS CG? 355 LAPLACIAN SYSTEMS, AGAIN 356 BOUNDS ON THE DIAMETER 36 PRECONDITIONING LAPLACIANS 361 APPROXIMATE SOLUTIONS 362 ITERATIVE RE?NEMENT 363 ITERATIVE METHODS IN THE MATRIX NORM 364 PRECONDITIONED ITERATIVE METHODS 365 PRECONDITIONING BY TREES 366 IMPROVING THE BOUND ON THE RUNNING TIME 367 FURTHER IMPROVEMENTS 368 QUESTIONS 37 AUGMENTED SPANNING TREE PRECONDITIONERS 371 RECURSION 372 HEAVY TREES 373 SAVING A LOG 38 FAST LAPLACIAN SOLVERS BY SPARSI?CATION 381 OVERVIEW 382 TODAY’S NOTION OF APPROXIMATION 383 THE IDEA 384 A SYMMETRIC EXPANSION 385 D AND A 386 SKETCH OF THE CONSTRUCTION 387 MAKING THE CONSTRUCTION E?CIENT 388 IMPROVEMENTS 39 TESTING ISOMORPHISM OF GRAPHS WITH DISTINCT EIGENVALUES 391 INTRODUCTION 392 GRAPH ISOMORPHISM 393 USING EIGENVALUES AND EIGENVECTORS 394 AN EASY CASE 395 ALL THE AUTOMORPHISMS 396 EQUIVALENCE CLASSES OF VERTICES 397 THE ?RST PARTITION 398 UNBALANCED VECTORS 399 THE STRUCTURE OF THE BALANCED CLASSES 3910ALGORITHMS 40 TESTING ISOMORPHISM OF STRONGLY REGULAR GRAPHS 401 INTRODUCTION 402 DE?NITIONS 403 PALEY GRAPHS AND THE PENTAGON 404 LATTICE GRAPHS 405 LATIN SQUARE GRAPHS 406 THE EIGENVALUES OF STRONGLY REGULAR GRAPHS 407 TESTING ISOMORPHISM BY INDIVIDUALIZATION AND RE?NEMENT 408 DISTINGUISHING SETS FOR STRONGLY REGULAR GRAPHS 409 NOTES VII INTERLACING FAMILIES 41 BIPARTITE RAMANUJAN GRAPHS 411 OVERVIEW 412 2-LIFTS 413 RANDOM 2-LIFTS 414 LAPLACIANIZED POLYNOMIALS 415 INTERLACING FAMILIES OF POLYNOMIALS 416 COMMON INTERLACINGS 417 REAL ROOTEDNESS 418 CONCLUSION 419 OVERVIEW ? D ?1 4111THE MATCHING POLYNOMIAL 4112PROPERTIES OF THE MATCHING POLYNOMIAL 4113THE PATH TREE 42 EXPECTED CHARACTERISTIC POLYNOMIALS 421 OVERVIEW 422 RANDOM SUMS OF GRAPHS 423 INTERLACING 424 SUMS OF POLYNOMIALS 425 RANDOM SWAPS 43 QUADRATURE FOR THE FINITE FREE CONVOLUTION 431 OVERVIEW 432 THE FINITE FREE CONVOLUTION 433 QUADRATURE 434 QUADRATURE BY INVARIANCE 435 STRUCTURE OF THE ORTHOGONAL GROUP 436 THE FORMULA 437 QUESTION 44 RAMANUJAN GRAPHS OF EVERY SIZE 441 OVERVIEW 442 THE APPROACH 443 INTERLACING FAMILIES OF POLYNOMIALS 444 ROOT BOUNDS FOR FINITE FREE CONVOLUTIONS 445 THE CALCULATION 446 SOME EXPLANATION OF THEOREM 4441 447 SOME THOUGHTS 45 MATCHING POLYNOMIALS OF GRAPHS 451 OVERVIEW 452 THE MATCHING POLYNOMIAL 453 PROPERTIES OF THE MATCHING POLYNOMIAL 454 THE PATH TREE 455 ROOT BOUNDS 46 BIPARTITE RAMANUJAN GRAPHS OF EVERY DEGREE 461 OVERVIEW 462 2-LIFTS 463 RANDOM 2-LIFTS