Tutte Colloquium - Ross Kang

Title: Chromatic structure in locally sparse graphs

Abstract:

Efforts to understand the structure of triangle-free graphs have long played a central role in the development of combinatorial mathematics. Classic results of Mantel (1907), Ramsey (1930), Blanche Descartes (1948) produce global structure from the local property of having no edges in any neighbourhood. Despite the scrutiny it has sustained over the decades, study of this topic, and its close relatives, continues to uncover surprisingly basic challenges, insights and connections. I will give a brief overview of the history as well as the focus of current/recent momentum.

I will also highlight a recent, general framework for producing global structure from local structure. This generalises and strengthens a swathe of important results in the area, including those of Ajtai, Komlós, Szemerédi (1981), Shearer (1983/1996), Johansson (1996), Alon (1996), Alon, Krivelevich, Sudakov (1999), Bansal, Gupta, Guruganesh (2018), Bonamy, Kelly, Nelson, Postle (2018), Molloy (2019), Bernshteyn (2019), and Achlioptas, Iliopoulos, Sinclair (2019). The framework is built around a technique inspired by statistical physics –namely, a local analysis of the hard-core model– combined with the suitable application of the Lovász local lemma.

This is joint work with Ewan Davies, Rémi de Joannis de Verclos, François Pirot, Jean-Sébastien Sereni.