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
Annika Heckel (Uppsala)
The threshold for a rainbow F-factor and a spread condition for colourings
3.10 pm
Standa Živný (Oxford)
Relaxations of Max-Cut and Beyond
4.05 pm
Tea
4.30 pm
Romain Tessera (Institut de Mathématiques de Jussieu-Paris Rive Gauche)
An optimal one-scale version of Gromov's theorem
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)
Annika Heckel (Uppsala)
The threshold for a rainbow F-factor and a spread condition for colourings
Abstract:
Title: We establish the threshold for a randomly coloured random graph to contain a rainbow copy of an F-factor (where F is any fixed 1-balanced graph), answering a question of Han and Yuan. Along the way we prove a theorem generalising recent work of Han and Yuan, where instead of rainbow colourings we consider a more general class of colourings satisfying a natural spread condition.
The proof also involves several careful couplings including a coupling technique of McDiarmid (twice) and a coupling of Riordan which translates between copies of F in G(n,p) and the r-uniform random hypergraph (where r is the number of vertices of F).
Joint work with Stepan Vakhrushev.
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.
Romain Tessera (Institut de Mathématiques de Jussieu-Paris Rive Gauche)
An optimal one-scale version of Gromov's theorem
Abstract:
Gromov's theorem is a cornerstone in geometric group theory. It says that a group with at most polynomial growth must be virtually nilpotent. Recently, a lot of attention has been devoted to so-called "one-scale" versions of this result: where one gets the same conclusion only assuming that the size of a single ball of large enough radius R is less than rD for some D. Such a statement does not simply follow by a compactness argument from Gromov's theorem and requires a much more "local" analysis.
The most efficient approach so far is through the theory of approximate groups, via the work of Breuillard, Green and Tao.
I will present a sharp version of their result, obtained with Matt Tointon. By sharp, we mean regarding the relation between the exponent D and the "complexity" of the virtually nilpotent group (including the index, which was not even effective in their statement). In fact, we obtain this as a small part of a much more detailed fine-scale description of the structure of G. These results have a wide range of applications in various aspects of the theory of vertex-transitive graphs: percolation theory, random walks, structure of finite groups, scaling limits of finite vertex-transitive graphs...