- Time: everyday Jan 19 to Jan 23, 2026, offline at IBS headquarter B332.
Online: 9:00-10:30am (Beijing), 10:00-11:30am (Seoul). - Zoom: 955 7502 7689, PW: 260119
This mini-course will serve as an introduction to cut problems in graphs and related topics. The course will begin by covering the basics of spectral graph theory, including the Alon–Boppana theorem and the expander mixing lemma. We will then introduce some fundamental tools in the field, such as the Goemans–Williamson algorithm, along with its applications to various types of max-cut problems in graphs and hypergraphs. Towards the end of the course, we will explore recent advancements in the area, which rely on more involved spectral properties of adjacency matrices.
- 1/19 Lecture 1: The max-cut problem, Edwards’ bound and the expander mixing lemma. Tablet note
- 1/20 Lecture 2: Alon-Boppana theorem and introduction to graph discrepancy. Tablet note
- 1/21 Lecture 3: Bollobás-Scott inverse relation between positive and negative discrepancy, and Goemans-Williamson method. Tablet note
- 1/22 Lecture 4: Optimal surplus for triangle-free graphs, and improved lower bounds for positive discrepancy of sparse graphs. Tablet note
- .1/23 Lecture 5: Lower bounds for the second largest eigenvalue and positive discrepancy when p < 1/2. Tablet note Reference list
