Contact Info
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
Title: Chromatic structure in locally sparse graphs
Speaker: | Ross Kang |
Affiliation: | Radboud University Nijmegen |
Zoom: | Please email Emma Watson |
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.
Combinatorics & Optimization
University of Waterloo
Waterloo, Ontario
Canada N2L 3G1
Phone: 519-888-4567, ext 33038
PDF files require Adobe Acrobat Reader.
The University of Waterloo acknowledges that much of our work takes place on the traditional territory of the Neutral, Anishinaabeg and Haudenosaunee peoples. Our main campus is situated on the Haldimand Tract, the land granted to the Six Nations that includes six miles on each side of the Grand River. Our active work toward reconciliation takes place across our campuses through research, learning, teaching, and community building, and is centralized within our Office of Indigenous Relations.