Throughout the NETWORKS day, presentations will be delivered by speakers including Noela Müller and Jeroen Zuiddam. The program begins at 9:30 AM and concludes at 5:00 PM with drinks. The evening program will commence at 7:00 PM, also at the Trippenhuis. Three speakers—Alice Guionnet (Lyon), Anton Bovier (Bonn), and Aad van der Vaart (Delft)—will highlight the work of Michel Talagrand, the recipient of the 2024 Abel Prize. 

Programme

Abstracts

Frank den Hollander

Mixing of fast random walks on dynamic random permutations

Noëla Müller

The number of random 2-SAT solutions is asymptotically log-normal

The study of random versions of combinatorial optimization problems has produced a spur of research activity among different disciplines. These random versions can serve as benchmark instances for the development of new algorithms, but also be linked to more fundamental questions like those of the mechanisms behind average case computational hardness. At the same time, they may be viewed as examples of glass forming liquids or as candidates for efficient coding schemes. While the study of random constraint satisfaction problems has seen great progress over the past two decades, many open questions remain, particularly related to models that lack a certain type of permutation symmetry. Random 2-SAT is a specifically simple example of a random constraint satisfaction problem lacking this kind of symmetry. In the work that I present, we show that throughout the satisfiable phase, the logarithm of the number of satisfying assignments of a random 2-SAT formula satisfies a central limit theorem. This implies that the log of the number of satisfying assignments exhibits fluctuations that are of the order of the square root of the number of variables. By contrast, for numerous other random constraint satisfaction problems (exhibiting the mentioned symmetry) the typical fluctuations of the logarithm of the number of solutions are bounded throughout all or most of the satisfiable regime.

The talk is based on joint work with Arnab Chatterjee, Amin Coja-Oghlan, Connor Riddlesden, Maurice Rolvien, Pavel Zakharov and Haodong Zhu.

Linda Cook

On polynomial degree-boundedness

We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph H, there is a polynomial p such that for every positive integer s, every graph of average degree at least p(s) either contains K_{s,s} as a subgraph, or contains an induced subdivision of H.

This improves upon a result of Kühn and Osthus from 2004, who proved it for graphs whose average degree is at least triply exponential in s, and a recent result of Du, Girão, Hunter, McCarty and Scott for graphs with average degree at least singly exponential in s.

As an application, we prove that the class of graphs that do not contain an induced subdivision of K_{s,t} is polynomially chi-bounded. In the case of K_{2,3}, this is the class of theta-free graphs, and answers a question of Davies.

Along the way, we also answer a recent question of McCarty, by showing that if A is a hereditary class of graphs for which there is a polynomial p such that every bipartite K_{s,s}-free graph in A has average degree at most p(s), then more generally, there is a polynomial p' such that every K_{s,s}-free graph in A has average degree at most p'(s).

Our main new tool is an induced variant of the Kovari-Sos-Turan theorem, which we find to be of independent interest.

(Note, similar results were found around the same time by Girão and Hunter).

Joint with: Romain Bourneuf (ENS de Lyon), Matija Bucic (Princeton), James Davies (Cambridge).

Jeroen Zuiddam

Shannon capacity, graphs limits, and asymptotic spectrum distance

Determining the Shannon capacity of graphs is a long-standing open problem in graph theory and optimization. Over decades, a wide range of upper and lower bound methods have been developed to analyze this problem. However, despite tremendous effort, even small instances of the problem have remained open.
We take a graph limit approach to the Shannon capacity problem: to determine the Shannon capacity of a graph, construct a sequence of easier to analyse graphs converging to it (in a newly developed "asymptotic spectrum distance"). We give general methods for constructing non-trivial converging sequences. Using a "finite" version of this approach we obtain a better lower bound for the Shannon capacity of the fifteen cycle.
The theory of asymptotic spectrum distance applies not only to Shannon capacity of graphs, and we expect it to be a powerful tool for other asymptotic problems in mathematics and computer science.

Joint work with David de Boer and Pjotr Buys.