MATH/CSCI 4690/6690: Spectral Graph Theory

This is a somewhat flexibly-paced course on spectral graph theory taught in the “hybrid asynchronous” online format. This webpage will contain notes, reading assignments, homework assignments, short videos, and computer demonstrations. Since the course is asynchronous, there are no simultaneous Zoom sessions during course times. The course notes below represent everything that I’d say during a lecture. In theory, reading them (and talking with me during office hours) should contain just as much information as an in-person class.

In-person class sessions are optional and must be booked online in advance because of classroom capacity limits. Our assigned class space, Boyd 323, can only accommodate 16 of the 44 students registered for this class at any one time. For this reason, if you want to come to an in-person class, I need you to schedule online using this link. You can schedule your class attendance between 1 hour and two weeks in advance. 

Online office hours and one-on-one discussions can also be booked online. At the moment, the times are relatively limited, and I’m restricting it to 5 students at each discussion. But I will probably adjust as needed over the course of the semester. 

Our text for the course is the book draft by Dan Spielman, Spectral and Algebraic Graph Theory. There’s a wonderful video lecture by Spielman himself introducing the subject which I encourage you to watch if you’re thinking about whether to take the course. 

Graphs are a fascinating and fundamental object in mathematics and computer science, providing a convenient language for expressing everything from social networks to polymer structures. There are deep applications of graph theory in machine learning and knowledge representation, as well as classification, data science, and mathematical finance. In pure mathematics, graph theory interfaces with combinatorics, probability, and geometry as well as being a worthy subject in its own right. (See: four color theorem.)

This is a first course in graph theory (so you don’t need prior graph-theoretic experience to take the course), but we are going to focus on studying graphs via the spectrum (set of eigenvalues) of a matrix (the graph Laplacian). For that reason, MATH 3000 or MATH 3300 (or equivalent experience) are required prerequisites for this version of the course, as well as the usual prerequisite of MATH 3200.  If you don’t have any linear algebra experience, the best thing to do is sit this one out and take Graph Theory next spring when it’s planned to return to the usual treatment of the subject.

Computing will be an integral part of the course. In most cases, meaningful examples in spectral graph theory are simply too big to be evaluated by hand. (In particular, we’ll be doing a lot of finding eigenvalues and eigenvectors of matrices, which is really easy numerically and almost impossible to do by hand.) Our book provides some Jupyter notebooks and examples for those with a programming language of choice. Otherwise, I’ll mostly use Mathematica. UGA has a site license for Mathematica and you can get a copy for your laptop or home computer free of charge. I encourage you to work through some introductory material on Mathematica. If you want more Mathematica training, I recommend this online Wolfram U course. Some of the homework assignments and projects will require you to write Mathematica programs, and it’s really helpful to be able to use a computer to check your work.

Homework will be turned in via Gradescope. Please use course entry code V88J4N to add yourself to the class. Although this is a self-paced course, the due dates in Gradescope are the recommended schedule. Each Gradescope assignment has a due date and a late due date. There is no penalty for submitting homework by the late due date. However, we can’t accept or grade assignments after the late due date. It will help you pace yourself if you complete as many assignments as you can by the original due date. If you are not done, please turn in what you have by the late submission date. If you haven’t started on an assignment by the late due date, please move on to a later assignment and contact me– we can make arrangements regarding grading if needed. Please remember to select pages for each question in Gradescope, including problems for which you are not submitting any work (these should have a page with something like “No work submitted for 3.6” or something similar).

The course syllabus is available online here.

Course Evaluation.

The course will be evaluated 50% on homework assignments, 25% for the midterm exam and 25% for the final exam. The midterm exam will be an in-person open book exam on Thursday, March 18.  There are three options for the time– the usual in-class time (book as usual) and in the evening at 6-7:30pm or 7:30-9:00pm (use this booking link). (Remote proctoring arrangements can be made for students who need to be off campus.) You may bring up to 350 pages of paper (and/or any number of printed books), plus any calculator accepted for the math SAT. The final exam will take place at our scheduled time of Thursday, May 6, 3:30pm-6:30pm. (Again, remote proctoring options will be available for students who need to be off-campus.)

