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!
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.
25 Feb
2pm
Rachel Greenfeld (Northwestern University)
TBA
Abstract: TBA
330pm
Dhruv Mubayi (University of Illinois at Chicago)
TBA
Abstract: TBA
Here is the list of past talks, with links to individual youtube videos and slides/notes where available. (The talks are also gathered together on our youtube channel.)
26 Nov
2pm
Élie Aïdékon (Fudan)
Boundedness of discounted tree sums
video
and
slides
Abstract: Let (V(u)) be a branching random walk and (η(u)) be i.i.d marks on the vertices. To each path ξ of the tree, we associate the discounted sum D(ξ) which is the sum of the exp(V(u))ηu along the path. We study conditions under which supξ D(ξ) is finite, answering an open question of Aldous and Bandyopadhyay. We will see that this problem is related to the study of the local time process of the branching random walk along a path. It is a joint work with Yueyun Hu and Zhan Shi.
330pm
Sergey Norin (McGill)
Optimizing the Campos-Griffiths-Morris-Sahasrabudhe upper bound on Ramsey numbers
video
and slides
Abstract:
In a recent breakthrough Campos, Griffiths, Morris and Sahasrabudhe obtained
the first exponential improvement of the upper bound on the classical Ramsey
numbers since 1935. I will outline a reinterpretation of their proof, replacing the underlying
book algorithm with a simple inductive statement. In particular, I will
present a complete proof of of an improved upper bound on the off-diagonal Ramsey numbers and describe
the main steps involved in improving their upper bound for the diagonal
Ramsey numbers to R(k,k)≤(3.8)k for sufficiently large k.
Based on joint work with Parth Gupta, Ndiame Ndiaye, and Louis Wei.
4 Jun
2pm
Shankar Bhamidi (UNC, Chapel Hill)
Living discreetly but thinking continuously: Dynamic networks
and stochastic approximation
video
and
slides
Abstract: Models for networks that evolve and change over time are
ubiquitous in a host of domains including modeling social networks,
understanding the evolution of systems in proteomics, the study of the
growth and spread of epidemics etc.
This talk will give a brief summary of three recent findings in this
area where stochastic approximation techniques play an important role:
(a) Understanding the effect and detectability of change point in the
evolution of the system dynamics.
(b) Reconstructing the initial "seed" that gave rise to the current
network, sometimes referred to as Network Archeology.
(c) The disparity in the behavior of different centrality measures
such as degree and page rank centrality for measuring popularity in
settings where there are vertices of different types such as
majorities and minorities as well as insight analyzing such problems
give for at first sight unrelated issues such as sampling rare groups
within the network.
The main goal will to be convey unexpected findings in each of these
three areas and in particular the "unreasonable effectiveness" of
continuous time branching processes.
330pm
Jacques Verstraete (UCSD)
Recent progress in Ramsey Theory
video
and
slides
Abstract:
The organizing principle of Ramsey theory is that in large mathematical structures, there are relatively
large substructures which are homogeneous. This is quantified in combinatorics by the notion of Ramsey numbers
r(s,t), which denote the minimum N such that in any red-blue coloring of the edges of
the complete graph on N vertices, there exists a red complete graph on s vertices or a blue complete graph on t vertices.
While the study of Ramsey numbers goes back almost one hundred years, to early papers of Ramsey and Erdős and Szekeres, the long-standing conjecture of Erdős that r(s,t) has order of magnitude close to ts - 1 as t → ∞ remains open in general.
It took roughly sixty years before the order of magnitude of r(3,t) was determined by Jeong Han Kim, who showed r(3,t) has order of magnitude t2/log t as t → ∞. In this talk, we discuss a variety of new techniques, including the modern method of containers, which lead to a proof of the conjecture of Erdős that r(4,t) is of order close to t3.
One of the salient philosophies in our approach is that good Ramsey graphs hide inside pseudorandom graphs, and the long-standing emphasis of tackling Ramsey theory from the point of view of purely random graphs is superseded by pseudorandom graphs. Via these methods, we also come close to determining the well-studied related quantities known as Erdős-Rogers functions and discuss related hypergraph coloring problems and applications.
Joint work in part with Sam Mattheus, Dhruv Mubayi and David Conlon.
7 May
2pm
Guillaume Chapuy (IRIF)
Random triangulations of surfaces, and the high-genus regime
video
and
slides
Abstract: I will talk about the behaviour of random maps on surfaces (for example, random triangulations) of given genus, when their size tends to infinity. Such questions can be asked from the viewpoint of the local behaviour (Benjamini-Schramm convergence) or global behaviour (diameter, Gromov Hausdorff convergence), and in both cases, much combinatorics is involved. I will survey the landmark results for the case of fixed genus, and state very recent results in which we manage to address the "high genus" regime, when the genus grows proportionally to the size -- for this regime we establish isoperimetric inequalities and prove the long-suspected fact that the diameter is logarithmic with high probability. Based on joint work with Thomas Budzinski and Baptiste Louf.
330pm
Irit Dinur (Weizmann Institute of Science)
Coboundary expansion and applications
Abstract:
Coboundary expansion is a notion introduced by Linial and Meshulam, and by Gromov that combines combinatorics topology and linear algebra.
Kaufman and Lubotzky observed its relation to "Property testing", and in recent years it has found several applications in theoretical computer science, including for error correcting codes (both classical and quantum), for PCP agreement tests, and even for studying polarization in social networks.
In the talk I will introduce this notion and some of its applications. No prior knowledge is assumed, of course.
27 Feb
2pm
Duncan Dauvergne (Toronto)
Geodesics networks in the directed landscape
video
Abstract: The directed landscape is a random directed metric on the plane that is the scaling limit for models in the KPZ universality class (i.e. last passage percolation on ℤ^2, TASEP). In this metric, typical pairs of points are connected by a unique geodesic. However, certain exceptional pairs are connected by more exotic geodesic networks. The goal of this talk is to describe a full classification for these exceptional pairs.
330pm
István Tomon (Umeå)
Discrepancy of graphs
video
and
slides
Abstract: The positive discrepancy of a graph $G$ is the maximum surplus of edges in an induced subgraph of $G$ compared to its expected size. This quantity is closely related to other well studied parameters, such as the minimum bisection and the spectral gap. I will talk about the extremal behavior of the positive discrepancy among graphs with given number of vertices and average degree, uncovering a surprising pattern. This leads to an almost complete solution of a problem of Alon on the minimum bisection and let's us extend the Alon-Boppana bound on the second eigenvalue to dense graphs. Joint work with Eero Räty and Benny Sudakov.
23 Jan
2pm
Augusto Teixeira (IMPA)
Sharpness of the phase transition for interlacements percolation
video
and
slides
Abstract:
In this talk we will review the problem of sharpness in percolation, tracing
its origins back to the seminal works of Menshikov, Grimmett-Marstrand and
Aizenman-Barsky, which successfully settled the question in the context of
Bernoulli independent percolation. Then we will present some recent
advancements on the field, which have opened up the possibility of
investigating dependent percolation models. Special emphasis will be given
to the Interpolation technique, which has proved itself very effective. In
particular, it has been used to establish the sharpness for Interlacements
Percolation, a model introduced by Sznitman with notoriously intricate
dependencies.
This talk is based on a joint work with Duminil-Copin, Goswami, Rodriguez
and Severo
330pm
Nina Kamčev (University of Zagreb)
Paths in random temporal graphs
video
and
slides
Abstract:
Random temporal graphs are a version of the classical Erdős-Rényi random graph G(n,p) where additionally, each edge has a distinct random time stamp, and connectivity is constrained to sequences of edges with increasing time stamps. We are interested in the asymptotics for the distances in such graphs, mostly in the regime of interest where the average degree np is of order log n ('near' the phase transition).
More specifically, we will discuss the asymptotic lengths of increasing paths: the lengths of the shortest and longest paths between typical vertices, as well as the maxima between any two vertices; this also covers the (temporal) diameter. In the regime np ≫ log n, longest increasing paths were studied by Angel, Ferber, Sudakov and Tassion.
The talk contains joint work with Nicolas Broutin and Gábor Lugosi.
14 Nov
2pm
Paul Bastide (LaBRI/TU Delft)
Skipless chain decompositions and improved poset saturation bounds
video
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
video
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)
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
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)
Further progress towards Hadwiger's conjecture
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.
Joint work with Rajko Nenadov.
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 Ŝ(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.