## Oxford Discrete Mathematics and Probability Seminar

The online Oxford Discrete Maths and Probability Seminar has been running regularly since March 2020. The talks will take place on Zoom, usually on Tuesdays at 2pm and/or 330pm UK time. The meetings are organized by Christina Goldschmidt and Alex Scott.

There is a seminar mailing list, which you can join by sending an empty email to sympa@maillist.ox.ac.uk with subject "subscribe discmathprob Firstname Lastname" (replace "Firstname Lastname" appropriately!). There is also a google calendar, which can be found here (you can subscribe by following the link and clicking on the + sign in the bottom right hand corner).

Most of the talks will be recorded and made publicly available on our youtube channel. [Please note this for GDPR purposes!]

This is an ongoing experiment, and we are all learning how to do things. We'll figure out what works!

## Current schedule

The schedule is always under construction! We will put up a Zoom link before the seminars take place. A list of past talks can be found below.

14 Nov       2pm             Paul Bastide (LaBRI/TU Delft)
Skipless chain decompositions and improved poset saturation bounds
zoom and slides

Abstract: We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers k and n, a family F of subsets of {1,...,n} is k-antichain saturated if it does not contain an antichain of size k (as induced subposet), but adding any set to F creates an antichain of size k. We use sat*(n,k) to denote the smallest size of such a family. With more work we pinpoint the exact value of sat*(n, k), for all k and sufficiently large n. Previously, exact values for sat*(n,k) were only known for k up to 6. We also show that for any poset P, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: sat*(n, P)=O(n^c), where c <= |P|2/4+1. This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.

330pm            Gábor Pete (Rényi Institute/Budapest University of Technology and Economics)
Preferential attachment trees built from random walks
zoom and slides

