Forthcoming events in this series


Tue, 05 Mar 2024

14:00 - 15:00
L4

Paradoxical Decompositions and Colouring Rules

Robert Simon
(London School of Economics)
Abstract

A colouring rule is a way to colour the points $x$ of a probability space according to the colours of finitely many measure preserving tranformations of $x$. The rule is paradoxical if the rule can be satisfied a.e. by some colourings, but by none whose inverse images are measurable with respect to any finitely additive extension for which the transformations remain measure preserving. We show that proper graph colouring as a rule can be paradoxical. And we demonstrate rules defined via optimisation that are paradoxical. A connection to measure theoretic paradoxes is established.

Tue, 27 Feb 2024

15:30 - 16:30
Online

Discrepancy of graphs

István Tomon
(Umea University)
Further Information

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

Abstract

The positive discrepancy of a graph $G$ is the maximum surplus of edges in an induced subgraph of $G$ compared to its expected size. This quantity is closely related to other well studied parameters, such as the minimum bisection and the spectral gap. I will talk about the extremal behavior of the positive discrepancy among graphs with given number of vertices and average degree, uncovering a surprising pattern. This leads to an almost complete solution of a problem of Alon on the minimum bisection and let's us extend the Alon-Boppana bound on the second eigenvalue to dense graphs.

Joint work with Eero Räty and Benny Sudakov.

Tue, 27 Feb 2024

14:00 - 15:00
Online

Geodesics networks in the directed landscape

Duncan Dauvergne
(University of Toronto)
Further Information

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

Abstract

The directed landscape is a random directed metric on the plane that is the scaling limit for models in the KPZ universality class (i.e. last passage percolation on $\mathbb{Z}^2$, TASEP). In this metric, typical pairs of points are connected by a unique geodesic.  However, certain exceptional pairs are connected by more exotic geodesic networks. The goal of this talk is to describe a full classification for these exceptional pairs.

Tue, 20 Feb 2024

14:00 - 15:00
L4

Hamiltonicity of expanders: optimal bounds and applications

Nemanja Draganić
(University of Oxford)
Abstract

An $n$-vertex graph $G$ is a $C$-expander if $|N(X)|\geq C|X|$ for every $X\subseteq V(G)$ with $|X|< n/2C$ and there is an edge between every two disjoint sets of at least $n/2C$ vertices.

We show that there is some constant $C>0$ for which every $C$-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in $(n,d,\lambda)$-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications.

Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.

Tue, 13 Feb 2024

14:00 - 15:00
L4

On the $(k+2,k)$-problem of Brown, Erdős and Sós

Oleg Pikhurko
(University of Warwick)
Abstract

Brown-Erdős-Sós initiated the study of the maximum number of edges in an $n$-vertex $r$-graph such that no $k$ edges span at most $s$ vertices. If $s=rk-2k+2$ then this function is quadratic in $n$ and its asymptotic was previously known for $k=2,3,4$. I will present joint work with Stefan Glock, Jaehoon Kim, Lyuben Lichev and Shumin Sun where we resolve the cases $k=5,6,7$.

Tue, 06 Feb 2024

14:00 - 15:00
L4

Typical Ramsey properties of the primes and abelian groups

Robert Hancock
(University of Oxford)
Abstract

Given a matrix $A$ with integer entries, a subset $S$ of an abelian group and $r\in\mathbb N$, we say that $S$ is $(A,r)$-Rado if any $r$-colouring of $S$ yields a monochromatic solution to the system of equations $Ax=0$. A classical result of Rado characterises all those matrices $A$ such that $\mathbb N$ is $(A,r)$-Rado for all $r \in \mathbb N$. Rödl and Ruciński, and Friedgut, Rödl and Schacht proved a random version of Rado’s theorem where one considers a random subset of $[n]:=\{1,\dots,n\}$.

In this paper, we investigate the analogous random Ramsey problem in the more general setting of abelian groups. Given a sequence $(S_n)_{n\in\mathbb N}$ of finite subsets of abelian groups, let $S_{n,p}$ be a random subset of $S_n$ obtained by including each element of $S_n$ independently with probability $p$. We are interested in determining the probability threshold for $S_{n,p}$ being $(A,r)$-Rado.

