Minicourse 1: A short course in spectral graph theory and distance-regular graphs
Lecturer: Sebastian Cioaba, University of Delaware, USA.
Abstract: In this short course, I will present the basics of spectral graph theory and distance-regular graphs. The presentation will be self-contained and after a short recap of linear algebra, we will describe the most common used matrices in spectral graph theory (adjacency matrix, Laplacian, signed adjacency matrix, normalized Laplacian, signless Laplacian), their eigenvalues and their basic properties. We will present some older and some recent applications of eigenvalues and spectral methods. For distance-regular graphs, we will describe the basic combinatorial and linear algebraic theory and some connections between distance-regular graphs and approximation algorithms in theoretical computer science and the problem of embedding graphs into Euclidean spaces with least distortion.
Minicourse 2: Container method in combinatorics
Lecturer: Rajko Nenadov, University of Auckland, New Zealand
Abstract: The container method is a powerful technique for enumerating independent sets in graphs and hypergraphs enjoying a sufficiently uniform edge distribution. Very briefly, the method exploits a clustering phenomenon exhibited by independent sets in such hypergraphs. These (hyper)graphs often arise in practice, making the container method widely applicable. The method frequently provides additional structural properties of independent sets, which are crucial for some applications.
Graph containers were pioneered by Kleitman and Winston in their seminal work on enumerating graphs without a cycle of length 4. The method was further refined by several researchers, most notably by Sapozhenko in the context of enumerating independent sets in regular graphs and sum-free sets. This line of research culminated in the work of Balogh, Morris, and Samotij, and, independently, Saxton and Thomason, who generalised the method to hypergraphs.
We begin with the basic graph container method and discuss classic applications, such as counting C4-free graphs and sum-free sets. We then move on to hypergraph containers and count the number of triangle-free graphs. From there, we explore numerous surprising applications of the hypergraph containers. These include the typical structure of triangle-free graphs, the Ramsey theorem for random graphs, and a construction of points in the Euclidean plane with no four on a line, where every sufficiently large set contains a collinear triple. We conclude this series of lectures by going over a recent short proof of hypergraph containers by Nenadov and Pham.
