Differences

This shows you the differences between two versions of the page.

--- sessions:2021sessions:2021session2 [2021/03/02 20:34] – [Confirmed participants] ross.kang
+++ sessions:2021sessions:2021session2 [2023/09/22 15:12] (current) – [Organisers] ross.kang
@@ Line 2: / Line 2: @@
 Lovász local lemma, entropy compression, stochastic local search algorithms, cluster expansion, hard-core model, exponentially many hypergraph colourings, and related topics/techniques.
+==== Organisers ====
+[[https://staff.fnwi.uva.nl/j.r.kang/|Ross Kang]] and [[https://lbgi.fr/~sereni/|Jean-Sébastien Sereni]]
 ==== Workshop dates ====
@@ Line 9: / Line 14: @@
 ==== Confirmed participants ====
-(updated 2 March)
+{{ 2021_2_progress_report.png?nolink&500|}}
+(updated 8 March, registration closed)
   * [[ross.kang@gmail.com|Ross Kang]] (organiser)
@@ Line 33: / Line 40: @@
   * Shoham Letzter
   * Matthew Wales
+  * Freddie Illingworth
+  * Xing Shi Cai
+  * Wouter Cames van Batenburg
+  * David Harris
 *denotes speaker
@@ Line 38: / Line 49: @@
 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.
+Registration deadline: 2 March (closed).
 ==== Open problems ====
@@ Line 46: / Line 57: @@
 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
+Deadline: 5 March (closed).
-==== Schedule (tentative, all time European) ====
+==== Schedule (all times European) ====
 . Monday, 8 March
-    a. Two talks (14:30, 15:30)
+    a. Two talks (14:30 Molloy, 15:30 Esperet)
     b. Open problem session/group formation (16:30-18:00)
 . Tuesday, 9 March
     a. Open working sessions
-    b. Progress reports (15:45)
+    b. Coffee break in wonder (15:15)
+    c. Progress reports (15:45)
 . Wednesday, 10 March
-    a. Three talks (14:30, 15:30, 16:30)
+    a. Three talks (14:30 Bernshteyn, 15:30 Rosenfeld, 16:30 Davies)
     b. Social event (20:00)
 . Thursday, 11 March
     a. Open working sessions
-    b. Progress reports (15:45)
+    b. Coffee break in wonder (15:15)
+    c. Progress reports (15:45)
 . Friday, 12 March
     a. Progress reports/Remaining open problems (15:00-16:30)
     b. Closing drinks
 . Sunday 14 March
-    a. Eat pie
+    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.
@@ Line 72: / Line 85: @@
 To preserve the interactive nature of the meeting, no talks are to be recorded and we encourage attendees to keep their cameras on.
-Zoom links will be posted here in due course.
+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 ====
+  * 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