Sparse Graphs Coalition

Lovász local lemma, entropy compression, stochastic local search algorithms, cluster expansion, hard-core model, exponentially many hypergraph colourings, and related topics/techniques.

Ross Kang and Jean-Sébastien Sereni

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

*denotes speaker

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).

Template: https://www.mimuw.edu.pl/~mp248287/opl-example.tgz

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).

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).

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.

I'll talk about the (pre)-history of entropy compression, from Moser-Tardos to improved bounds on coloring problems using tools from analytic combinatorics.

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.

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.

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 χ-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
• Hurley, Pirot. Uniformly Random Colourings of Sparse Graphs. https://arxiv.org/abs/2303.15367