###
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: