Spectral Graph Theory
Math 778S
Spring 2009 Course Syllabus

Instructor:  Prof. Lincoln Lu

Office: LC 314E, Email: lu@math.sc.edu

Office hours: Monday & Wednesday 12:20PM- 1:20PM & Tuesday 2:00PM-3:30PM, or by appointment.

Lecture time: Monday & Wednesday & Friday 11:15AM- 12:05PM, LC 303B

Credit Hours:  3

Prerequisite:  A GRADE OF C OR HIGHER IN MATH 544 or 526

Textbook: Spectral Graph Theory, by Fan Chung Graham. Revised first four chapters are available online.

Overview: The stories will be told --- how the spectrum reveals fundamental properties of a graph, how spectral graph theory links the discrete universe to the continuous one through geometric, analytic and algebraic techniques, and how, through eigenvalues, theory and applications in communications and computer science come together in symbiotic harmony.... quoted from the preface of the textbook.

Learning Outcomes: Students will master concepts and compute spectra of graphs. Students can use spectra to deduce other graph properties. In particular, they can use spectral methods to analyse real-world graphs.

Subject Material:   We shall cover the selected material presented in the textbook and other supplemental marterial such as PageRanks.

Assessment:   The assessment consists of homeworks, an exam and a take-home final exam. Homeworks will normally be assigned every other week.

Grading: The breakup grades are homework 50%, midterm 20%, and final 30%.

Handouts: The supplement marterial and homeworks will be posted here.

  • Handout 0: examples of real-world graphs
  • Handout 1: basic linear algebra
  • Handout 2: basic graph theory
  • Handout 3: Eigenvalues of adjacency matrix
  • Homework 1: homework1.pdf
  • An applet of the Cartesian graph product
  • Homework 2: homework2.pdf
  • Handout 4: Laplacian Eigenvalues and Graph Projection
  • Supplemental reading marterial: Graphs with 3 distinct eigenvalues and Graphs with 3 distinct (combinatorial) Laplacian eigenvalues.
  • Explicit Construction of Small Folkman Graphs: paper, talk.
  • Routing permutations on graphs via matchings by Chung, Graham, and Noga, SIAM J. Discrete Math. 7 (1994) 513--530.
  • Page, Lawrence; Brin, Sergey; Motwani, Rajeev and Winograd, Terry (1999) The PageRank citation ranking: Bringing order to the Web
  • Haveliwala, Kamvar (1999) The second eigenvalue of the Google matrix
  • S Kamvar, T Haveliwala, G Golub (2003) Adaptive Methods for the Computation of PageRank
  • D Fogaras, B Racz (2004) Towards Scaling Fully Personalized PageRank
  • J Cho, S Roy, RE Adams (2005) Page quality: In search of an unbiased web ranking

    GCGRE - project

    Gamecock Google Ranking Experiment (GCGRE) is a class project to promote the PageRank of certain webpages using the methods learned in this class. Every particiated student has a web page containing a keyword (GCGRE) and link them to others' pages. Here are these GCGRE pages: