CanaDAM 2021
En ligne, 25 - 28 mai 2021

Probabilistic Approaches
Org: Jozef Skokan (London School of Economics)

ANNIKA HECKEL, Ludwig-Maximilians-Universität München
How does the chromatic number of a random graph vary?  [PDF]

How much does the chromatic number of the random graph $G(n,\frac12)$ vary? Shamir and Spencer proved that it is contained in some sequence of intervals of length about $n^{1/2}$. Alon improved this slightly to $\frac{n^{1/2}}{\log n}$. Until recently, however, no lower bounds whatsoever on the fluctuations of the chromatic number of $G(n,\frac12)$ were known, even though the question was raised by Bollobás many years ago. I will talk about the main ideas needed to prove that, at least for infinitely many n, the chromatic number of $G(n,\frac12)$ is not concentrated on fewer than $n^{1/2 - o(1)}$ consecutive values.

I will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between $n^{1/4+o(1)}$ and $n^{1/2+o(1)}$, depending on n.

Joint work with Oliver Riordan.

MATTHEW JENSSEN, University of Birmingham
Singularity of random symmetric matrices revisited  [PDF]

Let $M_n$ be drawn uniformly from all $n \times n$ symmetric matrices with entries in $\{-1,1\}$. A well-known conjecture states that $M_n$ is singular with probability $\Theta(n^2 2^{-n})$. In this talk, I will discuss some recent progress toward this conjecture. Joint work with Marcelo Campos, Marcus Michelen, and Julian Sahasrabudhe.

JINYOUNG PARK, Institute for Advanced Study
On a problem of M. Talagrand  [PDF]

We will discuss some special cases of a conjecture of M. Talagrand relating two notions of “threshold” for an increasing family F of subsets of a finite set X. The full conjecture implies equivalence of the “Fractional ExpectationThreshold Conjecture,” due to Talagrand and recently proved by Frankston, Kahn, Narayanan, and myself, and the (stronger) “Expectation-Threshold Conjecture” of Kahn and Kalai.

Talagrand showed that his conjecture is true in some special cases and suggested a couple of more challenging test cases. In the talk, I will give more detailed descriptions of this problem, and some proof ideas if time allows.

This is joint work with Keith Frankston and Jeff Kahn.

WILL PERKINS, University of Illinois at Chicago
Correlation decay, phase transitions, and enumeration  [PDF]

I will describe some probabilistic techniques for combinatorial enumeration based on intuition from correlation decay and phase transitions in statistical physics. The techniques combine large deviation bounds, the cluster expansion, and local central limit theorems.

MEHTAAB SAWHNEY, Massachusetts Institute of Technology
Friendly bisections of random graphs  [PDF]

We prove that with high probability, the random graph $G(n,\frac12)$ on an even number of vertices admits a partition of its vertex set into two parts of equal size in which $n-o(n)$ vertices have more neighbours on their own side than across. This settles an old conjecture of F\"uredi from 1988, which also appears as Problem~91 in Green's list of 100 open problems. This is joint work with Asaf Ferber, Matthew Kwan, Bhargav Narayanan and Ashwin Sah.