Mathematics Seminar - Prof. Ross Kang

Title: Locally sparse graphs: combinatorics, probability & algorithms

Abstract:

The structure of triangle-free graphs has long played an influential role in the development of combinatorial mathematics. Both of the foundational results of Mantel (1907) and of Ramsey (1930) yield global structure from the local property of having no edges in any neighbourhood. About five years ago, I began to systematically explore this classic and well-studied area. This has led unexpectedly to some interesting fundamental questions and developments, particularly with respect to independent sets and colourings. I will give an overview of some of the history as well as discuss the focus of current/recent activities, with special emphasis on the probabilistic method and randomised algorithms.

This talk will include the presentation of a general framework for deriving global graph structure through local structure. This generalises and strengthens almost all of the main results in the area, including those of Ajtai, Komlós, Szemerédi (1981), Shearer (1983/1996), Johansson (1996), Alon (1996), Alon, Krivelevich, Sudakov (1999), Molloy (2019), Bernshteyn (2019), and Achlioptas, Iliopoulos, Sinclair (2019). It is built around a conceptually simple technique inspired by statistical physics --namely, a local analysis of the hard-core model-- as well as the suitable application of the Lovász local lemma or stochastic local search.

I will discuss joint work, variously, with Ewan Davies, Eoin Hurley, Rémi de Joannis de Verclos, François Pirot, and Jean-Sébastien Sereni.