Forthcoming events in this series

Tue, 14 Jun 2022

14:00 - 15:00
L4

### Resolution of the Erdős-Sauer problem on regular subgraphs

Benny Sudakov
(ETH Zurich)
Abstract

In this talk we discuss solution of the well-known problem of Erdős and Sauer from 1975 which asks for the maximum number of edges an $n$-vertex graph can have without containing a $k$-regular subgraph, for some fixed integer $k\geq 3$. We prove that any $n$-vertex graph with average degree at least $C_k\log\log n$ contains a $k$-regular subgraph. This matches the lower bound of Pyber, Rödl and Szemerédi and substantially
improves an old result of Pyber, who showed that average degree at least $C_k\log n$ is enough.

Our method can also be used to settle asymptotically a problem raised by Erdős and Simonovits in 1970 on almost regular subgraphs of sparse graphs and to make progress on the well-known question of Thomassen from 1983 on finding subgraphs with large girth and large average degree.

Joint work with Oliver Janzer

Tue, 07 Jun 2022

16:30 - 17:30
Virtual

### Thresholds

Jinyoung Park
(Stanford University)
Further Information

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

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.

Tue, 07 Jun 2022

03:00 - 04:00
Online

### Infinite-bin model and the longest increasing path in an Erdős-Rényi graph

Bastien Mallein
(Sorbonne Université - Université de Paris)
Further Information

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

Abstract

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.

Wed, 01 Jun 2022

10:30 - 17:30
L2

### One-Day Meeting in Combinatorics

Multiple
Further Information

The speakers are Gabor Lugosi (Barcelona), Gal Kronenberg (Oxford), Paul Balister (Oxford), Julia Wolf (Cambridge), and David Wood (Monash). Please see the event website for further details including titles, abstracts, and timings. Anyone interested is welcome to attend, and no registration is required.

Tue, 24 May 2022

14:00 - 15:00
L3

### Size-Ramsey numbers of graphs with maximum degree three

Nemanja Draganić
(ETH Zurich)
Abstract