Abstract: I will talk about two separate projects where random walks are building a random tree, yielding preferential attachment behaviour from completely local mechanisms.
First, the Tree Builder Random Walk is a randomly growing tree, built by a walker as she is walking around the tree. At each time n, she adds a leaf to her current vertex with probability n, γ∈(2/3, 1], then moves to a uniform random neighbor on the possibly modified tree. We show that the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási-Albert preferential attachment tree model. This coupling implies that many properties known for the BA-model, such as diameter and degree distribution, can be directly transferred to our model. Joint work with János Engländer, Giulio Iacobelli, and Rodrigo Ribeiro. Second, we introduce a network-of-networks model for physical networks: we randomly grow subgraphs of an ambient graph (say, a box of ℤd) until they hit each other, building a tree from how these spatially extended nodes touch each other. We compute non-rigorously the degree distribution exponent of this tree in large generality, and provide a rigorous analysis when the nodes are loop-erased random walks in dimension d=2 or d≥5, using a connection with the Uniform Spanning Tree. Joint work with Ádám Timár, Sigurdur Örn Stefánsson, Ivan Bonamassa, and Márton Pósfai. (See https://arxiv.org/abs/2306.01583)

23 Jan       2pm               Augusto Teixeira (IMPA)
TBA

Abstract: TBA

330pm            Nina Kamčev (University of Zagreb)
TBA

Abstract: TBA

## Past talks

17 Oct        2pm             Maria Chudnovsky (Princeton)
k-blocks and forbidden induced subgraphs
video

Abstract: A k-block in a graph is a set of k vertices every two of which are joined by k vertex disjoint paths. By a result of Weissauer, graphs with no k-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions for bounded tree width, a lot can be said about graphs with no k-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a k-block in a graphs. We will discuss this phenomenon and its consequences in the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.

330pm            Alice Contat (Université Paris-Saclay)
Critical core percolation on random graphs.
video and slides

Abstract: Motivated by the desire to construct large independent sets in random graphs, Karp and Sipser modified the usual greedy construction to yield an algorithm that outputs an independent set with a large cardinal called the Karp-Sipser core. When run on the Erdős-Rényi G(n,c/n) random graph, this algorithm is optimal as long as c < e. We will present the proof of a physics conjecture of Bauer and Golinelli (2002) stating that at criticality, the size of the Karp-Sipser core is of order n3/5. Along the way we shall highlight the similarities and differences with the usual greedy algorithm and the k-core algorithm.
Based on a joint work with Nicolas Curien and Thomas Budzinski.

6 June     330pm             Elchanan Mossel (MIT)
The Metropolis Algorithm for the Planted Clique Problem
video and slides

Abstract: More than 30 year ago Jerrum studied the planted clique problem and proved that under worst-case initialization Metropolis fails to recover planted cliques of size << n1/2 in the Erdős-Rényi graph G(n,1/2). This result is classically cited in the literature of the problem, as the "first evidence" that finding planted cliques of size much smaller than square root n is "algorithmically hard". Cliques of size >> n1/2 are easy to find using simple algorithms. In a recent work we show that the Metropolis process actually fails to find planted cliques under worst-case initialization for cliques up to size almost linear in n. Thus the algorithm fails well beyond the sqrt(n) "conjectured algorithmic threshold". We also prove that, for a large parameter regime, that the Metropolis process fails also under "natural initialization". Our results resolve some open questions posed by Jerrum in 1992. Based on joint work with Zongchen Chen and Iias Zadik.

5pm               David Aldous (U.C. Berkeley and University of Washington)
The Critical Beta-splitting Random Tree
video and slides

Abstract: In the critical beta-splitting model of a random n-leaf rooted tree, clades (subtrees) are recursively split into sub-clades, and a clade of m leaves is split into sub-clades containing i and m-i leaves with probabilities ∝1/(i(m-i)). This model turns out to have interesting properties. There is a canonical embedding into a continuous-time model (CTCS(n)). There is an inductive construction of CTCS(n) as n increases, analogous to the stick-breaking constructions of the uniform random tree and its limit continuum random tree. We study the heights of leaves and the limit fringe distribution relative to a random leaf. In addition to familiar probabilistic methods, there are analytic methods (developed by co-author Boris Pittel), based on explicit recurrences, which often give more precise results. So this model provides an interesting concrete setting in which to compare and contrast these methods. Many open problems remain.
Preprints at https://arxiv.org/abs/2302.05066 and https://arxiv.org/abs/2303.02529

7 Mar        2pm               Paul Seymour (Princeton)
A loglog step towards the Erdős-Hajnal conjecture
video and slides

Abstract: In 1977, Erdős and Hajnal made the conjecture that, for every graph H, there exists c>0 such that every H-free graph G has a clique or stable set of size at least |G|c; and they proved that this is true with |G|c replaced by 2c√{log |G|}. Until now, there has been no improvement on this result (for general H). We recently proved a strengthening: that for every graph H, there exists c>0 such that every H-free graph G with |G|\ge 2 has a clique or stable set of size at least 2c√{log |G| loglog|G|}. This talk will outline the proof. Joint work with Matija Bucic, Tung Nguyen and Alex Scott.

330pm             Miklos Racz (Northwestern)
Correlated stochastic block models: graph matching and community recovery
video and slides

Abstract: I will discuss statistical inference problems on edge-correlated stochastic block models. We determine the information-theoretic threshold for exact recovery of the latent vertex correspondence between two correlated block models, a task known as graph matching. As an application, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. Furthermore, we obtain the precise threshold for exact community recovery using multiple correlated graphs, which captures the interplay between the community recovery and graph matching tasks. This is based on joint work with Julia Gaudio and Anirudh Sridhar.

7 Feb        2pm               Jian Ding (Peking University)
Recent progress on random graph matching problems
video and slides

Abstract: In this talk, I will review some recent progress on random graph matching problems, that is, to recover the vertex correspondence between a pair of correlated random graphs from the observation of two unlabelled graphs. In this talk, I will touch issues of information threshold, efficient algorithms as well as complexity theory. This is based on joint works with Hang Du, Shuyang Gong and Zhangsong Li.

330pm             Sarah Peluse (Princeton/IAS)
Bounds for subsets of 𝔽pnx𝔽pn without L-shaped configurations
video

Abstract: I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi's theorem and describe a proof of such bounds for sets lacking nontrivial configurations of the form (x,y), (x,y+z), (x,y+2z), (x+z,y) in the finite field model setting.

22 Nov     330pm           Michelle Delcourt (Toronto Metropolitan University)
Hypergraph Matchings Avoiding Forbidden Submatchings
video and slides

In 1973, Erdős conjectured the existence of high girth (n,3,2)-Steiner systems. Recently, Glock, Kühn, Lo, and Osthus and independently Bohman and Warnke proved the approximate version of Erdős' conjecture. Just this year, Kwan, Sah, Sawhney, and Simkin proved Erdős' conjecture. As for Steiner systems with more general parameters, Glock, Kühn, Lo, and Osthus conjectured the existence of high girth (n,q,r)-Steiner systems. We prove the approximate version of their conjecture. This result follows from our general main results which concern finding perfect or almost perfect matchings in a hypergraph G avoiding a given set of submatchings (which we view as a hypergraph H where V(H)=E(G)). Our first main result is a common generalization of the classical theorems of Pippenger (for finding an almost perfect matching) and Ajtai, Komlós, Pintz, Spencer, and Szemerédi (for finding an independent set in girth five hypergraphs). More generally, we prove this for coloring and even list coloring, and also generalize this further to when H is a hypergraph with small codegrees (for which high girth designs is a specific instance). A number of applications in various areas follow from our main results including: Latin squares, high dimensional permutations, and rainbow matchings. This is joint work with Luke Postle.

5pm              Philip Easo (Caltech)
Percolation on finite transitive graphs
video and slides

Tom Hutchcroft and I have been working to develop a general theory of percolation on arbitrary finite transitive graphs. This extends from percolation on local approximations to infinite graphs, such as a sequence of tori, to percolation on the complete graphs - the Erdős-Rényi model. I will summarise our progress on the basic questions: When is there a phase transition for the emergence of a giant cluster? When is the giant cluster unique? How does this relate to percolation on infinite graphs? I will then sketch our proof that for finite transitive graphs with uniformly bounded vertex degrees, the supercritical giant cluster is unique, verifying a conjecture of Benjamini from 2001.

25 Oct     330pm            Rose McCarty (Princeton)
Average degree and girth
video

In 1983 Thomassen conjectured that every graph of sufficiently large average degree has a subgraph of large girth and large average degree. While this conjecture remains open, recent evidence suggests that something stronger might be true; perhaps the subgraph can be made induced when a clique and biclique are forbidden. We overview our proof for removing 4-cycles from Kt,t-free bipartite graphs. Moreover, we discuss consequences to tau-boundedness, which is an analog of chi-boundedness.

5pm              Yinon Spinka (UBC)
A tale of two balloons
video and slides

From each point of a Poisson point process start growing a balloon at rate 1. When two balloons touch, they pop and disappear. Will balloons reach the origin infinitely often or not? We answer this question for various underlying spaces. En route we find a new(ish) 0-1 law, and generalize bounds on independent sets that are factors of IID on trees. Joint work with Omer Angel and Gourab Ray.

7 June        3pm             Bastien Mallein (Paris)
Infinite-bin model and the longest increasing path in an Erdős-Rényi graph
video and slides

We consider an oriented acyclic version of the Erdős-Rényi random graph: the set of vertices is {1,...,n}, and for each pair i < j, an edge from i to j is independently added to the graph with probability p. The length of the longest path in such a graph grows linearly with the number of vertices in the graph, and its growth rate is a deterministic function C of the probability p of presence of an edge.
Foss and Konstantopoulos introduced a coupling between these graphs and a particle system called the "Infinite-bin model". By using this coupling, we prove some properties of C, that it is analytic on (0,1], its development in series at point 1 and its asymptotic behaviour as p goes to 0.

430pm             Jinyoung Park (Stanford)
Thresholds
video and slides

Abstract: Thresholds for increasing properties of random structures are a central concern in probabilistic combinatorics and related areas. In 2006, Kahn and Kalai conjectured that for any nontrivial increasing property on a finite set, its threshold is never far from its "expectation-threshold," which is a natural (and often easy to calculate) lower bound on the threshold. In this talk, I will present recent progress on this topic. Based on joint work with Huy Tuan Pham.

17 May        2pm           Baptiste Louf (Uppsala)
Unicellular maps and hyperbolic surfaces in high genus
video and slides

Abstract: In the past few years, the study of the geometric properties of random maps has been extended to a new regime, the "high genus regime", where we are interested in maps whose size and genus tend to infinity at the same time, at the same rate.
We consider here a slightly different case, where the genus also tends to infinity, but less rapidly than the size, and we study the law of simple cycles (with a well-chosen rescaling of the graph distance) in unicellular maps (maps with one face), thanks to a powerful bijection of Chapuy, Féray and Fusy.
The interest of this work is that we obtain exactly the same law as Mirzakhani and Petri who counted closed geodesics on a model of random hyperbolic surfaces in large genus (the Weil-Petersson measure). This leads us to conjecture that these two models are somehow "the same" in the limit. This is joint work with Svante Janson.

330pm             Mehtaab Sawhney (MIT)
Threshold for Steiner triple systems
video

Abstract: We prove that with high probability G(3)(n,n-1+o(1)) contains a spanning Steiner triple system for n≡1,3 mod 6, establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park.
This is joint work with Ashwin Sah and Michael Simkin.

23 Nov        2pm            Mariana Olvera-Cravioto (UNC CHapel Hill)
PageRank on directed preferential attachment graphs
video and slides

Abstract: We study a family of evolving directed random graphs that includes the directed preferential model and the directed uniform attachment model. The directed preferential model is of particular interest since it is known to produce scale-free graphs with regularly varying in-degree distribution. We start by describing the local weak limits for our family of random graphs in terms of randomly stopped continuous-time branching processes, and then use these limits to establish the asymptotic behavior of the corresponding PageRank distribution. We show that the limiting PageRank distribution decays as a power-law in both models, which is surprising for the uniform attachment model where the in-degree distribution has exponential tails. And even for the preferential attachment model, where the power-law hypothesis suggests that PageRank should follow a power-law, our result shows that the two tail indexes are different, with the PageRank distribution having a heavier tail than the in-degree distribution.

9 Nov         2pm             Matija Bucic (Princeton)
Turán numbers of sunflowers
video and slides

Abstract: A collection of distinct sets is called a sunflower if the intersection of any pair of sets equals the common intersection of all the sets. Sunflowers are fundamental objects in extremal set theory with relations and applications to many other areas of mathematics as well as theoretical computer science. A central problem in the area due to Erdős and Rado from 1960 asks for the minimum number of sets of size r needed to guarantee the existence of a sunflower of a given size. Despite a lot of recent attention including a polymath project and some amazing breakthroughs, even the asymptotic answer remains unknown.
We study a related problem first posed by Duke and Erdős in 1977 which requires that in addition the intersection size of the desired sunflower be fixed. This question is perhaps even more natural from a graph theoretic perspective since it asks for the Turán number of a hypergraph made by the sunflower consisting of k edges, each of size r and with common intersection of size t. For a fixed size of the sunflower k, the order of magnitude of the answer has been determined by Frankl and Furedi. In the 1980's, with certain applications in mind, Chung, Erdős and Graham and Chung and Erdős considered what happens if one allows k, the size of the desired sunflower, to grow with the size of the ground set. In the three uniform case r=3 the correct dependence on the size of the sunflower has been determined by Duke and Erdős and independently by Frankl and in the four uniform case by Bucic, Draganic, Sudakov and Tran. We resolve this problem for any uniformity, by determining up to a constant factor the n-vertex Turán number of a sunflower of arbitrary uniformity r, common intersection size t and with the size of the sunflower k allowed to grow with n. Joint work with: Domagoj Bradac and Benny Sudakov

26 Oct         2pm            Ashwin Sah (MIT)
Friendly bisections of random graphs
video and slides

Abstract: We introduce a new method for studying stochastic processes in random graphs controlled by degree information, involving combining enumeration techniques with an abstract second moment argument. We use it to constructively resolve a conjecture of Füredi from 1988: with high probability, the random graph G(n,1/2) admits a friendly bisection of its vertex set, i.e., a partition of its vertex set into two parts whose sizes differ by at most one in which n-o(n) vertices have at least as many neighbours in their own part as across. This work is joint with Asaf Ferber, Matthew Kwan, Bhargav Narayanan, and Mehtaab Sawhney.

12 Oct         2pm            Sumit Mukherjee (Columbia)
Generalized birthday problem for October 12
video and slides

Abstract: Suppose there are n students in a class. But assume that not everybody is friends with everyone else, and there is a graph which determines the friendship structure. What is the chance that there are two friends in this class, both with birthdays on October 12? More generally, given a simple labelled graph Gn on n vertices, color each vertex with one of c=cn colors chosen uniformly at random, independent from other vertices. We study the question: what is the number of monochromatic edges of color 1?
As it turns out, the limiting distribution has three parts, the first and second of which are quadratic and linear functions of a homogeneous Poisson point process, and the third component is an independent Poisson. In fact, we show that any distribution limit must belong to the closure of this class of random variables. As an application, we characterize exactly when the limiting distribution is a Poisson random variable.
This talk is based on joint work with Bhaswar Bhattacharya and Somabha Mukherjee.

8 Jun                           Special day: Round the World Relay in Combinatorics

This will be an all-day event, with seminars from 22 locations around the world. See here for details!

1 Jun                           Special afternoon: Random Matrix Theory and Combinatorics

2pm               Konstantin Tikhomirov (Georgia Tech)
Invertibility of random square matrices
video

Abstract: Consider an n by n random matrix A with i.i.d entries. In this talk, we discuss some results on the magnitude of the smallest singular value of A, and, in particular, the problem of estimating the singularity probability when the entries of A are discrete.

330pm             Gérard Ben Arous (Courant Institute)
Random Determinants and the Elastic Manifold
slides

This is joint work with Paul Bourgade and Benjamin McKenna (Courant Institute, NYU).
The elastic manifold is a paradigmatic representative of the class of disordered elastic systems. These models describe random surfaces with rugged shapes resulting from a competition between random spatial impurities (preferring disordered configurations), on the one hand, and elastic self-interactions (preferring ordered configurations), on the other. The elastic manifold model is interesting because it displays a depinning phase transition and has a long history as a testing ground for new approaches in statistical physics of disordered media, for example for fixed dimension by Fisher (1986) using functional renormalization group methods, and in the high-dimensional limit by Mézard and Parisi (1992) using the replica method.
We study the topology of the energy landscape of this model in the Mézard-Parisi setting, and compute the (annealed) topological complexity both of total critical points and of local minima. Our main result confirms the recent formulas by Fyodorov and Le Doussal (2020) and allows to identify the boundary between simple and glassy phases. The core argument relies on the analysis of the asymptotic behavior of large random determinants in the exponential scale.

25 May        2pm           Vincent Tassion (ETH)
Crossing probabilities for planar percolation
video and slides

Abstract: Percolation models were originally introduced to describe the propagation of a fluid in a random medium. In dimension two, the percolation properties of a model are encoded by so-called crossing probabilities (probabilities that certain rectangles are crossed from left to right). In the eighties, Russo, Seymour and Welsh obtained general bounds on crossing probabilities for Bernoulli percolation (the most studied percolation model, where edges of a lattice are independently erased with some given probability 1-p). These inequalities rapidly became central tools to analyze the critical behavior of the model.
In this talk I will present a new result which extends the Russo-Seymour-Welsh theory to general percolation measures satisfying two properties: symmetry and positive correlation. This is a joint work with Laurin Köhler-Schindler.

330pm             Michael Krivelevich (Tel Aviv)
Cycle lengths in sparse random graphs
video and slides

Abstract: We study the set L(G) of cycle lengths that appear in a sparse binomial random graph G(n,c/n) and in a random d-regular graph Gn,d. We show in particular that for most values of c, for G drawn from G(n,c/n) the set L(G) contains typically an interval [ω(1), (1-o(1))Lmax(G)], where Lmax(G) is the length of a longest cycle (the circumference) of G. For the case of random d-regular graphs, d≥3 fixed, we obtain an accurate asymptotic estimate for the probability of L(G) to contain a full interval [k,n] for a fixed k≥3. Similar results are obtained also for the supercritical case G(n,(1+ε)/n), and for random directed graphs.
A joint work with Yahav Alon and Eyal Lubetzky.

18 May        2pm            Mihyun Kang (Graz)
Benjamini-Schramm local limits of sparse random planar graphs
video and slides

Abstract: In this talk we will discuss some classical and recent results on local limits of random graphs. It is well known that the limiting object of the local structure of the classical Erdős-Renyi random graph is a Galton-Watson tree. This can nicely be formalised in the language of Benjamini-Schramm or Aldous-Steele local weak convergence. Regarding local limits of sparse random planar graphs, there is a smooth transition from a Galton-Watson tree to a Skeleton tree. This talk is based on joint work with Michael Missethan.

330pm             Amedeo Sgueglia (LSE)
Factors in randomly perturbed graphs
video and slides

Abstract: We study the model of randomly perturbed dense graphs, which is the union of any n-vertex graph Gα with minimum degree at least αn and the binomial random graph G(n,p). In this talk, we shall examine the following central question in this area: to determine when Gα ∪ G(n,p) contains H-factors, i.e. spanning subgraphs consisting of vertex disjoint copies of the graph H. We offer several new sharp and stability results.
This is joint work with Julia Böttcher, Olaf Parczyk, and Jozef Skokan.

11 May        3pm            Cécile Mailler (Bath)
The ants walk: finding geodesics in graphs using reinforcement learning
video

Abstract: How does a colony of ants find the shortest path between its nest and a source of food without any means of communication other than the pheromones each ant leave behind itself?
In this joint work with Daniel Kious (Bath) and Bruno Schapira (Marseille), we introduce a new probabilistic model for this phenomenon. In this model, the nest and the source of food are two marked nodes in a finite graph. Ants perform successive random walks from the nest to the food, and the distribution of the n-th walk depends on the trajectories of the (n-1) previous walks through some linear reinforcement mechanism.
Using stochastic approximation methods, couplings with Pólya urns, and the electric conductances method for random walks on graphs (which I will explain on some simple examples), we prove that, depending on the exact reinforcement rule, the ants may or may not always find the shortest path(s) between their nest and the source food.

430pm             Asaf Ferber (University of California, Irvine)
Lower bounds for multicolor Ramsey numbers
video

Abstract: We present an exponential improvement to the lower bound on diagonal Ramsey numbers for any fixed number of colors greater than two.
This is a joint work with David Conlon.

4 May        2pm             Annika Heckel (LMU München)
How does the chromatic number of a random graph vary?
video and slides

Abstract: How much does the chromatic number of the random graph G(n, 1/2) vary? Shamir and Spencer proved that it is contained in some sequence of intervals of length about n1/2. Alon improved this slightly to n1/2 / log n. Until recently, however, no lower bounds on the fluctuations of the chromatic number of G(n, 1/2) 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, 1/2) is not concentrated on fewer than n1/2-o(1)consecutive values.
I will also discuss the Zigzag Conjecture, made recently by Bollob\'as, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between n1/4+o(1)) and n1/2+o(1), depending on n.
Joint work with Oliver Riordan.

