One-Day Meeting in Combinatorics
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!

Schedule

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.


Abstracts

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.