Spectral Graph Theory and Graph Partitioning

Abstract

5 Tightness of the Bounds * 20 5.1 Characters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 5.2 A Look Beyond . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.3 Cayley Graphs and Their Spectrum . . . . . . . . . . . . . . . . . . . 27 5.4 The Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 5.5 The Hypercube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29