330pm             Jean-François Le Gall (Paris-Saclay)
Geodesics in random geometry
video and slides

We discuss the behavior of geodesics in the continuous models of random geometry known as the Brownian map and the Brownian plane. We say that a point x is a geodesic star with m arms if x is the endpoint of m disjoint geodesics. We prove that the set of all geodesic stars with m arms has dimension 5-m , for m=1,2,3,4. This complements recents results of Miller and Qian, who derived upper bounds for these dimensions.

27 Apr        2pm             Guillem Perarnau (Universitat Politècnica de Catalunya)
Maximum stationary values in directed random graphs
video and slides

Abstract: In this talk we will consider the extremal values of the stationary distribution of the sparse directed configuration model. Under the assumption of linear $(2+\eta)$-moments on the in-degrees and of bounded out-degrees, we obtain tight comparisons between the maximum value of the stationary distribution and the maximum in-degree. Under the further assumption that the order statistics of the in-degrees have power-law behavior, we show that the upper tail of the stationary distribution also has power-law behavior with the same index. Moreover, these results extend to the PageRank scores of the model, thus confirming a version of the so-called power-law hypothesis. Joint work with Xing Shi Cai, Pietro Caputo and Matteo Quattropani.

330pm             Roberto Oliveira (IMPA)
Reversible Markov chains with nonnegative spectrum
video