The size-Ramsey number $\hat{r}(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have, such that for any red/blue coloring of $G$, there is a monochromatic copy of $H$ in $G$. Recently, Conlon, Nenadov and Trujić showed that if $H$ is a graph on $n$ vertices and maximum degree three, then $\hat{r}(H) = O(n^{8/5})$, improving upon the bound of $n^{5/3 + o(1)}$ by Kohayakawa, Rödl, Schacht and Szemerédi. In our paper, we show that $\hat{r}(H)\leq n^{3/2+o(1)}$. While the previously used host graphs were vanilla binomial random graphs, we prove our result by using a novel host graph construction.
We also discuss why our bound is a natural barrier for the existing methods.
This is joint work with Kalina Petrova.

Tue, 17 May 2022

15:30 - 16:30
Virtual

### Threshold for Steiner triple systems

Mehtaab Sawhney
(MIT)
Further Information

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

Abstract

We prove that with high probability $\mathbb{G}^{(3)}(n,n^{-1+o(1)})$ contains a spanning Steiner triple system for $n\equiv 1,3\pmod{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.

Tue, 17 May 2022

14:00 - 15:00
Virtual

### Unicellular maps and hyperbolic surfaces in high genus

Baptiste Louf
(Uppsala University)
Further Information

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

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.

Tue, 10 May 2022

14:00 - 15:00
L4

### A Ramsey problem in blowups of graphs

António Girão
(Oxford)
Abstract

For graphs $G$ and $H$, we say $G \stackrel{r}{\to} H$ if every $r$-colouring of the edges of $G$ contains a monochromatic copy of $H$. Let $H[t]$ denote the $t$-blowup of $H$. The blowup Ramsey number $B(G \stackrel{r}{\to} H;t)$ is the minimum $n$ such that $G[n] \stackrel{r}{\to} H[t]$. Fox, Luo and Wigderson refined an upper bound of Souza, showing that, given $G$, $H$ and $r$ such that $G \stackrel{r}{\to} H$, there exist constants $a=a(G,H,r)$ and $b=b(H,r)$ such that for all $t \in \mathbb{N}$, $B(G \stackrel{r}{\to} H;t) \leq ab^t$. They conjectured that there exist some graphs $H$ for which the constant $a$ depending on $G$ is necessary. We prove this conjecture by showing that the statement is true when $H$ is a $3$-chromatically connected, which includes all cliques on $3$ or more vertices. We are also able to show perhaps surprisingly that for any forest $F$ there is $f(F,t)$ such that  for any $G \stackrel{r}{\to} H$, $B(G \stackrel{r}{\to} H;t)\leq f(F,t)$ i.e. the function does not depend on the ground graph $G$. This is joint work with Robert Hancock.

Tue, 03 May 2022

14:00 - 15:00
L4

### The structure of planar graphs

David Wood
(Monash University)
Abstract

This talk is about the global structure of planar graphs and other more general graph classes. The starting point is the Lipton-Tarjan separator theorem, followed by Baker's decomposition of a planar graph into layers with bounded treewidth. I will then move onto layered treewidth, which is a more global version of Baker's decomposition. Layered treewidth is a precursor to the recent development of row treewidth, which has been the key to solving several open problems. Finally, I will describe generalisations for arbitrary minor-closed classes.

Tue, 15 Mar 2022
14:00
C6

### Colouring locally sparse graphs with the first moment method

Eoin Hurley
(Heidelberg University)
Abstract

A classical theorem of Molloy and Johansson states that if a graph is triangle free and has maximum degree at most $\Delta$, then it has chromatic number at most $\frac{\Delta}{\log \Delta}$. This was extended to graphs with few edges in their neighbourhoods by Alon-Krivelevich and Sudakov, and to list chromatic number by Vu. I will give a full and self-contained proof of these results that relies only on induction and the first moment method.

Tue, 01 Mar 2022
14:00
L4

### Independent sets in random subgraphs of the hypercube

Gal Kronenberg
(Oxford)
Abstract

Independent sets in bipartite regular graphs have been studied extensively in combinatorics, probability, computer science and more. The problem of counting independent sets is particularly interesting in the d-dimensional hypercube $\{0,1\}^d$, motivated by the lattice gas hardcore model from statistical physics. Independent sets also turn out to be very interesting in the context of random graphs.

The number of independent sets in the hypercube $\{0,1\}^d$ was estimated precisely by Korshunov and Sapozhenko in the 1980s and recently refined by Jenssen and Perkins.

In this talk we will discuss new results on the number of independent sets in a random subgraph of the hypercube. The results extend to the hardcore model and rely on an analysis of the antiferromagnetic Ising model on the hypercube.

This talk is based on joint work with Yinon Spinka.

Tue, 22 Feb 2022
14:00
C2

### Minimum degree stability and locally colourable graphs

Freddie Illingworth
(Oxford)
Abstract

We tie together two natural but, a priori, different themes. As a starting point consider Erdős and Simonovits's classical edge stability for an $(r + 1)$-chromatic graph $H$. This says that any $n$-vertex $H$-free graph with $(1 − 1/r + o(1)){n \choose 2}$ edges is close to (within $o(n^2)$ edges of) $r$-partite. This is false if $1 − 1/r$ is replaced by any smaller constant. However, instead of insisting on many edges, what if we ask that the $n$-vertex graph has large minimum degree? This is the basic question of minimum degree stability: what constant $c$ guarantees that any $n$-vertex $H$-free graph with minimum degree greater than $cn$ is close to $r$-partite? $c$ depends not just on chromatic number of $H$ but also on its finer structure.

Somewhat surprisingly, answering the minimum degree stability question requires understanding locally colourable graphs -- graphs in which every neighbourhood has small chromatic number -- with large minimum degree. This is a natural local-to-global colouring question: if every neighbourhood is big and has small chromatic number must the whole graph have small chromatic number? The triangle-free case has a rich history. The more general case has some similarities but also striking differences.

Tue, 08 Feb 2022
14:00
Virtual

### Large hypergraphs without tight cycles

Barnabas Janzer
(Cambridge)
Abstract

An $r$-uniform tight cycle of length $k>r$ is a hypergraph with vertices $v_1,\ldots,v_k$ and edges $\{v_i,v_{i+1},…,v_{i+r-1}\}$ (for all $i$), with the indices taken modulo $k$. Sós, and independently Verstraëte, asked the following question: how many edges can there be in an $n$-vertex $r$-uniform hypergraph if it contains no tight cycles of any length? In this talk I will review some known results, and present recent progress on this problem.

Tue, 01 Feb 2022
14:00
Virtual

### Recoloring version of Hadwiger's conjecture

Clément Legrand-Duchesne
(LaBRI Bordeaux)
Abstract

Las Vergnas and Meyniel conjectured in 1981 that all the $t$-colorings of a $K_t$-minor free graph are Kempe equivalent. This conjecture can be seen as a reconfiguration counterpoint to Hadwiger's conjecture, although it neither implies it or is implied by it. We prove that for all positive $\epsilon$, for all large enough $t$, there exists a graph with no $K_{(2/3 + \epsilon)t}$ minor whose $t$-colorings are not all Kempe equivalent, thereby strongly disproving this conjecture, along with two other conjectures of the same paper.

Tue, 25 Jan 2022
14:00
Virtual

### Induced Poset Saturation

Maria-Romina Ivan
(Cambridge)
Abstract

Given a fixed poset $\mathcal P$, we say that a family $\mathcal F$ of subsets of $[n]$ is $\mathcal P$-free if it does not contain an (induced) copy of $\mathcal P$. And we say that $F$ is $\mathcal P$-saturated if it is maximal $\mathcal P$-free. How small can a $\mathcal P$-saturated family be? The smallest such size is the induced saturation number of $\mathcal P$, $\text{sat}^*(n, \mathcal P)$. Even for very small posets, the question of the growth speed of $\text{sat}^*(n,\mathcal P)$ seems to be hard. We present background on this problem and some recent results.

Tue, 30 Nov 2021
14:00
L6

### The n-queens problem

Candy Bowtell
(Oxford/Birmingham)
Abstract

The $n$-queens problem asks how many ways there are to place $n$ queens on an $n \times n$ chessboard so that no two queens can attack one another, and the toroidal $n$-queens problem asks the same question where the board is considered on the surface of a torus. Let $Q(n)$ denote the number of $n$-queens configurations on the classical board and $T(n)$ the number of toroidal $n$-queens configurations. The toroidal problem was first studied in 1918 by Pólya who showed that $T(n)>0$ if and only if $n \equiv 1,5 \mod 6$. Much more recently Luria showed that $T(n)\leq ((1+o(1))ne^{-3})^n$ and conjectured equality when $n \equiv 1,5 \mod 6$. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) $n \equiv 1,5 \mod 6$. We also show that $Q(n)\geq((1+o(1))ne^{-3})^n$ for all $n \in \mathbb{N}$ which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both $Q(n)$ and $T(n)$.

In this talk we'll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a $4$-partite $4$-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost' configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.

This is joint work with Peter Keevash.

Tue, 23 Nov 2021
14:00
Virtual

### PageRank on directed preferential attachment graph

Mariana Olvera-Cravioto
(UNC Chapel Hill)
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.

Tue, 16 Nov 2021
14:00
L6

### The singularity probability of a random symmetric matrix is exponentially small

Matthew Jenssen
Abstract

Let $A$ be drawn uniformly at random from the set of all $n \times n$ symmetric matrices with entries in $\{-1,1\}$. We show that $A$ is singular with probability at most $e^{-cn}$ for some absolute constant $c>0$, thereby resolving a well-known conjecture. This is joint work with Marcelo Campos, Marcus Michelen and Julian Sahasrabudhe.

Tue, 09 Nov 2021
14:00
Virtual

Matija Bucić
(Princeton/IAS)
Tue, 02 Nov 2021
14:00
L4

### A nonabelian Brunn-Minkowski inequality

Yifan Jing
(Oxford)
Abstract

Henstock and Macbeath asked in 1953 whether the Brunn-Minkowski inequality can be generalized to nonabelian locally compact groups; questions in the same line were also asked by Hrushovski, McCrudden, and Tao. We obtain here such an inequality and prove that it is sharp for helix-free locally compact groups, which includes real linear algebraic groups, Nash groups, semisimple Lie groups with finite center, solvable Lie groups, etc. If time allows I will also discuss some applications of this result. (Joint with Chieu-Minh Tran and Ruixiang Zhang)

Tue, 26 Oct 2021
14:00
Virtual

### Friendly bisections of random graphs

Ashwin Sah
(MIT)
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

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.

Tue, 19 Oct 2021
14:00
L5

### Sharp stability of the Brunn-Minkowski inequality

Peter Van Hintum
(Oxford)
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.

Tue, 12 Oct 2021
14:00
Virtual

### Generalized birthday problem for October 12

Sumit Mukherjee
(Columbia)
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.

Tue, 01 Jun 2021
15:30
Virtual

### Random Determinants and the Elastic Manifold

Gérard Ben Arous
(Courant Institute)
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.

Tue, 01 Jun 2021
14:30
Virtual

### Invertibility of random square matrices

Konstantin Tikhomirov
(Georgia Tech)
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.