Oxford Discrete Mathematics and Probability Seminar

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!

Current schedule

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!



Past talks

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 2ex(n,H)+o(n2) many Kr-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 X1, … 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)=X1 +… + Xn 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 Θ(nf(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 E0, and we infect new edges according to a predetermined rule. Given a graph H and a set of previously infected edges Et ⊆ E(Kn), we infect a non-infected edge e if it completes a new copy of H in G=([n] , Et ∪ {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=Kr. 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(n2) 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 Mn on a box of side length n is OP(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 Mn of the interface, and prove that at low temperature Mn/log n converges to cβ in probability. Furthermore, the sequence (Mn - E[Mn])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

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

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)
                                       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

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 1016.
    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.



Other online seminars

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

The One World Probability Seminar

Northeastern Virtual Combinatorics Colloquium

Combinatorics Lectures Online

CS Theory Online Talks

Horowitz Seminar on Probability, Ergodic Theory and Dynamical Systems

Extremal and Probabilistic Combinatorics Webinar

Online Probability Seminars

Big list of online math seminars