Our main result is a general black box for hypergraphs which we use to tackle problems of this type. Using this tool in conjunction with a series of supersaturation results, we determine the probability threshold for a number of different cases. A consequence of the Green-Tao theorem is the van der Waerden theorem for the primes: every finite colouring of the primes contains arbitrarily long monochromatic arithmetic progressions. Using our machinery, we obtain a random version of this result. We also prove a novel supersaturation result for $[n]^d$ and use it to prove an integer lattice generalisation of the random version of Rado's theorem.

This is joint work with Andrea Freschi and Andrew Treglown (both University of Birmingham).

Tue, 30 Jan 2024

14:00 - 15:00
L4

Kneser graphs are Hamiltonian

Torsten Mütze
(University of Warwick)
Abstract

For integers $k \ge 1$ and $n \ge 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph $K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of our work is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph $J(n,k,s)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two sets whose intersection has size exactly $s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graphs include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász' conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

This is joint work with my students Arturo Merino (TU Berlin) and Namrata (Warwick).

Tue, 23 Jan 2024

15:30 - 16:30
Online

Paths in random temporal graphs

Nina Kamčev
(University of Zagreb)
Further Information

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

Abstract

Random temporal graphs are a version of the classical Erdős-Rényi random graph $G(n,p)$ where additionally, each edge has a distinct random time stamp, and connectivity is constrained to sequences of edges with increasing time stamps. We are interested in the asymptotics for the distances in such graphs, mostly in the regime of interest where the average degree $np$ is of order $\log n$ ('near' the phase transition).

More specifically, we will discuss the asymptotic lengths of increasing paths: the lengths of the shortest and longest paths between typical vertices, as well as the maxima between any two vertices; this also covers the (temporal) diameter. In the regime $np \gg \log n$, longest increasing paths were studied by Angel, Ferber, Sudakov and Tassion.

The talk contains joint work with Nicolas Broutin and Gábor Lugosi.

Tue, 23 Jan 2024

14:00 - 15:00
Online

Sharpness of the phase transition for interlacements percolation

Augusto Teixeira
(Instituto Nacional de Matemática Pura e Aplicada (IMPA))
Further Information

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

Abstract

In this talk we will review the problem of sharpness in percolation, tracing its origins back to the seminal works of Menshikov, Grimmett-Marstrand and Aizenman-Barsky, which successfully settled the question in the context of Bernoulli independent percolation. Then we will present some recent advancements on the field, which have opened up the possibility of investigating dependent percolation models. Special emphasis will be given to the Interpolation technique, which has proved itself very effective. In particular, it has been used to establish the sharpness for Interlacements Percolation, a model introduced by Sznitman with notoriously intricate dependencies.

This talk is based on a joint work with Duminil-Copin, Goswami, Rodriguez and Severo

Tue, 16 Jan 2024

14:00 - 15:00
L4

Heights of random trees

Louigi Addario-Berry
(McGill University)
Abstract

A rooted tree $T$ has degree sequence $(d_1,\ldots,d_n)$ if $T$ has vertex set $[n]$ and vertex $i$ has $d_i$ children for each $i$ in $[n]$. 

I will describe a line-breaking construction of random rooted trees with given degree sequences, as well as a way of coupling random trees with different degree sequences that also couples their heights to one another. 

The construction and the coupling have several consequences, and I'll try to explain some of these in the talk.

First, let $T$ be a branching process tree with criticalmean oneoffspring distribution, and let $T_n$ have the law of $T$ conditioned to have size $n$. Then the following both hold.
1) $\operatorname{height}(T_n)/\log(n)$ tends to infinity in probability. 
2) If the offspring distribution has infinite variance then $\operatorname{height}(T_n)/n^{1/2}$ tends to $0$ in probability. This result settles a conjecture of Svante Janson.

The next two statements relate to random rooted trees with given degree sequences. 
1) For any $\varepsilon > 0$ there is $C > 0$ such that the following holds. If $T$ is a random tree with degree sequence $(d_1,\ldots,d_n)$ and at least $\varepsilon n$ leaves, then $\mathbb{E}(\operatorname{height}(T)) < C \sqrt{n}$. 
2) Consider any random tree $T$ with a fixed degree sequence such that $T$ has no vertices with exactly one child. Then $\operatorname{height}(T)$ is stochastically less than $\operatorname{height}(B)$, where $B$ is a random binary tree of the same size as $T$ (or size one greater, if $T$ has even size). 

