Algebraic and probabilistic techniques in combinatorics

Bojan Mohar (Simon Fraser University)

Jan 1, 2024 — Apr 30, 2024

About the course

The course will provide an introduction to algebraic and probabilistic techniques in combinatorics and graph theory. The main topics included will be: Eigenvalues of graphs and their applications, probabilistic methods (first order, second order, Lovasz local lemma), Szemeredi regularity lemma. Recent discoveries like the proof of the Sensitivity conjecture, the use of eigenvalues for equiangular lines, etc., will be part of the course. '

Registration

This course is available for registration under the Western Dean's Agreement. To register, you must obtain the approval of the course instructor and you must complete the Western Dean's agreement form , using the details below. The completed form should be signed by your home institution department and school of graduate studies, then returned to the host institution of the course.

Enrollment Details

Course Name
Algebraic and probabilistic techniques in combinatorics
Date
Jan 1, 2024 — Apr 30, 2024
Course Number
MATH 800
Section Number
Section Code

Instructor(s)

For help with completing the Western Dean’s agreement form, please contact the graduate student program coordinator at your institution. For more information about the agreement, please see the Western Dean's Agreement website

Other Course Details

Lecture Times

  • Time: Tuesday 10:30-12:20 and Thursday 10:30-12:20
    • First day of classes: January 9
    • Reading break: February 20-25
    • Last day of classes: April 11

Delivery details

Note: This course is also offered through PIMS and WDA (Western Dean’s Agreement) as an online course. A Zoom link will be shared with registered students.

Course outline

Part I
  • Introduction (warmup application of graph eigenvalues)
  • Eigenvalue basics (including Perron-Frobenius Theorem)
  • Eigenvalue interlacing (bounds on the maximum clique and chromatic number)
  • Wilf’s Theorem, proof of sensitivity conjecture
  • Graph Laplacians (Matrix-tree Theorem, Cheeger inequality)
  • Random walks, effective resistance
  • Spectral sparsifiers
Part II
  • Random graphs, probabilistic method (including Lovasz local lemma)
  • Quasirandom graphs
  • Eigenvalues of random graphs (Wigner, Tao-Vu)
  • Regularity Lemma
  • Finding regular partitions
  • Random covers and Ramanujan graphs

Grading scheme:

  • Homework assignments 30%
  • Midterm 30%
  • Final exam 40%
2023-2024