Mathematical Institute

University of Oxford

Wednesday 29 May 2019

A One-Day Meeting in Combinatorics will be held in the
Mathematical Institute, University of Oxford on **Wednesday 29 May 2019**.
A provisional schedule can be found below; other details to be added in due course!

10.30 am
Coffee

11.00 am
**
Vida Dujmovic (Ottawa)
**

*
Layered H-partitions with applications*

11.55 am
**
Louis Esperet (Grenoble)
**

*
Exact distance colouring in trees*

12.50 pm
Lunch

2.15 pm
**
Perla Sousi (Cambridge)
**

*
Random walk on dynamical percolation*

3.10 pm
**
Remco van der Hofstad (Eindhoven)
**

*
Hypercube percolation*

4.05 pm
Tea

4.30 pm
**
Martin Grohe (Aachen)
**

*
The combinatorial and descriptive complexity of identifying a graph
*

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 London Mathematical Society and the British Combinatorial Committee is gratefully acknowledged.

**Vida Dujmovic (Ottawa),
**
*
Layered H-partitions with applications
*

We introduce a new structural tool called layered
H-partitions, and prove that every planar graph has such a partition of
bounded layered width in which H has bounded treewidth. These results
generalise for graphs that exclude an apex graph as a minor. With the help
of this tool we settle two long-standing problems, one on queue-number of
planar graphs of Heath, Leighton and Rosenberg from 1992 and one on the
non-repetitive chromatic number of planar graphs by Alon, Grytczuk,
Haluszczak and Riordan from 2002.

**Louis Esperet (Grenoble),
**
*
Exact distance colouring in trees
*

We consider the problem of colouring points in a metric space, so that any
two points at distance exactly d have different colours, and the goal is to
minimize the number of colours. In the Euclidean plane this is the classical
Hadwiger-Neslon problem, and in this case the answer does not depend on d
(since the Euclidean plane is invariant under homothety). In the hyperbolic
plane however it is not known whether the number of colours can be bounded
by a constant (independent of d). In this talk I will consider infinite
regular trees, where the metric is given by the distances in the graph. In
this case we can prove that the minimum number of colours is of order d/log
d when d is an even integer. In particular, the fact that it grows with d
gives a negative answer to a problem of Van den Heuvel and Naserasr on exact
distance colouring in planar graphs.

Joint work with Nicolas Bousquet, Ararat Harutyunyan, and Rémi de Joannis de
Verclos.

**Perla Sousi (Cambridge),
***
Random walk on dynamical percolation
*

We study the behaviour of random walk on dynamical percolation. In this
model, the edges of a graph G are either open or closed and refresh their
status at rate µ, while at the same time a random walker moves on G at rate
1, but only along edges which are open. I will talk about the mixing time of
this process in the case where G is the d-dimensional lattice and the
complete graph. I will also talk about comparison results for mixing and
hitting times with the corresponding quantities for simple random walk on
the underlying graph G, for general graphs. (Based on joint works with Y.
Peres and J. Steif, with Sam Thomas and with Jonathan Hermon.)

**Remco van der Hofstad (Eindhoven),
**
*Hypercube percolation
*

Consider bond percolation on the hypercube {0,1}^n at the critical
probability p_c defined such that the expected cluster size equals
2^{n/3}, where 2^{n/3} acts as the cube root of the number of vertices of
the n-cube. Percolation on the Hamming cube was proposed by Erd"os and
Spencer (1979), and has proved to be substantially harder than percolation
on the complete graph. In this talk, I will describe the percolation phase
transition on the hypercube, and show that it shares many features with
that on the complete graph.

In previous work with Borgs, Chayes, Slade and Spencer, and with
Heydenreich, we have identified the subcritical and critical regimes of
percolation on the hypercube. In particular, we know that for
p=p_c(1+O(2^{-n/3})), the largest connected component has size roughly
2^{2n/3}. In work with Asaf Nachmias, we identify the supercritical
behavior of percolation on the hypercube, by showing that, for any
sequence \epsilon_n tending to zero, but \epsilon_n being much larger than
2^{-n/3}, percolation at p_c(1+\epsilon_n) has, with high probability, a
unique giant component of size (2+o(1))\epsilon_n 2^n. This also confirms
that the validity of the proposed critical value. Finally, we `unlace' the
proof by identifying the scaling of component sizes in the supercritical
and critical regimes without relying on the percolation lace expansion.
The lace expansion is a beautiful technique that is the major technical
tool for high-dimensional percolation, but that is also quite involved and
can have a disheartening effect on some. I will also sketch extensions to
the Hamming graph, which is the Cartesian product of d complete graphs,
where, for d=2,3,4, we have identified the scaling behavior in the
critical window with Federico, den Hollander and Hulshof.

**Martin Grohe (Aachen),
**
*
The combinatorial and descriptive complexity of identifying a graph
*

The Weisfeiler-Leman (WL) dimension is a graph invariant that, intuitively, measures how complicated it is to distinguish the graph from other graphs by combinatorial means. It is based on the Weisfeiler-Leman algorithm, a well-known combinatorial graph isomorphism test going back to work of Weisfeiler and Leman in the late 1960s. The WL-dimension has a surprising number of seemingly unrelated other characterisations in terms of logic, algebra, linear and semi-definite programming, and graph homomorphisms.

It has been shown that many natural graph classes have a bounded WL dimension, among them all classes excluding a fixed graph as a minor, the class of interval graphs, and all classes of bounded rank width.

In the first part of my talk, I will give an introduction to WL dimension and its various characterisations. In the second part I will speak about recent bounds we obtained for the WL dimension of graphs of bounded genus and graphs of bounded rank width.