Starting from March 31, 2020, we will run a weekly online Oxford discrete maths and probability seminar. The talks will take place on Zoom at Tuesdays at 2pm and/or 330pm UK time. The meetings are organized by Christina Goldschmidt and Alex Scott.

There is a seminar mailing list, which you can join by sending an empty email to sympa@maillist.ox.ac.uk with subject "subscribe discmathprob Firstname Lastname" (replace "Firstname Lastname" appropriately!). There is also a google calendar, which can be found here (you can subscribe by following the link and clicking on the + sign in the bottom right hand corner).

Most of the talks will be recorded and made them publicly available on our youtube channel. [Please note this for GDPR purposes!]

This is very much an experiment at the moment, so we are all learning how to do things. We'll figure out what works!

Here is the current schedule. We will put up a Zoom link before the seminar takes place. A list of past talks can be found below, as well as some links to other seminars and lists of seminars.

16 Jun
*We are currently taking a break for the summer!*

Here is the list of past talks, with links to individual youtube videos and slides/notes where available. (The talks are also gathered together on our youtube channel.)

9 Jun
*Special afternoon: Statistical physics and algorithms*

2pm
**
Dana Randall (Georgia Tech)
**

*Markov Chains for Programmable Active Matter*

video
and
slides

Abstract: Active matter describes ensembles of self-organizing agents, or particles, interacting with their local environments so that their micro-scale behavior determines macro-scale characteristics of the ensemble. While there has been a surge of activity exploring the physics underlying such systems, less attention has been paid to questions of how to program them to achieve desired outcomes. We will present some recent results designing programmable active matter for specific tasks, including aggregation, dispersion, speciation, and locomotion, building on insights from stochastic algorithms and statistical physics.

3pm
**
Will Perkins (UIC)
**

*First-order phase transitions and efficient sampling algorithms*

video
and
slides

Abstract: What is the connection between phase transitions in statistical physics and
the computational tractability of approximate counting and sampling? There
are many fascinating answers to this question but many mysteries remain. I will discuss one particular type of a phase transition: the first-order phase in the Potts model on ℤ^{d} for large q, and show how tools used to analyze the phase transition can be turned into efficient algorithms at the critical temperature. In the other direction, I'll discuss how the algorithmic perspective can help us understand phase transitions.

430pm
**
Allan Sly (Princeton)
**

*Replica Symmetry Breaking for Random Regular NAESAT*

video
and
slides

Abstract: Ideas from physics have predicted a number of important properties of random constraint satisfaction problems such as the satisfiability threshold and the free energy (the exponential growth rate of the number of solutions). Another prediction is the condensation regime where most of the solutions are contained in a small number of clusters and the overlap of two random solutions is concentrated on two points. We establish this phenomena in the random regular NAESAT model. Joint work with Danny Nam and Youngtak Sohn.

2 Jun
at 2pm
**
Wojciech Samotij (Tel Aviv)
**

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

slides (video available by request from the organizers)

Abstract:
We say that a graph G is H-free if G does not contain H as a (not
necessarily induced) subgraph. For a positive integer n, denote by ex(n,H)
the largest number of edges in an H-free graph with n vertices (the Turán
number of H). The classical theorem of Erdős, Kleitman, and Rothschild
states that, for every r≥3, there are 2^{ex(n,H)+o(n2)} many K_{r}-free
graphs with vertex set {1,…, n}.
There exist (at least) three different derivations of this estimate in the
literature: an inductive argument based on the Kővári-Sós-Turán theorem (and
its generalisation to hypergraphs due to Erdős), a proof based on
Szemerédi's regularity lemma, and an argument based on the hypergraph
container theorems. In this talk, we present yet another proof of this bound
that exploits connections between entropy and independence. This argument is
an adaptation of a method developed in a joint work with Gady Kozma, Tom
Meyerovitch, and Ron Peled that studied random metric spaces.

330pm
**
Jean Bertoin (University of Zürich)
**

*Scaling exponents of step-reinforced random walks*

video
and
slides