This is based on joint work with Serte Donderwinkel and Igor Kortchemski.

Tue, 28 Nov 2023

16:00 - 17:00
L1

Euclidean Ramsey Theory

Imre Leader
(University of Cambridge)
Abstract

Euclidean Ramsey Theory is a natural multidimensional version of Ramsey Theory. A subset of Euclidean space is called Ramsey if, for any $k$, whenever we partition Euclidean space of sufficiently high dimension into $k$ classes, one class much contain a congruent copy of our subset. It is still unknown which sets are Ramsey. We will discuss background on this and then proceed to some recent results.

Tue, 21 Nov 2023

14:00 - 15:00
L3

Embedding planar graphs on point-sets: Problems and new results

Raphael Steiner
(ETH Zurich)
Abstract

In this talk, I will present new results addressing two rather well-known problems on the embeddability of planar graphs on point-sets in the plane. The first problem, often attributed to Mohar, asks for the asymptotics of the minimum size of so-called universal point sets, i.e. point sets that simultaneously allow straight-line embeddings of all planar graphs on $n$ vertices. In the first half of the talk I will present a family of point sets of size $O(n)$ that allow straight-line embeddings of a large family of $n$-vertex planar graphs, including all bipartite planar graphs. In the second half of the talk, I will present a family of $(3+o(1))\log_2(n)$ planar graphs on $n$ vertices that cannot be simultaneously embedded straight-line on a common set of $n$ points in the plane. This significantly strengthens the previously best known exponential bound.

Tue, 14 Nov 2023

15:30 - 16:30
Online

Preferential attachment trees built from random walks

Gábor Pete
(Rényi Institute/Budapest University of Technology and Economics)
Further Information

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

Abstract

