Forthcoming events in this series


Tue, 17 Nov 2020
15:30
Virtual

Random Steiner complexes and simplical spanning trees

Ron Rosenthal
(Technion)
Further Information

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

Abstract

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 $\kappa_1(G_n)$ in a random $k$-regular graph on $n$ vertices satisfies $\lim_{n \to \infty} (\kappa_1(G_n))^{1/n} = c_{1,k}$ in probability, where $c_{1,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. 

Tue, 17 Nov 2020
14:00
Virtual

Minimum weight disk triangulations and fillings

Yuval Peled
(Courant)
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 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/2\log 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.

Tue, 10 Nov 2020
15:30
Virtual

Power-law bounds for critical long-range percolation

Tom Hutchcroft
(Cambridge)
Further Information

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

Abstract

In long-range percolation on $\mathbb{Z}^d$, each potential edge $\{x,y\}$ is included independently at random with probability roughly $\beta\|x-y\|-d-\alpha$, where $\alpha > 0$ controls how long-range the model is and $\beta > 0$ is an intensity parameter. The smaller $\alpha$ is, the easier it is for very long edges to appear. We are normally interested in fixing $\alpha$ and studying the phase transition that occurs as $\beta$ 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 $\alpha$ is small: It is a theorem of Noam Berger that if $\alpha < d$ then the phase transition is continuous, meaning that there are no infinite clusters at the critical value of $\beta$. (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.

Tue, 10 Nov 2020
14:00
Virtual

Critical behavior without FKG

Vincent Beffara
(Grenoble)
Further Information

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

Abstract

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.

Tue, 03 Nov 2020
15:30
Virtual

An improvement on Łuczak's connected matchings method

Shoham Letzter
(UCL)
Further Information

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

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.

Tue, 03 Nov 2020
14:00
Virtual

Combinatorics from the zeros of polynomials

Julian Sahasrabudhe
(Cambridge)
Further Information

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

Abstract

Let $X$ be a random variable, taking values in $\{1,…,n\}$, with standard deviation $\sigma$ and let $f_X$ be its probability generating function. Pemantle conjectured that if $\sigma$ is large and $f_X$ 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.

Tue, 27 Oct 2020
15:30
Virtual

Further progress towards Hadwiger's conjecture

Luke Postle
(Waterloo)
Further Information

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

Abstract

In 1943, Hadwiger conjectured that every graph with no Kt minor is $(t-1)$-colorable for every $t\geq 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ 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 $K_t$ minor is $O(t(\log t)^\beta)$-colorable for every $\beta > 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 $K_t$ minor is $O(t (\log t)^\beta)$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^6)$-colorable.

Tue, 27 Oct 2020
14:00
Virtual

The geometry of random minimal factorizations of a long cycle

Igor Kortchemski
(Ecole Polytechnique)
Further Information

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

Abstract

We will be interested in the structure of random typical minimal factorizations of the n-cycle into transpositions, which are factorizations of $(1,\ldots,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.

Tue, 20 Oct 2020
10:30
Virtual

The threshold bias of the clique-factor game

Anita Liebenau
(UNSW)
Further Information

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

Abstract

Let $r>3$ be an integer and consider the following game on the complete graph $K_n$ for $n$ a multiple of $r$: Two players, Maker and Breaker, alternately claim previously unclaimed edges of $K_n$ such that in each turn Maker claims one and Breaker claims $b$ edges. Maker wins if her graph contains a $K_r$-factor, that is a collection of $n/r$ vertex-disjoint copies of $K_r$, and Breaker wins otherwise. In other words, we consider the $b$-biased $K_r$-factor Maker-Breaker game. We show that the threshold bias for this game is of order $n^2/(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.

Tue, 20 Oct 2020
09:00
Virtual

Scaling limits of the two- and three-dimensional uniform spanning trees

David Croydon
(Kyoto)
Further Information

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

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

Tue, 13 Oct 2020
15:30
Virtual

Speeds of hereditary properties and mutual algebricity

Caroline Terry
(Ohio State)
Further Information

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

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.

Tue, 13 Oct 2020
14:00
Virtual

The local limit of uniform spanning trees

Asaf Nachmias
(Tel Aviv)
Further Information

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

Abstract

Let $G_n$ be a sequence of finite, simple, connected, regular graphs with degrees tending to infinity and let $T_n$ be a uniformly drawn spanning tree of $G_n$. In joint work with Yuval Peres we show that the local limit of $T_n$ is the $\text{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.

Tue, 06 Oct 2020
15:30
Virtual

Liouville quantum gravity with matter central in (1,25): a probabilistic approach

Nina Holden
(ETH)
Further Information

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

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\in (-\infty,1]$. We study a discretization of LQG which makes sense for all $c\in (-\infty,25)$. Based on a joint work with Gwynne, Pfeffer, and Remy.

Tue, 06 Oct 2020
14:00
Virtual

The Schur-Erdős problem for graphs of bounded dimension

Janos Pach
(Renyi Institute)
Further Information

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

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 $2^{cm}$ 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.

Tue, 09 Jun 2020
16:30
Virtual

Replica Symmetry Breaking for Random Regular NAESAT

Allan Sly
(Princeton)
Further Information

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

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.

Tue, 09 Jun 2020
15:00
Virtual

First-order phase transitions and efficient sampling algorithms

Will Perkins
(Illinois)
Further Information

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

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 $\mathbb{Z}^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.

Tue, 09 Jun 2020
14:00
Virtual

Markov Chains for Programmable Active Matter

Dana Randall
(Georgia Tech)
Further Information

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

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.

Tue, 02 Jun 2020
15:30
Virtual

Scaling exponents of step-reinforced random walks

Jean Bertoin
(University of Zurich)
Further Information

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

Abstract

Let $X_1, \ldots$ be i.i.d. copies of some real random variable $X$. For any $\varepsilon_2, \varepsilon_3, \ldots$ in $\{0,1\}$, a basic algorithm introduced by H.A. Simon yields a reinforced sequence $\hat{X}_1, \hat{X}_2, \ldots$ as follows. If $\varepsilon_n=0$, then $\hat{X}_n$ is a uniform random sample from $\hat{X}_1, …, \hat{X}_{n-1}$; otherwise $\hat{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)=X_1 +\ldots + X_n$ with that of its step reinforced version $\hat{S}(n)=\hat{X}_1+\ldots + \hat{X}_n$. Depending on the tail of $X$ and on asymptotic behavior of the sequence $\varepsilon_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.

Tue, 02 Jun 2020
14:00
Virtual

An entropy proof of the Erdős-Kleitman-Rothschild theorem.

Wojciech Samotij
(Tel Aviv)
Further Information

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

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 $\text{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\geq3$, there are $2^{\text{ex}(n,H)+o(n2)}$ many $K_r$-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.

Tue, 26 May 2020
11:00
Virtual

Subgraph densities in a surface

David Wood
(Monash)
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 following question at the intersection of extremal and structural graph theory. Given a fixed graph $H$ that embeds in a fixed surface $\Sigma$, what is the maximum number of copies of $H$ in an $n$-vertex graph that embeds in $\Sigma$? Exact answers to this question are known for specific graphs $H$ when $\Sigma$ is the sphere. We aim for more general, albeit less precise, results. We show that the answer to the above question is $\Theta(nf(H))$, where $f(H)$ is a graph invariant called the `flap-number' of $H$, which is independent of $\Sigma$. 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]

Tue, 26 May 2020
09:30
Virtual

The small subgraph conditioning method and hypergraphs

Catherine Greenhill
(UNSW)
Further Information

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

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.

Tue, 19 May 2020
15:30
Virtual

Maximum height of 3D Ising interfaces

Eyal Lubetzky
(Courant Institute)
Further Information

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

Abstract

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 $M_n$ on a box of side length $n$ is $O_P(\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 $M_n$ of the interface, and prove that at low temperature $M_n/\log n$ converges to $c\beta$ in probability. Furthermore, the sequence $(M_n - E[M_n])_{n\geq 1}$ is tight, and even though this sequence does not converge, its subsequential limits satisfy uniform Gumbel tails bounds.
Joint work with Reza Gheissari.

Tue, 19 May 2020
14:00
Virtual

The maximum length of K_r-Bootstrap Percolation

Gal Kronenberg
(Oxford)
Further Information

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

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 $E_0$, and we infect new edges according to a predetermined rule. Given a graph $H$ and a set of previously infected edges $E_t \subseteq E(Kn)$, we infect a non-infected edge $e$ if it completes a new copy of $H$ in $G=([n] , E_t \cup \{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=K_r$. They answered the question for $r \leq 4$ and gave a non-trivial lower bound for every $r \geq 5$. They also conjectured that the maximal running time is $o(n^2)$ for every integer $r$. We disprove their conjecture for every $r \geq 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ó.

Tue, 12 May 2020
15:30
Virtual

Approximate subgroups with bounded VC dimension

Anand Pillay
(Notre Dame)
Further Information

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

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

Tue, 12 May 2020
14:00
Virtual

Sections of high rank varieties and applications

Tamar Ziegler
(Hebrew University of Jerusalem)
Further Information

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

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 \mid P(v)=0\}$. Any function $f:X\to C$ which is polynomial of degree $d$ on lines in $X$ is the restriction of a degree $d$ polynomial on $V$.