Simon Fraser University
Engaging the World

Course Outlines

Summer 2023 - MATH 895 G100

Reading (4)

Class Number: 2199

Delivery Method: In Person

Overview

  • Course Times + Location:

    Location: TBA

Description

COURSE DETAILS:

Topic: Expansion, Lifts, and Interlacing Families
Outline: This is an ambitious course aimed at understanding one of the great recent developments
in combinatorics, namely the Marcus-Spielman-Srivastava interlacing polynomial method and its application to prove the existence of bipartite Ramanujan graphs of all possible degrees.
In preparation for reading this paper we will take approximately 3 weeks to introduce each of the following three important topics in algebraic graph theory:
(1) The spectrum of the adjacency matrix and the matching polynomial. Spectrum of the adjacency matrix: structural connections and Cayley graphs. Matching polynomial: real rootedness and absolute bounds.
(2) Graph expansion, including connections to the second largest eigenvalue, mixing of random walks, the Alon-Boppana bound, and random constructions.
(3) Lifts of graphs and random lifts, including relationships to the spectrum, graph structure.
Finally, with this material in hand we will delve into the (first) masterpiece of Marcus-SpielmanSrivastava: Interlacing Families I: Bipartite Ramanujan Graphs of All Degrees. This paper is beautifully written and can be approached without much background, but the preceding investigation will establish the basic results on which this paper is based, and give the appropriate context to understand the main result.

Prerequisite: Graph theory and exposure to algebraic graph theory.

Grading

  • Assignments 60%
  • Final Project 40%

NOTES:

Course Structure and Grades: We will meet twice per week with the class beginning much like a standard class with lectures covering basic material. Later in the course students will take turns presenting material with each student giving at least two presentations during the course. There will be four (large) homework assignments given out during the course which students will be permitted to work on in groups. Each assignment will be worth 15% of the final grade. The remaining 40% of the grade will be based upon a final project.

Materials

MATERIALS + SUPPLIES:

References: We will use a variety of sources for this course. Spectral Graph Theory by Godsil and Royle will be a key resource for the first part. An online course given by Linial and Wigderson on graph expansion will be a key resource for the second part. The third part will call upon papers of Linial and Lov´asz. The final part will be the main paper for the course by Marcus, Spielman, and Srivastava.

REQUIRED READING NOTES:

Your personalized Course Material list, including digital and physical textbooks, are available through the SFU Bookstore website by simply entering your Computing ID at: shop.sfu.ca/course-materials/my-personalized-course-materials.

Graduate Studies Notes:

Important dates and deadlines for graduate students are found here: http://www.sfu.ca/dean-gradstudies/current/important_dates/guidelines.html. The deadline to drop a course with a 100% refund is the end of week 2. The deadline to drop with no notation on your transcript is the end of week 3.

Registrar Notes:

ACADEMIC INTEGRITY: YOUR WORK, YOUR SUCCESS

SFU’s Academic Integrity website http://www.sfu.ca/students/academicintegrity.html is filled with information on what is meant by academic dishonesty, where you can find resources to help with your studies and the consequences of cheating. Check out the site for more information and videos that help explain the issues in plain English.

Each student is responsible for his or her conduct as it affects the university community. Academic dishonesty, in whatever form, is ultimately destructive of the values of the university. Furthermore, it is unfair and discouraging to the majority of students who pursue their studies honestly. Scholarly integrity is required of all members of the university. http://www.sfu.ca/policies/gazette/student/s10-01.html

RELIGIOUS ACCOMMODATION

Students with a faith background who may need accommodations during the semester are encouraged to assess their needs as soon as possible and review the Multifaith religious accommodations website. The page outlines ways they begin working toward an accommodation and ensure solutions can be reached in a timely fashion.