Abstract: The title of the talk corresponds to a family of interesting random processes, which includes lazy random walks on graphs and much beyond them. Often, a key step in analysing such processes is to estimate their spectral gaps (ie. the difference between two largest eigenvalues). It is thus of interest to understand what else about the chain we can know from the spectral gap. We will present a simple comparison idea that often gives us the best possible estimates. In particular, we re-obtain and improve upon several known results on hitting, meeting, and intersection times; return probabilities; and concentration inequalities for time averages. We then specialize to the graph setting, and obtain sharp inequalities in that setting. This talk is based on work that has been in progress for far too long with Yuval Peres.

9 Mar        2pm             Bénédicte Haas (Paris 13)
Tail asymptotics for extinction times of self-similar fragmentations
video and slides

Abstract: Self-similar fragmentation processes are random models for particles that are subject to successive fragmentations. When the index of self-similarity is negative the fragmentations intensify as the masses of particles decrease. This leads to a shattering phenomenon, where the initial particle is entirely reduced to dust - a set of zero-mass particles - in finite time which is what we call the extinction time. Equivalently, these extinction times may be seen as heights of continuous compact rooted trees or scaling limits of heights of sequences of discrete trees. Our objective is to set up precise bounds for the large time asymptotics of the tail distributions of these extinction times.

330pm            Corrine Yap (Rutgers)
A Topological Turán Problem
video and slides

Abstract: The classical Turán problem asks: given a graph H, how many edges can an n-vertex graph have while containing no isomorphic copy of H? By viewing (k+1)-uniform hypergraphs as k-dimensional simplicial complexes, we can ask a topological version (first posed by Nati Linial): given a k-dimensional simplicial complex S, how many facets can an n-vertex k-dimensional simplicial complex have while containing no homeomorphic copy of S? Until recently, little was known for k > 2. In this talk, we give an answer for general k, by way of dependent random choice and the combinatorial notion of a trace-bounded hypergraph. Joint work with Jason Long and Bhargav Narayanan.

2 Mar       2pm               Justin Salez (Université Paris-Dauphine)
Sparse expanders have negative Ollivier-Ricci curvature
slides (video available by request from the organizers)

We prove that bounded-degree expanders with non-negative Ollivier-Ricci curvature do not exist, thereby solving a long-standing open problem suggested by Naor and Milman and publicized by Ollivier (2010). In fact, this remains true even if we allow for a vanishing proportion of large degrees, large eigenvalues, and negatively-curved edges. To establish this, we work directly at the level of Benjamini-Schramm limits. More precisely, we exploit the entropic characterization of the Liouville property on stationary random graphs to show that non-negative curvature and spectral expansion are incompatible 'at infinity'. We then transfer this result to finite graphs via local weak convergence and a relative compactness argument. We believe that this 'local weak limit' approach to mixing properties of Markov chains will have many other applications.

330pm            Perla Sousi (Cambridge)
The uniform spanning tree in 4 dimensions
video and slides

A uniform spanning tree of ℤ4 can be thought of as the "uniform measure" on trees of ℤ4. The past of 0 in the uniform spanning tree is the finite component that is disconnected from infinity when 0 is deleted from the tree. We establish the logarithmic corrections to the probabilities that the past contains a path of length n, that it has volume at least n and that it reaches the boundary of the box of side length n around 0. Dimension 4 is the upper critical dimension for this model in the sense that in higher dimensions it exhibits "mean-field" critical behaviour. An important part of our proof is the study of the Newtonian capacity of a loop erased random walk in 4 dimensions. This is joint work with Tom Hutchcroft.

16 Feb       2pm              Nati Linial (Hebrew University)
Geodesic Geometry on Graphs
video and slides

Abstract: We investigate a graph theoretic analog of geodesic geometry. In a graph G=(V,E) we consider a system of pathsP={Pu,v| u,v∈V} where Pu,v connects vertices u and v. This system is consistent in that if vertices y,z are in Pu,v, then the sub-path of Pu,v between them coincides with Py,z. A map w:E→(0,∞) is said to induce P if for every u,v∈V the path Pu,v is w-geodesic. We say that G is metrizable if every consistent path system is induced by some such w. As we show, metrizable graphs are very rare, whereas there exist infinitely many 2-connected metrizable graphs.
This is the MSc thesis of Daniel Cizma done under my guidance

330pm            Ramon van Handel (Princeton)
Some unusual extremal problems in convexity and combinatorics

Abstract: It is a basic fact of convexity that the volume of convex bodies is a polynomial, whose coefficients contain many familiar geometric parameters as special cases. A fundamental result of convex geometry, the Alexandrov-Fenchel inequality, states that these coefficients are log-concave. This proves to have striking connections with other areas of mathematics: for example, the appearance of log-concave sequences in many combinatorial problems may be understood as a consequence of the Alexandrov-Fenchel inequality and its algebraic analogues.
There is a long-standing problem surrounding the Alexandrov-Fenchel inequality that has remained open since the original works of Minkowski (1903) and Alexandrov (1937): in what cases is equality attained? In convexity, this question corresponds to the solution of certain unusual isoperimetric problems, whose extremal bodies turn out to be numerous and strikingly bizarre. In combinatorics, an answer to this question would provide nontrivial information on the type of log-concave sequences that can arise in combinatorial applications. In recent work with Y. Shenfeld, we succeeded to settle the equality cases completely in the setting of convex polytopes. I will aim to describe this result, and to illustrate its potential combinatorial implications through a question of Stanley on the combinatorics of partially ordered sets.

9 Feb       2pm                Robin Stephenson (Sheffield)
The scaling limit of a critical random directed graph
video and slides

Abstract: We consider the random directed graph D(n,p) with vertex set {1,2,…,n} in which each of the n(n-1) possible directed edges is present independently with probability p. We are interested in the strongly connected components of this directed graph. A phase transition for the emergence of a giant strongly connected component is known to occur at p = 1/n, with critical window p = 1/n + λn-4/3 for λ∈ℝ. We show that, within this critical window, the strongly connected components of D(n,p), ranked in decreasing order of size and rescaled by n-1/3, converge in distribution to a sequence (C1,C2,…) of finite strongly connected directed multigraphs with edge lengths which are either 3-regular or loops. The convergence occurs in the sense of an L1 sequence metric for which two directed multigraphs are close if there are compatible isomorphisms between their vertex and edge sets which roughly preserve the edge lengths. Our proofs rely on a depth-first exploration of the graph which enables us to relate the strongly connected components to a particular spanning forest of the undirected Erdős-Rényi random graph G(n,p), whose scaling limit is well understood. We show that the limiting sequence (C1,C2,…) contains only finitely many components which are not loops. If we ignore the edge lengths, any fixed finite sequence of 3-regular strongly connected directed multigraphs occurs with positive probability.

330pm            Vida Dujmović (Ottawa)
Product structure theory and its applications
video and slides

Abstract: I will introduce product structure theory of graphs and show how families of graphs that have such a structure admit short adjacency labeling scheme and small induced universal graphs. Time permitting, I will talk about another recent application of product structure theory, namely vertex ranking (coloring)

2 Feb          2pm             Lisa Sauermann (IAS)
On the extension complexity of low-dimensional polytopes
video and slides

