A One-Day Meeting in Combinatorics will be held in the
Mathematical Institute, University of Oxford on Tuesday 2 June 2026.
The schedule can be found below.
10.30 am
Coffee
11.00 am
Penny Haxell (Waterloo)
Algorithms for independent transversals and reconfiguration
11.55 am
Guus Regts (University of Amsterdam)
Zeros and correlation decay for the hard-core model on graphs
12.50 pm
Lunch
2.15 pm
Leslie Goldberg (Oxford)
The instability of all backoff protocols
3.10 pm
Standa Živný (Oxford)
Relaxations of Max-Cut and beyond
4.05 pm
Tea
4.30 pm
Matthew Tointon (Bristol)
A sharp one-scale version of Gromov's theorem with applications to probability on graphs
Anyone interested is welcome to attend, and no registration is required. Some funds may be
available to contribute to the expenses of research students who wish to attend. For any inquiries, please contact Alex Scott (scott at maths.ox.ac.uk).
Support for this event by the Heilbronn Institute for Mathematical Research and the British Combinatorial Committee is gratefully acknowledged.
Penny Haxell (Waterloo)
Algorithms for independent transversals and reconfiguration
Abstract:
An independent transversal (IT) of a graph G with a given vertex partition P
is an independent set in G consisting of one vertex in each of the
parts of P. This is a very general notion, and many
problems in mathematics can be expressed by asking
whether a particular graph G with a particular choice of P has an IT.
Various criteria involving properties of G and P are known that
will guarantee the existence of an IT in G.
More broadly, one may wish to consider the space of all IT's for a
given G and P, and investigate how they are related. For example,
under what conditions is this space connected, in the sense that
one can transition from any IT to any other via a sequence of
single-vertex modifications? It has been shown (Buys-Kang-Ozeki,
Wdowinski) that with conditions only very slightly stronger than those
ensuring the existence of a single IT, this connectivity property also
holds.
Here we consider the algorithmic version of this question, and show
that under certain similarly minimal conditions, such
reconfiguration paths in the space of all IT's can be found efficiently.
Guus Regts (University of Amsterdam)
Zeros and correlation decay for the hard-core model on graphs
Abstract: For a graph G and λ>0 the hard-core model is the probability distribution on the collection of independent sets, where the probabilityof an independent set J is proportional to λ|J|. (So for λ=1 we obtain the uniform distribution on the independent sets of G.) The partition function of the model, the summation of λ|J| over all independent sets J, is known as the independence polynomial of G. In this talk I will discuss some results relating the sensitivity of the marginal probability of a given vertex on far way events to the distribution of zeros of the independence polynomial. (Based on joint work with Han Peters and Josias Reppekus)
Leslie Goldberg (Oxford)
The instability of all backoff protocols
Abstract: In this work we prove Aldous's conjecture from 1987 that there is no backoff protocol that is stable for any positive arrival rate. The setting is a communication channel for coordinating requests for a shared resource. Each user who wants to access the resource makes a request by sending a message to the channel. The users don't have any way to communicate with each other, except by sending messages to the channel. The operation of the channel proceeds in discrete time steps. If exactly one message is sent to the channel during a given time step then this message succeeds (and leaves the system). If multiple messages are sent during a given time step then these messages collide. Each of the users that sent these messages therefore waits a random amount of time before re-sending. A backoff protocol is a randomised algorithm for determining how long to wait --- the waiting time is a function of how many collisions a message has had. Specifically, a backoff protocol is described by a send sequence p = (p0,p1,p2,...). If a message has had k collisions before a given time step then, with probability pk, it sends during that time step, whereas with probability 1-pk it is silent (waiting for later).
The most famous backoff protocol is binary exponential backoff, where pk = 2-k. Under Kelly's model, in which the number of new messages that arrive at the channel at each time step is given by a Poisson random variable with mean λ,
Aldous proved that binary exponential backoff is unstable for any positive λ.
He conjectured that the same is true for any backoff protocol.
We prove this conjecture. (Joint work with John Lapinskas)
Standa Živný (Oxford)
Relaxations of Max-Cut and beyond
Abstract:
Given a graph whose maximum cut is of size ρ, can one find efficiently a cut of size 0.9ρ? This is not possible under Khot's Unique Games Conjecture. What if the task is merely to find a 3-way cut of size at least 0.9ρ? Or to find a triangle-free subgraph of size 0.9ρ? In this talk I'll tell you about these two problems and other examples of approximations of maximum homomorphism problems.
Joint work with Tamio-Vesa Nakajima.
Matthew Tointon (Bristol)
A sharp one-scale version of Gromov's theorem with applications to probability on graphs
Abstract:
Gromov's theorem is a cornerstone of geometric group theory that has seen spectacular applications in many other areas. The theorem says that if a group has polynomial growth (roughly, it "spreads out slowly") then it must have a nilpotent subgroup of finite index. Recently, a lot of attention has been devoted to so-called "one-scale" versions of Gromov's theorem, where one gets the same conclusion assuming only that a single ball in the group is not too large. Breuillard, Green and Tao achieved a remarkable result in this direction using approximate groups. In this talk I will present a theorem, joint with Romain Tessera, that makes their conclusion quantitatively sharp and much more structurally detailed. I will also give an overview of some recent applications to random walks and percolation on vertex-transitive graphs.