Let X_{1}, … be i.i.d. copies of some real random variable X. For
any ε_{2}, ε_{3}, … in {0,1}, a basic algorithm
introduced by H.A. Simon yields a reinforced sequence X̂_{1}, X̂_{2},
… as follows. If ε_{n}=0, then X̂_{n} is a uniform
random sample from X̂_{1}, …, X̂_{n-1};
otherwise X̂_{n} is a new independent copy of X. The purpose of this talk is to compare the scaling exponent of the usual random walk S(n)=X_{1}
+… + X_{n} with that of its step reinforced version
Ŝ(n)=X̂_{1}+… + X̂_{n}.
Depending on the tail of X and on asymptotic behavior of
the sequence ε_{j}, we show that step reinforcement may speed up
the walk, or at the contrary slow it down, or also does not affect the
scaling exponent at all. Our motivation partly stems from the study of
random walks with memory, notably the so-called elephant random walk and its
variations.

26 May
*Special morning: North meets South -- Discrete Maths and Probability Downunder*

930am
**
Catherine Greenhill (UNSW)
**

*The small subgraph conditioning method and hypergraphs*

video
and
slides

Abstract: The small subgraph conditioning method is an analysis of variance technique which was introduced by Robinson and Wormald in 1992, in their proof that almost all cubic graphs are Hamiltonian. The method has been used to prove many structural results about random regular graphs, mostly to show that a certain substructure is present with high probability. I will discuss some applications of the small subgraph conditioning method to hypergraphs, and describe a subtle issue which is absent in the graph setting.

11am
**
David Wood (Monash)
**

*Subgraph densities in a surface*

