Past 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
4 May 2021
15:30
Jean-François Le Gall

Further Information: 

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

Abstract

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.

  • Combinatorial Theory Seminar
4 May 2021
14:00
Annika Heckel

Further Information: 

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

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 $n^{1/2}$. Alon improved this slightly to $n^{1/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 $n^{1/2-o(1)}$ consecutive values.
I will also discuss the Zigzag Conjecture, made recently by Bollobás, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between $n^{1/4+o(1)}$ and $n^{1/2+o(1)}$, depending on $n$.
Joint work with Oliver Riordan.

  • Combinatorial Theory Seminar

Pages