Abstract: It is sometimes possible to represent a complicated polytope as a projection of a much simpler polytope. To quantify this phenomenon, the extension complexity of a polytope P is defined to be the minimum number of facets in a (possibly higher-dimensional) polytope from which P can be obtained as a (linear) projection. In this talk, we discuss some results on the extension complexity of random d-dimensional polytopes (obtained as convex hulls of random points on either on the unit sphere or in the unit ball), and on the extension complexity of polygons with all vertices on a common circle. Joint work with Matthew Kwan and Yufei Zhao.

330pm            Nathanaël Berestycki (Vienna)
Free boundary dimers: random walk representation and scaling limit
video and slides

Abstract: The dimer model, a classical model of statistical mechanics, is the uniform distribution on perfect matchings of a graph. In two dimensions, one can define an associated height function which turns the model into a random surface (with specified boundary conditions). In the 1960s, Kasteleyn and Temperley/Fisher found an exact "solution" to the model, computing the correlations in terms of a matrix called the Kasteleyn matrix. This exact solvability was the starting point for the breakthrough work of Kenyon (2000) who proved that the centred height function converges to the Dirichlet (or zero boundary conditions) Gaussian free field. This was the first proof of conformal invariance in statistical mechanics.
In this talk, I will focus on a natural modification of the model where one allows the vertices on the boundary of the graph to remain unmatched: this is the so-called monomer-dimer model, or dimer model with free boundary conditions. The main result that we obtain is that the scaling limit of the height function of the monomer-dimer model in the upper half-plane is the Neumann (or free boundary conditions) Gaussian free field. Key to this result is a somewhat miraculous random walk representation for the inverse Kasteleyn matrix, which I hope to discuss.
Joint work with Marcin Lis (Vienna) and Wei Qian (Paris).

26 Jan        2pm             Richard Montgomery (Birmingham)
A solution to Erdős and Hajnal's odd cycle problem
video and slides

Abstract: I will discuss how to construct cycles of many different lengths in graphs, in particular answering the following two problems on odd and even cycles. Erdős and Hajnal asked in 1981 whether the sum of the reciprocals of the odd cycle lengths in a graph diverges as the chromatic number increases, while, in 1984, Erdős asked whether there is a constant C such that every graph with average degree at least C contains a cycle whose length is a power of 2.

330pm            Noga Alon (Princeton)
Random friends walking on random graphs
video and slides

Abstract: Let X and Y be two n-vertex graphs. Identify the vertices of Y with n people, any two of whom are either friends or strangers (according to the edges and non-edges in Y), and imagine that these people are standing one at each vertex of X. At each point in time, two friends standing at adjacent vertices of X may swap places, but two strangers may not. The friends-and-strangers graph FS(X,Y) has as its vertex set the collection of all configurations of people standing on the vertices of X, where two configurations are adjacent when they are related via a single friendly swap. This provides a common generalization for the famous 15-puzzle, transposition Cayley graphs of symmetric groups, and early work of Wilson and of Stanley.
I will describe several recent results and open problems addressing the extremal and typical aspects of the notion, focusing on the result that the threshold probability for connectedness of FS(X,Y) for two independent binomial random graphs X and Y in G(n,p) is p=p(n)=n-1/2+o(1).
Joint work with Colin Defant and Noah Kravitz.

19 Jan                           Special afternoon: Logic and Combinatorics

230pm           Emmanuel Breuillard (Cambridge)
A subspace theorem for manifolds
slides

Abstract: The Schmidt subspace theorem is a far-reaching generalization of the Thue-Siegel-Roth theorem in diophantine approximation. In this talk I will give an interpretation of Schmidt's subspace theorem in terms of the dynamics of diagonal flows on homogeneous spaces and describe how the exceptional subspaces arise from certain rational Schubert varieties associated to the family of linear forms through the notion of Harder-Narasimhan filtration and an associated slope formalism. This geometric understanding opens the way to a natural generalization of Schmidt's theorem to the setting of diophantine approximation on submanifolds of GLd, which is our main result. In turn this allows us to recover and generalize the main results of Kleinbock and Margulis regarding diophantine exponents of submanifolds. I will also mention an application to diophantine approximation on Lie groups. Joint work with Nicolas de Saxcé.

4pm            Artem Chernikov (UCLA)
Hypergraph regularity and higher arity VC-dimension
video and slides

Abstract: We generalize the fact that all graphs omitting a fixed finite bipartite graph can be uniformly approximated by rectangles (Alon-Fischer-Newman, Lovász-Szegedy), showing that hypergraphs omitting a fixed finite (k+1)-partite (k+1)-uniform hypergraph can be approximated by k-ary cylinder sets.
In particular, in the decomposition given by hypergraph regularity one only needs the first k levels: such hypergraphs can be approximated using sets of vertices, sets of pairs, and so on up to sets of k-tuples, and on most of the resulting k-ary cylinder sets, the density is either close to 0 or close to 1. Moreover, existence of such approximations uniformly under all measures on the vertices is a characterization.Our proof uses a combination of analytic, combinatorial and model-theoretic methods, and involves a certain higher arity generalization of the epsilon-net theorem from VC-theory.
Joint work with Henry Towsner.

24 Nov       2pm             Alexander Holroyd (Bristol)
Matching Random Points
video and slides

Abstract: What is fairness, and to what extent is it practically achievable? I'll talk about a simple mathematical model under which one might hope to understand such questions. Red and blue points occur as independent homogeneous Poisson processes of equal intensity in Euclidean space, and we try to match them to each other. We would like to minimize the sum of a some function (say, a power, γ) of the distances between matched pairs. This does not make sense, because the sum is infinite, so instead we satisfy ourselves with minimizing *locally*. If the points are interpreted as agents who would like to be matched as close as possible, the parameter γ encodes a measure of fairness - large γ means that we try to avoid occasional very bad outcomes (long edges), even if that means inconvenience to others - small γ means everyone is in it for themselves.
In dimension 1 we have a reasonably complete picture, with a phase transition at γ=1. For γ<1 there is a unique minimal matching, while for γ>1 there are multiple matchings but no stationary solution. In higher dimensions, even existence is not clear in all cases.

330pm               Gwenaël Joret (Université Libre de Bruxelles)
Sparse universal graphs for planarity
video and slides

This talk will focus on the following two related problems:
(1) What is the minimum number of edges in a graph containing all n-vertex planar graphs as subgraphs? A simple construction of Babai, Erdős, Chung, Graham, and Spencer (1982) has O(n3/2) edges, which is the best known upper bound.
(2) What is the minimum number of *vertices* in a graph containing all n-vertex planar graphs as *induced* subgraphs? Here steady progress has been achieved over the years, culminating in a O(n4/3) bound due to Bonamy, Gavoille, and Pilipczuk (2019).
As it turns out, a bound of n1+o(1) can be achieved for each of these two problems. The two constructions are somewhat different but are based on a common technique. In this talk I will first give a gentle introduction to the area and then sketch these constructions. The talk is based on joint works with Vida Dujmović, Louis Esperet, Cyril Gavoille, Piotr Micek, and Pat Morin.

17 Nov       2pm             Yuval Peled (Courant)
Minimum weight disk triangulations and fillings
video and slides

We study the minimum total weight of a disk triangulation using any number of vertices out of {1,..,n} where the boundary is fixed and the $n \choose 3$ triangles have independent rate-1 exponential weights. We show that, with high probability, the minimum weight is equal to (c+o(1))n-1/2log n for an explicit constant c. Further, we prove that, with high probability, the minimum weights of a homological filling and a homotopical filling of the cycle (123) are both attained by the minimum weight disk triangulation. We will discuss a related open problem concerning simple-connectivity of random simplicial complexes, where a similar phenomenon is conjectured to hold. Based on joint works with Itai Benjamini, Eyal Lubetzky, and Zur Luria.

330pm               Ron Rosenthal (Technion)
Random Steiner complexes and simplical spanning trees
(video available by request from the organizers)