Abstract: We study the following question at the intersection of extremal and structural graph theory. Given a fixed graph H that embeds in a fixed surface Σ, what is the maximum number of copies of H in an n-vertex graph that embeds in Σ? Exact answers to this question are known for specific graphs H when Σ is the sphere. We aim for more general, albeit less precise, results. We show that the answer to the above question is Θ(n^{f(H)}), where f(H) is a graph invariant called the `flap-number' of H, which is independent of Σ. This simultaneously answers two open problems posed by Eppstein (1993). When H is a complete graph we give more precise answers. This is joint work with Tony Huynh and Gwenaël Joret [https://arxiv.org/abs/2003.13777].

19 May at 2pm
**
Gal Kronenberg (Oxford)
**

*The maximum length of K_r-Bootstrap Percolation*

video
and
slides

Abstract: How long does it take for a pandemic to stop spreading?
When modelling an infection process, especially these days, this is one of
the main questions that comes to mind.
In this talk, we consider this question in the bootstrap percolation
setting.

Graph-bootstrap percolation, also known as weak saturation, was
introduced by Bollobás in 1968. In this process, we start with
initial "infected" set of edges E_{0}, and we infect new edges
according to a predetermined rule. Given a graph H and a set of
previously infected edges E_{t} ⊆ E(K_{n}), we infect a non-infected
edge e if it completes a new copy of H in G=([n] , E_{t} ∪ {e}). A
question raised by Bollobás asks for the maximum time the process
can run before it stabilizes. Bollobás, Przykucki, Riordan, and
Sahasrabudhe considered this problem for the most natural case
where H=K_{r}. They answered the question for r ≤ 4 and gave a
non-trivial lower bound for every r ≥ 5. They also conjectured
that the maximal running time is o(n^{2}) for every integer r. We
disprove their conjecture for every r ≥ 6 and we give a better
lower bound for the case r=5; in the proof we use the Behrend
construction. This is a joint work with József Balogh, Alexey
Pokrovskiy, and Tibor Szabó.

330pm
**
Eyal Lubetzky (Courant)
**

*Maximum height of 3D Ising interfaces*

video
and
slides

Dobrushin (1972) showed that, at low enough temperatures, the interface of
the 3D Ising model - the random surface separating the plus and minus phases
above and below the xy-plane - is localized: it has O(1) height fluctuations
above a fixed point, and its maximum height M_{n} on a box of side length n is
O_{P}(log n). We study this interface and derive a shape theorem for its
``pillars'' conditionally on reaching an atypically large height. We use
this to analyze the maximum height M_{n} of the interface, and prove that at
low temperature M_{n}/log n converges to cβ in probability. Furthermore, the
sequence (M_{n} - E[M_{n}])_{n≥1} is tight, and even though this sequence does not
converge, its subsequential limits satisfy uniform Gumbel tails bounds.

Joint work with Reza Gheissari.

12 May
*Special afternoon: Logic and Combinatorics*

2pm
**
Tamar Ziegler (Hebrew University of Jerusalem)
**

*Sections of high rank varieties and applications*

video
and
slides

Abstract: I will describe some recent work with D. Kazhdan where we obtain results in algebraic geometry, inspired by questions in additive combinatorics, via analysis over finite fields. Specifically we are interested in quantitative properties of polynomial rings that are independent of the number of variables. A sample application is the following theorem : Let V be a complex vector space, P a high rank polynomial of degree d, and X the null set of P, X={v|P(v)=0}. Any function f:X→C which is polynomial of degree d on lines in X is the restriction of a degree d polynomial on V.

330pm
**
Anand Pillay (Notre Dame)
**

*Approximate subgroups with bounded VC dimension.*

video
and
slides

Abstract. This is joint with Gabe Conant. We give a structure theorem for finite subsets A of arbitrary groups G such that A has "small tripling" and "bounded VC dimension". Roughly, A will be a union of a bounded number of translates of a coset nilprogession of bounded rank and step (up to a small error).

5 May at 2pm
**
Liana Yepremyan (LSE)
**

*Ryser's conjecture and more*

video
and
slides

Abstract: A Latin square of order n is an nxn array filled with n symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser, Brualdi and Stein from 60s which says that every Latin square of order nxn contains a transversal of order n-1. A closely related problem is 40 year old conjecture of Brouwer that every Steiner triple system of order n contains a matching of size (n-4)/3. The third problem we'd like to mention asks how many distinct symbols in Latin arrays suffice to guarantee a full transversal? In this talk we discuss a novel approach to attack these problems. Joint work with Peter Keevash, Alexey Pokrovskiy and Benny Sudakov.

330pm
**
Benny Sudakov (ETH Zurich)
**

*Multidimensional Erdős-Szekeres theorem*

video

Abstract: The classical Erdős-Szekeres theorem dating back almost a
hundred years states that any sequence of (n-1)^{2}+1
distinct real numbers contains a monotone subsequence of length n. This
theorem has been generalised to higher dimensions
in a variety of ways but perhaps the most natural one was proposed by
Fishburn and Graham more than 25 years ago. They raise
the problem of how large should a d-dimesional array be in order to
guarantee a "monotone" subarray of size n x n x ... x n.
In this talk we discuss this problem and show how to improve their original
Ackerman-type bounds to at most a triple exponential.
(Joint work with M. Bucic and T. Tran)

28 Apr
**Special afternoon: Random graphs and planar maps**

2pm
**
Grégory Miermont (ENS Lyon)
**

*The breadth-first construction of scaling limits of graphs with finite excess*

video

Abstract: Random graphs with finite excess appear naturally in at least two different settings: random graphs in the critical window (aka critical percolation on regular and other classes of graphs), and unicellular maps of fixed genus. In the first situation, the scaling limit of such random graphs was obtained by Addario-Berry, Broutin and Goldschmidt based on a depth-first exploration of the graph and on the coding of the resulting forest by random walks. This idea originated in Aldous' work on the critical random graph, using instead a breadth-first search approach that seem less adapted to taking graph scaling limits. We show hat this can be done nevertheless, resulting in some new identities for quantities like the radius and the two-point function of the scaling limit. We also obtain a similar "breadth-first" construction of the scaling limit of unicellular maps of fixed genus. This is based on joint work with Sanchayan Sen.

330pm
**
Olivier Bernardi (Brandeis)
**

*Percolation on triangulations, and a bijective path to Liouville
quantum gravity*

video
and
slides

Abstract: I will discuss the percolation model on planar triangulations, and
present a bijection that is key to relating this model to some fundamental
probabilistic objects. I will attempt to achieve several goals:

1. Present the site-percolation model on random planar triangulations.

2. Provide an informal introduction to several probabilistic objects: the
Gaussian free field, Schramm-Loewner evolutions, and the Brownian map.

3. Present a bijective encoding of percolated triangulations by certain
lattice paths, and explain its role in establishing exact relations between
the above-mentioned objects.

This is joint work with Nina Holden, and Xin Sun.

21 Apr at 2pm
**
Agelos Georgakopoulos (Warwick)
**

*The percolation density θ(p) is analytic*

video
and
slides

Abstract: We prove that for Bernoulli bond percolation on ℤ^{d}, d≥2, the
percolation density θ(p) (defined as the probability of the origin lying in
an infinite cluster) is an analytic function of the parameter in the
supercritical interval (p_c,1]. This answers a question of Kesten from
1981.

The proof involves a little bit of elementary complex analysis (Weierstrass
M-test), a few well-known results from percolation theory
(Aizenman-Barsky/Menshikov theorem), but above all combinatorial ideas. We
used a new notion of contours, bounds on the number of partitions of an
integer, and the inclusion-exclusion principle, to obtain a refinement of a
classical argument of Peierls that settled the 2-dimensional case in 2018.
More recently, we coupled these techniques with a renormalisation argument
to handle all dimensions.

Joint work with Christoforos Panagiotis.

330pm
**
Cristina Toninelli (Paris Dauphine)
**

*Bootstrap percolation and kinetically constrained spin models:
critical time scales*

video
and
slides

Abstract: Recent years have seen a great deal of progress in understanding the behavior of bootstrap percolation models, a particular class of monotone cellular automata. In the two dimensional lattice there is now a quite complete understanding of their evolution starting from a random initial condition, with a universality picture for their critical behavior. Here we will consider their non-monotone stochastic counterpart, namely kinetically constrained models (KCM). In KCM each vertex is resampled (independently) at rate one by tossing a p-coin iff it can be infected in the next step by the bootstrap model. In particular infection can also heal, hence the non-monotonicity. Besides the connection with bootstrap percolation, KCM have an interest in their own : when p shrinks to 0 they display some of the most striking features of the liquid/glass transition, a major and still largely open problem in condensed matter physics.

14 Apr at 2pm
**
Bhargav Narayanan (Rutgers)
**

*
Thresholds*

video
and
slides

Abstract: I'll discuss our recent proof of a conjecture of Talagrand, a fractional version of the "expectation-threshold" conjecture of Kahn and Kalai. As a consequence of this result, we resolve various (heretofore) difficult problems in probabilistic combinatorics and statistical physics.

330pm
**
Ron Peled (Tel Aviv)
**

*
Site percolation on planar graphs and circle packings*

video
and
slides

Abstract: Color each vertex of an infinite graph blue with probability p and red with probability 1-p, independently among vertices. For which values of p is there an infinite connected component of blue vertices? The talk will focus on this classical percolation problem for the class of planar graphs. Recently, Itai Benjamini made several conjectures in this context, relating the percolation problem to the behavior of simple random walk on the graph. We will explain how partial answers to Benjamini's conjectures may be obtained using the theory of circle packings. Among the results is the fact that the critical percolation probability admits a universal lower bound for the class of recurrent plane triangulations. No previous knowledge on percolation or circle packings will be assumed.

7 Apr at 2pm
**
Louigi Addario-Berry (McGill)
**

*
Hipster random walks and their ilk*

video

Abstract: I will describe how certain recursive distributional equations can be solved by using tools from numerical analysis on the convergence of approximation schemes for PDEs. This project is joint work with Luc Devroye, Hannah Cairns, Celine Kerriou, and Rivka Maclaine Mitchell.

31 Mar at 2pm
**
Rob Morris (IMPA)
**

*
Erdős covering systems
*

video
and
slides

Abstract: A *covering system* of the integers is a finite collection of
arithmetic progressions whose union is the set of integers ℤ. The study of
these objects was initiated in 1950 by Erdős, and over the following
decades he asked a number of beautiful questions about them. Most famously,
his so-called 'minimum modulus problem' was resolved in 2015 by Hough, who
proved that in every covering system with distinct moduli, the minimum
modulus is at most 10^{16}.

In this talk I will describe a simple and general method of attacking
covering problems that was inspired by Hough's proof. We expect that this
technique, which we call the 'distortion method', will have further
applications in combinatorics.

This talk is based on joint work with Paul Balister, Béla Bollobás, Julian
Sahasrabudhe and Marius Tiba.

Here are links to some other online seminars and lists of events:

The One World Probability Seminar

Northeastern Virtual Combinatorics Colloquium

Horowitz Seminar on Probability, Ergodic Theory and Dynamical Systems

Extremal and Probabilistic Combinatorics Webinar

Big list of online math seminars