Instructor:  Prof. Lincoln Lu

Office: LC 400I, Email: lu@math.sc.edu

Office hours: Tuesday & Thursday 1:00PM- 2:30PM & or by appointment.

Lecture time: Tuesday & Thursday 2:50PM- 4:05PM, LC 310

Credit Hours:  3

Prerequisite:  Some background in graph theory and linear algebra

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. We will study the eigenvalues of three classical matrices associated to the graphs: the adjacency matrix, the Combinatrorics Laplacian, and the normalized Combinatorial Laplacian, as well as the pagerank matrix used in the Google searching engine.

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. They will be able to read research papers and present results in the class. They will combine methods learned from this course and practice them at new problems. Students will demonstrate their problem-solving skills through homework, an exam, and a final project.

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

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 project 30%. The letter grade is assigned by the following table:

Grading Scale

Final project: Select one of the following papers to present at the classes:

1. H. Chuang, G.R. Omidi, Graphs with 3 distinct eigenvalues, Linear Algebra and its Applications, 2008.
2. Xiaodong Zhang, The Laplacian eigenvalues of graphs: a survey. in Linear Algebra Research Advances, Editor: Gerald D. Ling, pp. 201-228,2007 Nova Science Publishers, Inc.
3. E.R. van Dam and G.R. Omidi, Graphs whose normalized Laplacian has three eigenvalues , arxiv:1202.3027.
4. Aida Abiad, Willem H Haemers, Cospectral Graphs and Regular Orthogonal Matrices of Level 2, The Electronic Journal of Combinatorics, Volume 19, Issue 3 (2012), Paper #P13.
5. Linyuan Lu, Explicit Construction of Small Folkman Graphs, Siam Journal of Discrete Math, 21 No. 4 (2008), 1053-1060.
6. Chung, Graham, and Noga, Routing permutations on graphs via matchings SIAM J. Discrete Math. 7 (1994) 513--530.
7. Wei-Tian Li, Linyuan Lu, and Yiting Yang, Routing numbers of Cycles, Complete Bipartite Graphs, and Hypercubes, SIAM J. Discrete Math. 24, (2010), pp. 1482-1494.
8. Sven Reichard, Strongly regular graphs with the 7-vertex condition, J. Algebr Comb 41, (2015), 817-842.
9. R. Andersen, Fan Chung, and Kevin Lang, Using pagerank vectors to locally partition a graph Internet Mathematics, 4 (2007), 35--64.
10. AMIN COJA-OGHLAN, Graph Partitioning via Adaptive Spectral Techniques, Combinatorics, Probability and Computing, 19, pp 227-284.