A spanning tree of G is a subgraph of G with the same vertex set as G that is a tree. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in random k-regular graphs, showing that the number of spanning trees κ1(Gn) in a random k-regular graph on n vertices satisfies limn→∞1(Gn))1/n=c1,k in probability, where c1,k=(k-1)k-1(k^2-2k)-(k-2)/2.
In this talk we will discuss a high-dimensional of the matching model for simplicial complexes, known as random Steiner complexes. In particular, we will prove a high-dimensional counterpart of McKay's result and discuss the local limit of such random complexes.
Based on a joint work with Lior Tenenbaum.

10 Nov       2pm             Vincent Beffara (Grenoble)
Critical behavior without FKG
video and slides

I will present work in progress with D. Gayet and F. Pouran (Grenoble) to establish Russo-Seymour-Welsh (RSW) estimates for 2d statistical mechanics models that do not satisfy the FKG inequality. RSW states that critical percolation has no characteristic length, in the sense that large rectangles are crossed by an open path with a probability that is bounded below by a function of their shape, but uniformly in their size; this ensures the polynomial decay of many relevant quantities and opens the way to deeper understanding of the critical features of the model. All the standard proofs of RSW rely on the FKG inequality, i.e. on the positive correlation between increasing events; we establish the stability of RSW under small perturbations that do not preserve FKG, which extends it for instance to the high-temperature anti-ferromagnetic Ising model.

330pm               Tom Hutchcroft (Cambridge)
Power-law bounds for critical long-range percolation
video and slides

Abstract: In long-range percolation on ℤd, each potential edge {x,y} is included independently at random with probability roughly β||x-y||-d-α, where α > 0 controls how long-range the model is and β > 0 is an intensity parameter. The smaller α is, the easier it is for very long edges to appear. We are normally interested in fixing α and studying the phase transition that occurs as β is increased and an infinite cluster emerges. Perhaps surprisingly, the phase transition for long-range percolation is much better understood than that of nearest neighbour percolation, at least when α is small: It is a theorem of Noam Berger that if α < d then the phase transition is continuous, meaning that there are no infinite clusters at the critical value of β. (Proving the analogous result for nearest neighbour percolation is a notorious open problem!) In my talk I will describe a new, quantitative proof of Berger's theorem that yields power-law upper bounds on the distribution of the cluster of the origin at criticality.
As a part of this proof, I will describe a new universal inequality stating that on any graph, the maximum size of a percolation cluster is of the same order as its median with high probability. This inequality can also be used to give streamlined new proofs of various classical results on e.g. Erdős-Rényi random graphs, which I will hopefully have time to talk a little bit about also.

3 Nov       2pm               Julian Sahasrabudhe (Cambridge)
Combinatorics from the zeros of polynomials
video and slides

Abstract: Let X be a random variable, taking values in {1,…,n}, with standard deviation σ and let fX be its probability generating function. Pemantle conjectured that if σ is large and fX has no roots close to 1 in the complex plane then X must approximate a normal distribution. In this talk, I will discuss a complete resolution of Pemantle's conjecture. As an application, we resolve a conjecture of Ghosh, Liggett and Pemantle by proving a multivariate central limit theorem for, so called, strong Rayleigh distributions. I will also discuss how these sorts of results shed light on random variables that arise naturally in combinatorial settings. This talk is based on joint work with Marcus Michelen.

330pm                Shoham Letzter (UCL)
An improvement on Łuczak's connected matchings method
video and slides

Abstract: A connected matching is a matching contained in a connected component. A well-known method due to Łuczak reduces problems about monochromatic paths and cycles in complete graphs to problems about monochromatic matchings in almost complete graphs. We show that these can be further reduced to problems about monochromatic connected matchings in complete graphs.
I will describe Łuczak's reduction, introduce the new reduction, and mention potential applications of the improved method.

27 Oct       2pm              Igor Kortchemski (Ecole polytechnique)
The geometry of random minimal factorizations of a long cycle
video and slides

Abstract: We will be interested in the structure of random typical minimal factorizations of the n-cycle into transpositions, which are factorizations of (1,…,n) as a product of n-1 transpositions. We shall establish a phase transition when a certain amount of transpositions have been read one after the other. One of the main tools is a limit theorem for two-type Bienaymé-Galton-Watson trees conditioned on having given numbers of vertices of both types, which is of independent interest. This is joint work with Valentin Féray.

330pm               Luke Postle (Waterloo)
video and slides

Abstract: In 1943, Hadwiger conjectured that every graph with no Kt minor is (t-1)-colorable for every t≥1. In the 1980s, Kostochka and Thomason independently proved that every graph with no Kt minor has average degree O(t(log t)1/2) and hence is O(t(log t)1/2)-colorable. Recently, Norin, Song and I showed that every graph with no Kt minor is O(t(log t)β)-colorable for every β > 1/4, making the first improvement on the order of magnitude of the O(t(log t)1/2) bound. Here we show that every graph with no Kt minor is O(t (log t)β)-colorable for every β > 0; more specifically, they are O(t (log log t)6)-colorable.

20 Oct                           Special morning: North meets South 2 -- Discrete Maths and Probability in Japan and Australia

900am             David Croydon (Kyoto)
Scaling limits of the two- and three-dimensional uniform spanning trees
video and slides

Abstract: I will introduce recent work on the two- and three-dimensional uniform spanning trees (USTs) that establish the laws of these random objects converge under rescaling in a space whose elements are measured, rooted real trees, continuously embedded into Euclidean space. (In the three-dimensional case, the scaling result is currently only known along a particular scaling sequence.) I will also discuss various properties of the intrinsic metrics and measures of the limiting spaces, including their Hausdorff dimension, as well as the scaling limits of the random walks on the two- and three-dimensional USTs. In the talk, I will attempt to emphasise where the differences lie between the two cases, and in particular the additional challenges that arise when it comes to the three-dimensional model.
The two-dimensional results are joint with Martin Barlow (UBC) and Takashi Kumagai (Kyoto). The three-dimensional results are joint with Omer Angel (UBC) and Sarai Hernandez-Torres (UBC).

1030am             Anita Liebenau (UNSW)
The threshold bias of the clique-factor game
video and slides

Let r>3 be an integer and consider the following game on the complete graph Kn for n a multiple of r: Two players, Maker and Breaker, alternately claim previously unclaimed edges of Kn such that in each turn Maker claims one and Breaker claims b edges. Maker wins if her graph contains a Kr-factor, that is a collection of n/r vertex-disjoint copies of Kr, and Breaker wins otherwise. In other words, we consider the b-biased Kr-factor Maker-Breaker game. We show that the threshold bias for this game is of order n2/(r+2). This makes a step towards determining the threshold bias for making bounded-degree spanning graphs and extends a result of Allen, Böttcher, Kohayakawa, Naves and Person who resolved the case r=3 or 4 up to a logarithmic factor.

13 Oct       2pm              Asaf Nachmias (Tel Aviv)
The local limit of uniform spanning trees
video

Abstract: Let Gn be a sequence of finite, simple, connected, regular graphs with degrees tending to infinity and let Tn be a uniformly drawn spanning tree of Gn. In joint work with Yuval Peres we show that the local limit of Tn is the Poisson(1) branching process conditioned to survive forever (that is, the asymptotic frequency of the appearance of any small subtree is given by the branching process). The proof is based on electric network theory and I hope to show most of it.

330pm               Caroline Terry (Ohio State)
Speeds of hereditary properties and mutual algebricity
(video available by request from the organizers)

Abstract: A hereditary graph property is a class of finite graphs closed under isomorphism and induced subgraphs. Given a hereditary graph property H, the speed of H is the function which sends an integer n to the number of distinct elements in H with underlying set {1,...,n}. Not just any function can occur as the speed of hereditary graph property. Specifically, there are discrete jumps" in the possible speeds. Study of these jumps began with work of Scheinerman and Zito in the 90's, and culminated in a series of papers from the 2000's by Balogh, Bollobás, and Weinreich, in which essentially all possible speeds of a hereditary graph property were characterized. In contrast to this, many aspects of this problem in the hypergraph setting remained unknown. In this talk we present new hypergraph analogues of many of the jumps from the graph setting, specifically those involving the polynomial, exponential, and factorial speeds. The jumps in the factorial range turned out to have surprising connections to the model theoretic notion of mutual algebricity, which we also discuss. This is joint work with Chris Laskowski.

