Table of Contents

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

Organisers

Ross Kang and Jean-Sébastien Sereni

Workshop dates

8-12 March 2021

Confirmed participants

(updated 8 March, registration closed)

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

Open problems

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

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

Talks

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.

Research results