Course materials.

In this space will go links to my class notes and in-class problems for the course. The classes with computer demonstrations have Mathematica notebooks posted here. 

  1. Introduction. The diffusion operator.
    1. Reading: Spectral and Algebraic Graph Theory p. 1-4.
    2. Video: Diffusion operator computer demonstration.
    3. Mathematica notebook: Diffusion operator computer demonstration.
    4. Optional video: 3Blue1Brown “Essence of Linear Algebra”
      1. Vectors, What Even Are They?
      2. Linear combinations, basis and span.
      3. Linear transformations and matrices
      4. Matrix multiplication as composition
    5. Minihomework: Linear algebra review.
  2. Quadratic forms and the Graph Laplacian.
    1. Reading: Spectral and Algebraic Graph Theory p. 5-17.
    2. Video: Graph Laplacian computer demonstration.
    3. Mathematica notebook: Graph Laplacian computer demonstration.
    4. Minihomework: Elementary properties of the graph Laplacian
  3. Eigenvalues, eigenvectors and the Courant-Fischer theorem.
    1. Note: You’re usually supposed to look at the materials in the order they appear on this list. But this time, I recommend that you start with the video, then read the notes, and finally read the book chapter.
    2. Video: 3Blue1Brown “Essence of Linear Algebra”
      1. Eigenvalues and eigenvectors
    3. Reading: Spectral and Algebraic Graph Theory p. 21-26
    4. Minihomework: Linear algebra of eigenvalues and eigenvectors
  4. The Laplacian and Graph Drawing.
    1. Reading: Spectral and Algebraic Graph Theory, p. 27-31
    2. Minihomework: Isomorphisms and drawings
      This homework has a computational component. Below are some links for documentation that may be useful to you. Graphs are built in to Mathematica. If you’re using another language, you should be able to use iGraph.
      1. Optional: Wolfram U. Lesson on Graphs in Mathematica
        1. Kirchhoff matrix (another name for graph Laplacian)
        2. Eigensystem.
      2. Optional: iGraph open-source graph theory library
        1. laplacian
        2. scipy.linalg.eigvals
        3. scipy.linalg.eig
  5. Eigenvalue interlacing and the Perron-Frobenius theorem.
    1. Reading: Spectral and Algebraic Graph Theory, p. 32-38.
    2. Minihomework: Spectral graph coloring.
  6. Comparing graphs and the Loewner ordering.
    1. Reading: Spectral and Algebraic Graph Theory, p. 39-45.
    2. Minihomework: Comparing graphs.
  7. Eigenvalues and eigenvectors of some example graphs.
    1. Reading: Spectral and Algebraic Graph Theory, p. 47-51.
    2. Minihomework: Eigenvalues and Eigenvectors of Example Graphs.
  8. Path and Cycle graphs.
    1. Reading: Spectral and Algebraic Graph Theory, p. 51-54.
    2. Minihomework: Path and Cycle graphs.
  9. Cayley graphs and Paley graphs.
    1. Reading: Spectral and Algebraic Graph Theory, p. 55-58.
    2. (Not coming in Spring 2021 Course) Minihomework: The Paley graphs.
  10. Generalized hypercubes as approximations of Complete Graphs.
    1. Reading: Spectral and Algebraic Graph Theory, p. 58-62.
    2. (Not coming in Spring 2021 Course) Minihomework: Build your own Paley and generalized hypercube graphs.
  11. The Matrix-Tree Theorem
    1. Reading: Spectral and Algebraic Graph Theory, p. 110-114.
    2. (Not coming in Spring 2021 Course) Minihomework: The matrix-tree theorem and leverage probabilities

Material on this page is a work-for-hire produced for the University of Georgia.