Forthcoming events in this series

Tue, 07 Mar 2023

15:30 - 16:30
Virtual

Correlated stochastic block models: graph matching and community recovery

Miklos Racz
(Northwestern University)
Further Information

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

Abstract

I will discuss statistical inference problems on edge-correlated stochastic block models. We determine the information-theoretic threshold for exact recovery of the latent vertex correspondence between two correlated block models, a task known as graph matching. As an application, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. Furthermore, we obtain the precise threshold for exact community recovery using multiple correlated graphs, which captures the interplay between the community recovery and graph matching tasks. This is based on joint work with Julia Gaudio and Anirudh Sridhar.

Tue, 07 Mar 2023

14:00 - 15:00
Virtual

A loglog step towards the Erdős-Hajnal conjecture

Paul Seymour
(Princeton)
Further Information

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

Abstract

In 1977, Erdős and Hajnal made the conjecture that, for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ has a clique or stable set of size at least $|G|^c$; and they proved that this is true with $|G|^c$ replaced by $2^{c\sqrt{\log |G|}}$. Until now, there has been no improvement on this result (for general $H$). We recently proved a strengthening: that for every graph $H$, there exists $c>0$ such that every $H$-free graph $G$ with $|G|\ge 2$ has a clique or stable set of size at least $2^{c\sqrt{\log |G| \log\log|G|}}$. This talk will outline the proof. Joint work with Matija Bucić, Tung Nguyen and Alex Scott.

Tue, 28 Feb 2023

14:00 - 15:00
L4

Some combinatorial applications of guided random processes

Peter Keevash
(Oxford University)
Abstract

Random greedy algorithms became ubiquitous in Combinatorics after Rödl's nibble (semi-random method), which was repeatedly refined for various applications, such as iterative graph colouring algorithms (Molloy-Reed) and lower bounds for the Ramsey number $R(3,t)$ via the triangle-free process (Bohman-Keevash / Fiz Pontiveros-Griffiths-Morris). More recently, when combined with absorption, they have played a key role in many existence and approximate counting results for combinatorial structures, following a paradigm established by my proofs of the Existence of Designs and Wilson's Conjecture on the number of Steiner Triple Systems. Here absorption (converting approximate solutions to exact solutions) is generally the most challenging task, which has spurred the development of many new ideas, including my Randomised Algebraic Construction method, the Kühn-Osthus Iterative Absorption method and Montgomery's Addition Structures (for attacking the Ryser-Brualdi-Stein Conjecture). The design and analysis of a suitable guiding mechanism for the random process can also come with major challenges, such as in the recent proof of Erdős' Conjecture on Steiner Triple Systems of high girth (Kwan-Sah-Sawhney-Simkin). This talk will survey some of this background and also mention some recent results on the Queens Problem (Bowtell-Keevash / Luria-Simkin / Simkin) and the Existence of Subspace Designs (Keevash-Sah-Sawhney). I may also mention recent solutions of the Talagrand / Kahn-Kalai Threshold Conjectures (Frankston-Kahn-Narayanan-Park / Park-Pham) and thresholds for Steiner Triple Systems / Latin Squares (Keevash / Jain-Pham), where the key to my proof is constructing a suitable spread measure via a guided random process.

Tue, 21 Feb 2023

14:00 - 15:00
L4

Hamilton decompositions of regular bipartite tournaments

Bertille Granet
(Heidelberg University)
Abstract

A regular bipartite tournament is an orientation of a complete balanced bipartite graph $K_{2n,2n}$ where every vertex has its in- and outdegree both equal to $n$. In 1981, Jackson conjectured that any regular bipartite tournament can be decomposed into Hamilton cycles. We prove this conjecture for sufficiently large $n$. Along the way, we also prove several further results, including a conjecture of Liebenau and Pehova on Hamilton decompositions of dense bipartite digraphs.

Tue, 14 Feb 2023

14:00 - 15:00
L4

Approximation of Boolean solution sets to polynomial conditions on finite prime fields

Thomas Karam
(University of Oxford)
Abstract

