Past Combinatorial Theory Seminar

19 October 2021
14:00
Peter Van Hintum
Abstract

I'll consider recent results concerning the stability of the classic Brunn-Minkowski inequality. In particular, I will focus on the linear stability for homothetic sets. Resolving a conjecture of Figalli and Jerison, we showed there are constants $C,d>0$ depending only on $n$ such that for every subset $A$ of $\mathbb{R}^n$ of positive measure, if $|(A+A)/2 - A| \leq d |A|$, then $|co(A) - A| \leq C |(A+A)/2 - A|$ where $co(A)$ is the convex hull of $A$. The talk is based on joint work with Hunter Spink and Marius Tiba.

  • Combinatorial Theory Seminar
12 October 2021
14:00
Sumit Mukherjee

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

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 $G_n$ on $n$ vertices, color each vertex with one of $c=c_n$ 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.

  • Combinatorial Theory Seminar
1 June 2021
15:30
Gérard Ben Arous

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

Abstract

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.

  • Combinatorial Theory Seminar
1 June 2021
14:30
Konstantin Tikhomirov

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details. Joint with the Random Matrix Theory Seminar.

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.

  • Combinatorial Theory Seminar
25 May 2021
15:30
Michael Krivelevich

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

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 $G_{n,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 $[\omega(1), (1-o(1))L_{\max}(G)]$, where $L_{\max}(G)$ is the length of a longest cycle (the circumference) of $G$. For the case of random $d$-regular graphs, $d\geq 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\geq 3$. Similar results are obtained also for the supercritical case $G(n,(1+\epsilon)/n)$, and for random directed graphs.
A joint work with Yahav Alon and Eyal Lubetzky.

  • Combinatorial Theory Seminar
25 May 2021
14:00
Vincent Tassion

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

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.

  • Combinatorial Theory Seminar
18 May 2021
15:15
Amedeo Sgueglia

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

Abstract

We study the model of randomly perturbed dense graphs, which is the union of any $n$-vertex graph $G_\alpha$ with minimum degree at least $\alpha 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_\alpha \cup 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.

  • Combinatorial Theory Seminar
18 May 2021
14:00
Mihyun Kang

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

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 Erdos-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.

  • Combinatorial Theory Seminar
11 May 2021
15:00
Cécile Mailler

Further Information: 

Part of the Oxford Discrete Maths and Probability Seminar, held via Zoom. Please see the seminar website for details.

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.

  • Combinatorial Theory Seminar

Pages