I will talk about two separate projects where random walks are building a random tree, yielding preferential attachment behaviour from completely local mechanisms.
First, the Tree Builder Random Walk is a randomly growing tree, built by a walker as she is walking around the tree. At each time $n$, she adds a leaf to her current vertex with probability $n^{-\gamma}, \gamma\in(2/3, 1]$, then moves to a uniform random neighbor on the possibly modified tree. We show that the tree process at its growth times, after a random finite number of steps, can be coupled to be identical to the Barabási-Albert preferential attachment tree model. This coupling implies that many properties known for the BA-model, such as diameter and degree distribution, can be directly transferred to our model. Joint work with János Engländer, Giulio Iacobelli, and Rodrigo Ribeiro. Second, we introduce a network-of-networks model for physical networks: we randomly grow subgraphs of an ambient graph (say, a box of $\mathbb{Z}^d$) until they hit each other, building a tree from how these spatially extended nodes touch each other. We compute non-rigorously the degree distribution exponent of this tree in large generality, and provide a rigorous analysis when the nodes are loop-erased random walks in dimension $d=2$ or $d\geq 5$, using a connection with the Uniform Spanning Tree. Joint work with Ádám Timár, Sigurdur Örn Stefánsson, Ivan Bonamassa, and Márton Pósfai. (See https://arxiv.org/abs/2306.01583)

Tue, 14 Nov 2023

14:00 - 15:00
Online

Skipless chain decompositions and improved poset saturation bounds

Paul Bastide
(LaBRI/Utrecht)
Further Information

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

Abstract

We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer two conjectures about the asymptotics of induced saturation numbers for the antichain, which are defined as follows. For positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$ (as induced subposet), but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use $\textrm{sat}^{\ast}(n,k)$ to denote the smallest size of such a family. With more work we pinpoint the exact value of $\textrm{sat}^{\ast}(n,k)$, for all $k$ and sufficiently large $n$. Previously, exact values for $\textrm{sat}^{\ast}(n,k)$ were only known for $k$ up to 6. We also show that for any poset $\mathcal{P}$, its induced saturation number (which is defined similar as for the antichain) grows at most polynomially: $\textrm{sat}^{\ast}(n, \mathcal{P})=O(n^c)$, where $c \leq |\mathcal{P}|^2/4+1$. This is based on joint works with Carla Groenland, Maria-Romina Ivan, Hugo Jacob and Tom Johnston.

Tue, 31 Oct 2023

14:00 - 15:00
L3

Competitive analysis in random graph processes

Peleg Michaeli
(University of Oxford)
Abstract

Consider the following "controlled" random graph process: edges of the complete graph are revealed one by one in random order to an online algorithm, which immediately decides whether to retain each observed edge. The algorithm's objective is to construct a graph property within specified constraints on the total number of observed edges ("time") and the total number of retained edges ("budget").

During this talk, I will present results in this model for natural graph properties, such as connectivity, Hamiltonicity, and containment of fixed-size subgraphs. Specifically, I will describe a strategy to construct a Hamilton cycle at the hitting time for minimum degree 2 by retaining a linear number of edges. This extends the classical hitting time result for Hamiltonicity originally established by Ajtai–Komlós–Szemerédi and Bollobás.

The talk is based on joint work with Alan Frieze and Michael Krivelevich.

Tue, 24 Oct 2023

14:00 - 15:00
L3

Monochromatic products and sums in N and Q

Matt Bowen
(University of Oxford)
Abstract

We show that every 2-coloring of the natural numbers and any finite coloring of the rationals contains monochromatic sets of the form $\{x, y, xy, x+y\}$. We also discuss generalizations and obstructions to extending this result to arbitrary finite coloring of the naturals. This is partially based on joint work with Marcin Sabok.

Tue, 17 Oct 2023

15:30 - 16:30
Online

Critical core percolation on random graphs

Alice Contat
(Université Paris-Saclay)
Further Information

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

Abstract

Motivated by the desire to construct large independent sets in random graphs, Karp and Sipser modified the usual greedy construction to yield an algorithm that outputs an independent set with a large cardinal called the Karp-Sipser core. When run on the Erdős-Rényi $G(n,c/n)$ random graph, this algorithm is optimal as long as $c < e$. We will present the proof of a physics conjecture of Bauer and Golinelli (2002) stating that at criticality, the size of the Karp-Sipser core is of order $n^{3/5}$. Along the way we shall highlight the similarities and differences with the usual greedy algorithm and the $k$-core algorithm.
Based on a joint work with Nicolas Curien and Thomas Budzinski.

Tue, 17 Oct 2023

14:00 - 15:00
Online

$k$-blocks and forbidden induced subgraphs

Maria Chudnovsky
(Princeton)
Further Information

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

Abstract

A $k$-block in a graph is a set of $k$ vertices every two of which are joined by $k$ vertex disjoint paths. By a result of Weissauer, graphs with no $k$-blocks admit tree-decompositions with especially useful structure. While several constructions show that it is probably very difficult to characterize induced subgraph obstructions for bounded tree width, a lot can be said about graphs with no $k$-blocks. On the other hand, forbidding induced subgraphs places significant restrictions on the structure of a $k$-block in a graphs. We will discuss this phenomenon and its consequences in the study of tree-decompositions in classes of graphs defined by forbidden induced subgraphs.

Tue, 10 Oct 2023

14:00 - 15:00
L3

(CANCELLED) Percolation through isoperimetry

Michael Krivelevich
(Tel Aviv University)
Abstract

Let $G$ be a $d$-regular graph of growing degree on $n$ vertices, and form a random subgraph $G_p$ of $G$ by retaining edge of $G$ independently with probability $p=p(d)$. Which conditions on $G$ suffice to observe a phase transition at $p=1/d$, similar to that in the binomial random graph $G(n,p)$, or, say, in a random subgraph of the binary hypercube $Q^d$?

We argue that in the supercritical regime $p=(1+\epsilon)/d$, $\epsilon>0$ being a small constant, postulating that every vertex subset $S$ of $G$ of at most $n/2$ vertices has its edge boundary at least $C|S|$, for some large enough constant $C=C(\epsilon)>0$, suffices to guarantee the likely appearance of the giant component in $G_p$. Moreover, its asymptotic order is equal to that in the random graph $G(n,(1+\epsilon)/n)$, and all other components are typically much smaller.

We further give examples demonstrating the tightness of this result in several key senses.

A joint work with Sahar Diskin, Joshua Erde and Mihyun Kang.

Tue, 13 Jun 2023

14:00 - 15:00
L5

A Ramsey Characterisation of Eventually Periodic Words

Maria Ivan
(University of Cambridge)
Abstract

A factorisation $x=u_1u_2\cdots$ of an infinite word $x$ on alphabet $X$ is called ‘super-monochromatic’, for a given colouring of the finite words $X^{\ast}$ on alphabet $X$, if each word $u_{k_1}u_{k_2}\cdots u_{k_n}$, where $k_1<\cdots<k_n$, is the same colour. A direct application of Hindman’s theorem shows that if $x$ is eventually periodic, then for every finite colouring of $X^{\ast}$, there exist a suffix of $x$ that admits a super-monochromatic factorisation. What about the converse?

In this talk we show that the converse does indeed hold: thus a word $x$ is eventually periodic if and only if for every finite colouring of $X^{\ast}$ there is a suffix of $x$ having a super-monochromatic factorisation. This has been a conjecture in the community for some time. Our main tool is a Ramsey result about alternating sums. This provides a strong link between Ramsey theory and the combinatorics of infinite words.

Joint work with Imre Leader and Luca Q. Zamboni

Tue, 06 Jun 2023

17:00 - 18:00
Virtual

The Critical Beta-splitting Random Tree

David Aldous
(U.C. Berkeley and University of Washington)
Further Information

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

Abstract

In the critical beta-splitting model of a random $n$-leaf rooted tree, clades (subtrees) are recursively split into sub-clades, and a clade of $m$ leaves is split into sub-clades containing $i$ and $m-i$ leaves with probabilities $\propto 1/(i(m-i))$. This model turns out to have interesting properties. There is a canonical embedding into a continuous-time model ($\operatorname{CTCS}(n)$). There is an inductive construction of $\operatorname{CTCS}(n)$ as $n$ increases, analogous to the stick-breaking constructions of the uniform random tree and its limit continuum random tree. We study the heights of leaves and the limit fringe distribution relative to a random leaf. In addition to familiar probabilistic methods, there are analytic methods (developed by co-author Boris Pittel), based on explicit recurrences, which often give more precise results. So this model provides an interesting concrete setting in which to compare and contrast these methods. Many open problems remain.
Preprints at https://arxiv.org/abs/2302.05066 and https://arxiv.org/abs/2303.02529

Tue, 06 Jun 2023

15:30 - 16:30
Virtual

The Metropolis Algorithm for the Planted Clique Problem

Elchanan Mossel
(MIT)
Further Information

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

Abstract

More than 30 year ago Jerrum studied the planted clique problem and proved that under worst-case initialization Metropolis fails to recover planted cliques of size $\ll n^{1/2}$ in the Erdős-Rényi graph $G(n,1/2)$. This result is classically cited in the literature of the problem, as the "first evidence" that finding planted cliques of size much smaller than square root $n$ is "algorithmically hard". Cliques of size $\gg n^{1/2}$ are easy to find using simple algorithms. In a recent work we show that the Metropolis process actually fails to find planted cliques under worst-case initialization for cliques up to size almost linear in $n$. Thus the algorithm fails well beyond the $\sqrt{n}$ "conjectured algorithmic threshold". We also prove that, for a large parameter regime, that the Metropolis process fails also under "natural initialization". Our results resolve some open questions posed by Jerrum in 1992. Based on joint work with Zongchen Chen and Iias Zadik.

Tue, 30 May 2023

14:00 - 15:00
L5

Cycle Partition of Dense Regular Digraphs and Oriented Graphs

Allan Lo
(University of Birmingham)
Abstract

Magnant and Martin conjectured that every $d$-regular graph on $n$ vertices can be covered by $n/(d+1)$ vertex-disjoint paths. Gruslys and Letzter verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all $\alpha>0$, there exists $n_0=n_0(\alpha)$ such that every $d$-regular digraph on $n$ vertices with $d \ge \alpha n $ can be covered by at most $n/(d+1)$ vertex-disjoint cycles. Moreover if $G$ is an oriented graph, then $n/(2d+1)$ cycles suffice. This also establishes Jackson's long standing conjecture for large $n$ that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian.
This is joint work with Viresh Patel and  Mehmet Akif Yıldız.

Wed, 24 May 2023

10:15 - 18:00
L3

One-Day Meeting in Combinatorics

Multiple
Abstract

The speakers are Maya Stein (University of Chile), Mathias Schacht (Hamburg), János Pach (Rényi Institute, Hungary and IST Austria), Marthe Bonamy (Bordeaux)Mehtaab Sawhney (Cambridge/MIT), and Julian Sahasrabudhe (Cambridge). Please see the event website for further details including titles, abstracts, and timings. Anyone interested is welcome to attend, and no registration is required.