Table of Contents
2021 Session 2 : Entropy Compression and Related Methods
Lovász local lemma, entropy compression, stochastic local search algorithms, cluster expansion, hard-core model, exponentially many hypergraph colourings, and related topics/techniques.
8-12 March 2021
(updated 8 March, registration closed)
- Ross Kang (organiser)
- Jean-Sébastien Sereni (organiser)
- Louis Esperet*
- Oscar Treffers
- Mike Molloy*
- Guillem Perarnau
- Matthieu Rosenfeld*
- Ewan Davies*
- Anton Bernshteyn*
- Annika Heckel
- François Pirot
- Stijn Cambie
- Eoin Hurley
- Jan Volec
- Carla Groenland
- Vilhelm Agdur
- Alberto Espuny Díaz
- Lena Yuditsky
- Tomáš Kaiser
- Jakub Przybyło
- Shoham Letzter
- Matthew Wales
- Freddie Illingworth
- Xing Shi Cai
- Wouter Cames van Batenburg
- David Harris
To apply for participation in this workshop, please send an email to the organisers. By signing up, one commits to an active involvement in the meeting's activities, roughly 3 or 4 hours per day. There may be a cap on participants, but note that all talks will be open to any interested individuals.
Registration deadline: 2 March (closed).
Submit open problems related to the themes of the workshop (generously interpreted) by email to the organisers. One main aim of the workshop is, in small groups, to work on and solve these!
Deadline: 5 March (closed).
Schedule (all times European)
1. Monday, 8 March a. Two talks (14:30 Molloy, 15:30 Esperet) b. Open problem session/group formation (16:30-18:00) 2. Tuesday, 9 March a. Open working sessions b. Coffee break in wonder (15:15) c. Progress reports (15:45) 3. Wednesday, 10 March a. Three talks (14:30 Bernshteyn, 15:30 Rosenfeld, 16:30 Davies) b. Social event (20:00) 4. Thursday, 11 March a. Open working sessions b. Coffee break in wonder (15:15) c. Progress reports (15:45) 5. Friday, 12 March a. Progress reports/Remaining open problems (15:00-16:30) b. Closing drinks 6. Sunday 14 March a. Eat pie in wonder (20:00)
For the open working sessions, we plan/suggest (based on the suggestion of Fiona Skerman) group contact moments once in the morning, once in the early afternoon, and optionally if needed once in the evening to coordinate across the Atlantic.
To preserve the interactive nature of the meeting, no talks are to be recorded and we encourage attendees to keep their cameras on.
For Monday's talks, use https://us02web.zoom.us/j/86719578298?pwd=MStpZ2lIaEVjMEJXTDlYbVRlT0dSQT09 (Meeting ID: 867 1957 8298 Passcode: Lovasz); for Wednesday's talks, use https://us02web.zoom.us/j/83019879074?pwd=Z2VuQjNRbFgxdkhNOW5pVVVWMDk2dz09 (Meeting ID: 830 1987 9074 Passcode: Moser).
Mike Molloy: The chromatic number of triangle-free graphs
Here's an application of the entropy compression technique: If G is a triangle-free graph with maximum degree D, then the chromatic number of G is at most (1+o(1)) D/ log D. I will discuss this result, focusing mainly on the thought process which led to the proof and on hurdles I'd like to see overcome which might enable extending the proof technique to other applications.
Louis Esperet: Entropy compression for coloring problems
I'll talk about the (pre)-history of entropy compression, from Moser-Tardos to improved bounds on coloring problems using tools from analytic combinatorics.
Anton Bernshteyn: Constructive versions of the Lovász Local Lemma
The breakthrough work of Moser and Tardos on the algorithmic Lovász Local Lemma has led to the emergence of a wide array of constructive versions of the LLL in a variety of different settings, ranging from computability theory to measure theory to distributed algorithms. In this talk, I will survey some of these developments.
Matthieu Rosenfeld: A simple counting argument
Abstract: I will present a simple counting argument that was used by myself and by Wanless and Wood. This argument seems to provide slightly better bounds than entropy compression (for less work) in many cases. I will present two simple applications and try to clarify some connections between this argument and the LLL and entropy compression.
Ewan Davies: The cluster expansion, Lovász local lemma and algorithms
The local lemma and its variants are such convenient statements that it is tempting to use them as a black box. We will shine a light into this box and survey deep connections between the cluster expansion from statistical physics, the local lemma, algorithms for finding objects guaranteed by the local lemma, and see how entropy compression emerges. The main goal of this talk is to act as a navigation aid for the extensive and diverse literature on these topics.
- Groenland, Kaiser, Treffers, Wales. Graphs of low average degree without independent transversals. https://arxiv.org/abs/2106.15175
- Davies, Illingworth. The $\chi$-Ramsey problem for triangle-free graphs. https://arxiv.org/abs/2107.12288
- Hurley, Pirot. A first moment proof of the Johansson-Molloy theorem. https://arxiv.org/abs/2109.15215