6 Oct       2pm                Janos Pach (Rényi Institute, Budapest and MIPT, Moscow)
The Schur-Erdős problem for graphs of bounded dimension
video

Abstract: There is a growing body of results in extremal combinatorics and Ramsey theory which give better bounds or stronger conclusions under the additional assumption of bounded VC-dimension. Schur and Erdős conjectured that there exists a suitable constant c with the property that every graph with at least 2cm vertices, whose edges are colored by m colors, contains a monochromatic triangle. We prove this conjecture for edge-colored graphs such that the set system induced by the neighborhoods of the vertices with respect to each color class has bounded VC-dimension. This result is best possible up to the value of c.
Joint work with Jacob Fox and Andrew Suk.

330pm                Nina Holden (ETH)
Liouville quantum gravity with matter central in (1,25): a probabilistic approach
video and slides

Abstract: Liouville quantum gravity (LQG) is a theory of random fractal surfaces with origin in the physics literature in the 1980s. Most literature is about LQG with matter central charge c∈(-∞,1]. We study a discretization of LQG which makes sense for all c∈(-∞,25). Based on a joint work with Gwynne, Pfeffer, and Remy.

9 Jun                              Special afternoon: Statistical physics and algorithms

2pm                Dana Randall (Georgia Tech)
Markov Chains for Programmable Active Matter
video and slides

Abstract: Active matter describes ensembles of self-organizing agents, or particles, interacting with their local environments so that their micro-scale behavior determines macro-scale characteristics of the ensemble. While there has been a surge of activity exploring the physics underlying such systems, less attention has been paid to questions of how to program them to achieve desired outcomes. We will present some recent results designing programmable active matter for specific tasks, including aggregation, dispersion, speciation, and locomotion, building on insights from stochastic algorithms and statistical physics.

3pm                Will Perkins (UIC)
First-order phase transitions and efficient sampling algorithms
video and slides

Abstract: What is the connection between phase transitions in statistical physics and the computational tractability of approximate counting and sampling? There are many fascinating answers to this question but many mysteries remain. I will discuss one particular type of a phase transition: the first-order phase in the Potts model on ℤd for large q, and show how tools used to analyze the phase transition can be turned into efficient algorithms at the critical temperature. In the other direction, I'll discuss how the algorithmic perspective can help us understand phase transitions.

430pm                Allan Sly (Princeton)
Replica Symmetry Breaking for Random Regular NAESAT
video and slides

Abstract: Ideas from physics have predicted a number of important properties of random constraint satisfaction problems such as the satisfiability threshold and the free energy (the exponential growth rate of the number of solutions). Another prediction is the condensation regime where most of the solutions are contained in a small number of clusters and the overlap of two random solutions is concentrated on two points. We establish this phenomena in the random regular NAESAT model. Joint work with Danny Nam and Youngtak Sohn.

2 Jun     at 2pm              Wojciech Samotij (Tel Aviv)
An entropy proof of the Erdős-Kleitman-Rothschild theorem.
slides (video available by request from the organizers)

Abstract: We say that a graph G is H-free if G does not contain H as a (not necessarily induced) subgraph. For a positive integer n, denote by ex(n,H) the largest number of edges in an H-free graph with n vertices (the Turán number of H). The classical theorem of Erdős, Kleitman, and Rothschild states that, for every r≥3, there are 2ex(n,H)+o(n2) many Kr-free graphs with vertex set {1,…, n}. There exist (at least) three different derivations of this estimate in the literature: an inductive argument based on the Kővári-Sós-Turán theorem (and its generalisation to hypergraphs due to Erdős), a proof based on Szemerédi's regularity lemma, and an argument based on the hypergraph container theorems. In this talk, we present yet another proof of this bound that exploits connections between entropy and independence. This argument is an adaptation of a method developed in a joint work with Gady Kozma, Tom Meyerovitch, and Ron Peled that studied random metric spaces.

330pm               Jean Bertoin (University of Zürich)
Scaling exponents of step-reinforced random walks
video and slides

Abstract: Let X1, … be i.i.d. copies of some real random variable X. For any ε2, ε3, … in {0,1}, a basic algorithm introduced by H.A. Simon yields a reinforced sequence X̂1, X̂2, … as follows. If εn=0, then X̂n is a uniform random sample from X̂1, …, X̂n-1; otherwise X̂n is a new independent copy of X. The purpose of this talk is to compare the scaling exponent of the usual random walk S(n)=X1 +… + Xn with that of its step reinforced version Ŝ(n)=X̂1+… + X̂n. Depending on the tail of X and on asymptotic behavior of the sequence εj, we show that step reinforcement may speed up the walk, or at the contrary slow it down, or also does not affect the scaling exponent at all. Our motivation partly stems from the study of random walks with memory, notably the so-called elephant random walk and its variations.

26 May                           Special morning: North meets South -- Discrete Maths and Probability Downunder

930am                Catherine Greenhill (UNSW)
The small subgraph conditioning method and hypergraphs
video and slides

Abstract: The small subgraph conditioning method is an analysis of variance technique which was introduced by Robinson and Wormald in 1992, in their proof that almost all cubic graphs are Hamiltonian. The method has been used to prove many structural results about random regular graphs, mostly to show that a certain substructure is present with high probability. I will discuss some applications of the small subgraph conditioning method to hypergraphs, and describe a subtle issue which is absent in the graph setting.

11am                David Wood (Monash)
Subgraph densities in a surface

Abstract: We study the following question at the intersection of extremal and structural graph theory. Given a fixed graph H that embeds in a fixed surface Σ, what is the maximum number of copies of H in an n-vertex graph that embeds in Σ? Exact answers to this question are known for specific graphs H when Σ is the sphere. We aim for more general, albeit less precise, results. We show that the answer to the above question is Θ(nf(H)), where f(H) is a graph invariant called the flap-number' of H, which is independent of Σ. This simultaneously answers two open problems posed by Eppstein (1993). When H is a complete graph we give more precise answers. This is joint work with Tony Huynh and Gwenaël Joret [https://arxiv.org/abs/2003.13777].

19 May at 2pm               Gal Kronenberg (Oxford)
The maximum length of K_r-Bootstrap Percolation
video and slides

Abstract: How long does it take for a pandemic to stop spreading? When modelling an infection process, especially these days, this is one of the main questions that comes to mind. In this talk, we consider this question in the bootstrap percolation setting.
Graph-bootstrap percolation, also known as weak saturation, was introduced by Bollobás in 1968. In this process, we start with initial "infected" set of edges E0, and we infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges Et ⊆ E(Kn), we infect a non-infected edge e if it completes a new copy of H in G=([n] , Et ∪ {e}). A question raised by Bollobás asks for the maximum time the process can run before it stabilizes. Bollobás, Przykucki, Riordan, and Sahasrabudhe considered this problem for the most natural case where H=Kr. They answered the question for r ≤ 4 and gave a non-trivial lower bound for every r ≥ 5. They also conjectured that the maximal running time is o(n2) for every integer r. We disprove their conjecture for every r ≥ 6 and we give a better lower bound for the case r=5; in the proof we use the Behrend construction. This is a joint work with József Balogh, Alexey Pokrovskiy, and Tibor Szabó.

330pm               Eyal Lubetzky (Courant)
Maximum height of 3D Ising interfaces
video and slides

