Forthcoming events in this series

Tue, 22 Nov 2022

17:00 - 18:00
Virtual

### Percolation on finite transitive graphs

Philip Easo
(Caltech)
Further Information

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

Abstract

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.

Tue, 22 Nov 2022

15:30 - 16:30
Virtual

### Hypergraph Matchings Avoiding Forbidden Submatchings

Michelle Delcourt
(Toronto Metropolitan University)
Further Information

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

Abstract

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.

Tue, 15 Nov 2022

14:00 - 15:00
L5

### Unavoidable order-size pairs in graphs and hypergraphs

Maria Axenovich
(KIT)
Abstract

A graph has a pair $(m,f)$ if it has an induced subgraph on $m$ vertices and $f$ edges. We write $(n,e)\rightarrow (m,f)$  if any graph on $n$ vertices and $e$ edges has a pair $(m,f)$.  Let  $$S(n,m,f)=\{e: ~(n,e)\rightarrow (m,f)\} ~{\rm and}$$     $$\sigma(m,f) = \limsup_{n\rightarrow \infty}\frac{ |S(n,m,f)|}{\binom{n}{2}}.$$ These notions were first introduced and investigated by Erdős, Füredi, Rothschild, and Sós. They found five pairs $(m,f)$ with  $\sigma(m,f)=1$ and showed that for all other pairs $\sigma(m,f)\leq 2/3$.  We extend these results in two directions.

First, in a joint work with Weber, we show that not only $\sigma(m,f)$ can be zero, but also $S(n,m,f)$  could be empty for some pairs $(m,f)$ and any sufficiently large $n$. We call such pairs $(m,f)$ absolutely avoidable.

Second, we consider a natural analogue $\sigma_r(m,f)$ of $\sigma(m,f)$ in the setting of $r$-uniform hypergraphs.  Weber showed that for any $r\geq 3$ and  $m>r$,  $\sigma_r(m,f)=0$ for most values of $f$.  Surprisingly, it was not immediately clear whether there are nontrivial pairs $(m,f)$,  $(f\neq 0$, $f\neq \binom{m}{r}$,  $r\geq 3$),  for which $\sigma_r(m,f)>0$. In a joint work with Balogh, Clemen, and Weber we show that $\sigma_3(6,10)>0$ and conjecture that in the $3$-uniform case $(6,10)$ is the only such pair.

Tue, 08 Nov 2022

14:00 - 15:00
L5

### On the Ryser-Buraldi-Stein conjecture

Richard Montgomery
(University of Warwick)
Abstract

A Latin square of order n is an n by n grid filled with n different symbols so that every symbol occurs exactly once in each row and each column, while a transversal in a Latin square is a collection of cells which share no row, column or symbol. The Ryser-Brualdi-Stein conjecture states that every Latin square of order n should have a transversal with n-1 elements, and one with n elements if n is odd. In 2020, Keevash, Pokrovskiy, Sudakov and Yepremyan improved the long-standing best known bounds on this conjecture by showing that a transversal with n-O(log n/loglog n) elements exists in any Latin square of order n. In this talk, I will discuss how to show, for large n, that a transversal with n-1 elements always exists.

Tue, 01 Nov 2022

14:00 - 15:00
L5

### Generating random regular graphs quickly

Oliver Riordan
(Oxford University)
Abstract

A random $d$-regular graph is just a $d$-regular simple graph on $[n]=\{1,2,\ldots,n\}$ chosen uniformly at random from all such graphs. This model, with $d=d(n)$, is one of the most natural random graph models, but is quite tricky to work with/reason about, since actually generating such a graph is not so easy. For $d$ constant, Bollobás's configuration model works well; for larger $d$ one can combine this with switching arguments pioneered by McKay and Wormald. I will discuss recent progress with Nick Wormald, pushing linear-time generation up to $d=o(\sqrt{n})$. One ingredient is reciprocal rejection sampling, a trick for 'accepting' a certain graph with a probability proportional to $1/N(G)$, where $N(G)$ is the number of certain configurations in $G$. The trick allows us to do this without calculating $N(G)$, which would take too long.

Tue, 25 Oct 2022

17:00 - 18:00
Virtual

### A tale of two balloons

Yinon Spinka
(UBC)
Further Information

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

Abstract

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.

Tue, 25 Oct 2022

15:30 - 16:30
Virtual

### Average degree and girth

Rose McCarty
(Princeton University)
Further Information

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

Abstract

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 $K_{t,t}$-free bipartite graphs. Moreover, we discuss consequences to tau-boundedness, which is an analog of chi-boundedness.

Tue, 18 Oct 2022

14:00 - 15:00
L5

### Improved bounds for 1-independent percolation on $\mathbb{Z}^n$

Paul Balister & Michael Savery
(Oxford University)
Abstract

A 1-independent bond percolation model on a graph $G$ is a probability distribution on the spanning subgraphs of $G$ in which, for all vertex-disjoint sets of edges $S_1$ and $S_2$, the states (i.e. present or not present) of the edges in $S_1$ are independent of the states of the edges in $S_2$. Such models typically arise in renormalisation arguments applied to independent percolation models, or percolation models with finite range dependencies. A 1-independent model is said to percolate if the random subgraph has an infinite component with positive probability. In 2012 Balister and Bollobás defined $p_{\textrm{max}}(G)$ to be the supremum of those $p$ for which there exists a 1-independent bond percolation model on $G$ in which each edge is present in the random subgraph with probability at least $p$ but which does not percolate. A fundamental and challenging problem in this area is to determine, or give good bounds on, the value of $p_{\textrm{max}}(G)$ when $G$ is the lattice graph $\mathbb{Z}^2$. Since $p_{\textrm{max}}(\mathbb{Z}^n)\leq p_{\textrm{max}}(\mathbb{Z}^{n-1})$, it is also of interest to establish the value of $\lim_{n\to\infty}p_{\textrm{max}}(\mathbb{Z}^n)$.

In this talk we will present a significantly improved upper bound for this limit as well as improved upper and lower bounds for $p_{\textrm{max}}(\mathbb{Z}^2)$. We will also show that with high confidence we have $p_{\textrm{max}}(\mathbb{Z}^n)<p_{\textrm{max}}(\mathbb{Z}^2)$ for large $n$ and discuss some open problems concerning 1-independent models on other graphs.

This is joint work with Tom Johnston and Alex Scott.

Tue, 11 Oct 2022
14:00
L5

### Sets with small doubling in R^k and Z^k

Marius Tiba
(Oxford University)
Abstract

In this talk we explore structural results about sets with small doubling in k dimensions. We start in the continuous world with a sharp stability result for the Brunn-Minkowski inequality conjectured by Figalli and Jerison and work our way to the discrete world, where we discuss the natural extension: we show that non-degenerate sets in Z^k with doubling close to 2^k are close to convex progressions i.e. convex sets intersected with a sub-lattice. This talk is based on joint work with Peter van Hintum and Hunter Spink.

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.