Let $p \ge 3$ be a prime integer. The density of a non-empty solution set of a system of affine equations $L_i(x) = b_i$, $i=1,\dots,k$ on a vector space over the field $\mathbb{F}_p$ is determined by the dimension of the linear subspace $\langle L_1,\dots,L_k \rangle$, and tends to $0$ with the dimension of that subspace. In particular, if the solution set is dense, then the system of equations contains at most boundedly many pairwise distinct linear forms. In the more general setting of systems of affine conditions $L_i(x) \in E_i$ for some strict subsets $E_i$ of $\mathbb{F}_p$ and where the solution set and its density are taken inside $S^n$ for some non-empty subset $S$ of $\mathbb{F}_p$ (such as $\{0,1\}$), we can however usually find subsets of $S^n$ with density at least $1/2$ but such that the linear subspace $\langle L_1,\dots,L_k \rangle$ has arbitrarily high dimension. We shall nonetheless establish an approximate boundedness result: if the solution set of a system of affine conditions is dense, then it contains the solution set of a system of boundedly many affine conditions and which has approximately the same density as the original solution set. Using a recent generalisation by Gowers and the speaker of a result of Green and Tao on the equidistribution of high-rank polynomials on finite prime fields we shall furthermore prove a weaker analogous result for polynomials of small degree.

Based on joint work with Timothy Gowers (College de France and University of Cambridge).

Tue, 07 Feb 2023

15:30 - 16:30
Virtual

Bounds for subsets of $\mathbb{F}_{p}^{n} \times \mathbb{F}_{p}^{n}$ without L-shaped configurations

Sarah Peluse
(Princeton/IAS)
Further Information

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

Abstract

I will discuss the difficult problem of proving reasonable bounds in the multidimensional generalization of Szemerédi's theorem and describe a proof of such bounds for sets lacking nontrivial configurations of the form (x,y), (x,y+z), (x,y+2z), (x+z,y) in the finite field model setting.

Tue, 07 Feb 2023

14:00 - 15:00
Virtual

Recent progress on random graph matching problems

Jian Ding
(Peking University)
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, I will review some recent progress on random graph matching problems, that is, to recover the vertex correspondence between a pair of correlated random graphs from the observation of two unlabelled graphs. In this talk, I will touch issues of information threshold, efficient algorithms as well as complexity theory. This is based on joint works with Hang Du, Shuyang Gong and Zhangsong Li.

Tue, 31 Jan 2023

14:00 - 15:00
L4

Hypercontractivity on compact Lie groups, and some applications

David Ellis
(University of Bristol)
Abstract

We present two ways of obtaining hypercontractive inequalities for low-degree functions on compact Lie groups: one based on Ricci curvature bounds, the Bakry-Emery criterion and the representation theory of compact Lie groups, and another based on a (very different) probabilistic coupling approach. As applications we make progress on a question of Gowers concerning product-free subsets of the special unitary groups, and we also obtain 'mixing' inequalities for the special unitary groups, the special orthogonal groups, the spin groups and the compact symplectic groups. We expect that the latter inequalities will have applications in physics.

Based on joint work with Guy Kindler (HUJI), Noam Lifshitz (HUJI) and Dor Minzer (MIT).

Tue, 24 Jan 2023

14:00 - 15:00
L4

Asymmetric graph removal

Yuval Wigderson
(Tel Aviv University)
Abstract

The triangle removal lemma of Ruzsa and Szemerédi is a fundamental result in extremal graph theory; very roughly speaking, it says that if a graph is "far" from triangle-free, then it contains "many" triangles. Despite decades of research, there is still a lot that we don't understand about this simple statement; for example, our understanding of the quantitative dependencies is very poor.

In this talk, I will discuss asymmetric versions of the triangle removal lemma, where in some cases we can get almost optimal quantitative bounds. The proofs use a mix of ideas coming from graph theory, number theory, probabilistic combinatorics, and Ramsey theory.

Based on joint work with Lior Gishboliner and Asaf Shapira.

Tue, 17 Jan 2023

14:00 - 15:00
L4

Expansion in supercritical random subgraphs of the hypercube and its consequences

Mihyun Kang
(Graz University of Technology)
Abstract

We consider a bond percolation on the hypercube in the supercritical regime. We derive vertex-expansion properties of the giant component. As a consequence we obtain upper bounds on the diameter of the giant component and the mixing time of the lazy random walk on the giant component. This talk is based on joint work with Joshua Erde and Michael Krivelevich.

Tue, 29 Nov 2022

14:00 - 15:00
L5

Distances in colourings of the plane

James Davies
(Cambridge University)
Abstract

We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd (integral) distance from each other. We will also discuss some further results with Rose McCarty and Michal Pilipczuk concerning prime and polynomial distances.

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.