Dobrushin (1972) showed that, at low enough temperatures, the interface of the 3D Ising model - the random surface separating the plus and minus phases above and below the xy-plane - is localized: it has O(1) height fluctuations above a fixed point, and its maximum height Mn on a box of side length n is OP(log n). We study this interface and derive a shape theorem for its `pillars'' conditionally on reaching an atypically large height. We use this to analyze the maximum height Mn of the interface, and prove that at low temperature Mn/log n converges to cβ in probability. Furthermore, the sequence (Mn - E[Mn])n≥1 is tight, and even though this sequence does not converge, its subsequential limits satisfy uniform Gumbel tails bounds.
Joint work with Reza Gheissari.

12 May                           Special afternoon: Logic and Combinatorics

2pm               Tamar Ziegler (Hebrew University of Jerusalem)
Sections of high rank varieties and applications
video and slides

Abstract: I will describe some recent work with D. Kazhdan where we obtain results in algebraic geometry, inspired by questions in additive combinatorics, via analysis over finite fields. Specifically we are interested in quantitative properties of polynomial rings that are independent of the number of variables. A sample application is the following theorem : Let V be a complex vector space, P a high rank polynomial of degree d, and X the null set of P, X={v|P(v)=0}. Any function f:X→C which is polynomial of degree d on lines in X is the restriction of a degree d polynomial on V.

330pm               Anand Pillay (Notre Dame)
Approximate subgroups with bounded VC dimension.
video and slides

Abstract. This is joint with Gabe Conant. We give a structure theorem for finite subsets A of arbitrary groups G such that A has "small tripling" and "bounded VC dimension". Roughly, A will be a union of a bounded number of translates of a coset nilprogession of bounded rank and step (up to a small error).

5 May at 2pm                 Liana Yepremyan (LSE)
Ryser's conjecture and more
video and slides

Abstract: A Latin square of order n is an nxn array filled with n symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser, Brualdi and Stein from 60s which says that every Latin square of order nxn contains a transversal of order n-1. A closely related problem is 40 year old conjecture of Brouwer that every Steiner triple system of order n contains a matching of size (n-4)/3. The third problem we'd like to mention asks how many distinct symbols in Latin arrays suffice to guarantee a full transversal? In this talk we discuss a novel approach to attack these problems. Joint work with Peter Keevash, Alexey Pokrovskiy and Benny Sudakov.

330pm                Benny Sudakov (ETH Zurich)
Multidimensional Erdős-Szekeres theorem
video

Abstract: The classical Erdős-Szekeres theorem dating back almost a hundred years states that any sequence of (n-1)2+1 distinct real numbers contains a monotone subsequence of length n. This theorem has been generalised to higher dimensions in a variety of ways but perhaps the most natural one was proposed by Fishburn and Graham more than 25 years ago. They raise the problem of how large should a d-dimesional array be in order to guarantee a "monotone" subarray of size n x n x ... x n. In this talk we discuss this problem and show how to improve their original Ackerman-type bounds to at most a triple exponential. (Joint work with M. Bucic and T. Tran)

28 Apr                            Special afternoon: Random graphs and planar maps

2pm                Grégory Miermont (ENS Lyon)
The breadth-first construction of scaling limits of graphs with finite excess
video

Abstract: Random graphs with finite excess appear naturally in at least two different settings: random graphs in the critical window (aka critical percolation on regular and other classes of graphs), and unicellular maps of fixed genus. In the first situation, the scaling limit of such random graphs was obtained by Addario-Berry, Broutin and Goldschmidt based on a depth-first exploration of the graph and on the coding of the resulting forest by random walks. This idea originated in Aldous' work on the critical random graph, using instead a breadth-first search approach that seem less adapted to taking graph scaling limits. We show hat this can be done nevertheless, resulting in some new identities for quantities like the radius and the two-point function of the scaling limit. We also obtain a similar "breadth-first" construction of the scaling limit of unicellular maps of fixed genus. This is based on joint work with Sanchayan Sen.

330pm                Olivier Bernardi (Brandeis)
Percolation on triangulations, and a bijective path to Liouville quantum gravity
video and slides

Abstract: I will discuss the percolation model on planar triangulations, and present a bijection that is key to relating this model to some fundamental probabilistic objects. I will attempt to achieve several goals:
1. Present the site-percolation model on random planar triangulations.
2. Provide an informal introduction to several probabilistic objects: the Gaussian free field, Schramm-Loewner evolutions, and the Brownian map.
3. Present a bijective encoding of percolated triangulations by certain lattice paths, and explain its role in establishing exact relations between the above-mentioned objects.
This is joint work with Nina Holden, and Xin Sun.

21 Apr at 2pm                Agelos Georgakopoulos (Warwick)
The percolation density θ(p) is analytic
video and slides

Abstract: We prove that for Bernoulli bond percolation on ℤd, d≥2, the percolation density θ(p) (defined as the probability of the origin lying in an infinite cluster) is an analytic function of the parameter in the supercritical interval (p_c,1]. This answers a question of Kesten from 1981.
The proof involves a little bit of elementary complex analysis (Weierstrass M-test), a few well-known results from percolation theory (Aizenman-Barsky/Menshikov theorem), but above all combinatorial ideas. We used a new notion of contours, bounds on the number of partitions of an integer, and the inclusion-exclusion principle, to obtain a refinement of a classical argument of Peierls that settled the 2-dimensional case in 2018. More recently, we coupled these techniques with a renormalisation argument to handle all dimensions.
Joint work with Christoforos Panagiotis.

330pm                Cristina Toninelli (Paris Dauphine)
Bootstrap percolation and kinetically constrained spin models: critical time scales
video and slides

Abstract: Recent years have seen a great deal of progress in understanding the behavior of bootstrap percolation models, a particular class of monotone cellular automata. In the two dimensional lattice there is now a quite complete understanding of their evolution starting from a random initial condition, with a universality picture for their critical behavior. Here we will consider their non-monotone stochastic counterpart, namely kinetically constrained models (KCM). In KCM each vertex is resampled (independently) at rate one by tossing a p-coin iff it can be infected in the next step by the bootstrap model. In particular infection can also heal, hence the non-monotonicity. Besides the connection with bootstrap percolation, KCM have an interest in their own : when p shrinks to 0 they display some of the most striking features of the liquid/glass transition, a major and still largely open problem in condensed matter physics.

14 Apr at 2pm                Bhargav Narayanan (Rutgers)
Thresholds
video and slides

Abstract: I'll discuss our recent proof of a conjecture of Talagrand, a fractional version of the "expectation-threshold" conjecture of Kahn and Kalai. As a consequence of this result, we resolve various (heretofore) difficult problems in probabilistic combinatorics and statistical physics.

330pm                Ron Peled (Tel Aviv)
Site percolation on planar graphs and circle packings
video and slides

Abstract: Color each vertex of an infinite graph blue with probability p and red with probability 1-p, independently among vertices. For which values of p is there an infinite connected component of blue vertices? The talk will focus on this classical percolation problem for the class of planar graphs. Recently, Itai Benjamini made several conjectures in this context, relating the percolation problem to the behavior of simple random walk on the graph. We will explain how partial answers to Benjamini's conjectures may be obtained using the theory of circle packings. Among the results is the fact that the critical percolation probability admits a universal lower bound for the class of recurrent plane triangulations. No previous knowledge on percolation or circle packings will be assumed.

7 Apr at 2pm                  Louigi Addario-Berry (McGill)
Hipster random walks and their ilk
video

Abstract: I will describe how certain recursive distributional equations can be solved by using tools from numerical analysis on the convergence of approximation schemes for PDEs. This project is joint work with Luc Devroye, Hannah Cairns, Celine Kerriou, and Rivka Maclaine Mitchell.

31 Mar at 2pm                Rob Morris (IMPA)
Erdős covering systems
video and slides

Abstract: A covering system of the integers is a finite collection of arithmetic progressions whose union is the set of integers ℤ. The study of these objects was initiated in 1950 by Erdős, and over the following decades he asked a number of beautiful questions about them. Most famously, his so-called 'minimum modulus problem' was resolved in 2015 by Hough, who proved that in every covering system with distinct moduli, the minimum modulus is at most 1016.
In this talk I will describe a simple and general method of attacking covering problems that was inspired by Hough's proof. We expect that this technique, which we call the 'distortion method', will have further applications in combinatorics.
This talk is based on joint work with Paul Balister, Béla Bollobás, Julian Sahasrabudhe and Marius Tiba.