One-Day Meeting in Combinatorics
Mathematical Institute
University of Oxford

Wednesday 1 June 2022

A One-Day Meeting in Combinatorics will be held in the Mathematical Institute, University of Oxford on Wednesday 1 June 2022. The schedule can be found below.

Schedule

10.30 am                      Coffee

11.00 am                      Gabor Lugosi (Barcelona)
                                     Root finding and broadcasting in recursive trees and dags

11.55 am                      Gal Kronenberg (Oxford)
                                     Partitioning cubic graphs into isomorphic linear forests

12.50 pm                      Lunch

2.15 pm                        Paul Balister (Oxford)
                                     Monotone cellular automata

3.10 pm                        Julia Wolf (Cambridge)
                                     Irregular triads in 3-uniform hypergraphs

4.05 pm                        Tea

4.30 pm                        David Wood (Monash)
                                     Universality in minor-closed graph classes


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

Gabor Lugosi (Barcelona), Root finding and broadcasting in recursive trees and dags

Abstract: Networks are often naturally modeled by random processes in which nodes of the network are added one-by-one, according to some random rule. Uniform and preferential attachment trees are among the simplest examples of such dynamically growing networks. The statistical problems we address in this talk regard discovering the past of the network when a present-day snapshot is observed. We present a few results that show that, even in gigantic networks, a lot of information is preserved from the very early days. In particular, we discuss the problem of finding the root and the broadcasting problem.


Gal Kronenberg (Oxford), Partitioning cubic graphs into isomorphic linear forests

Abstract: The linear arboricity of a graph G, denoted by la(G), is the minimum number of edge-disjoint linear forests (i.e. collections of disjoint paths) in G whose union is all the edges of G. It is known that the linear arboricity of every cubic graph is 2. In 1987 Wormald conjectured that every cubic graph with even number of edges, can be partitioned such that the two parts are isomorphic linear forests.
This is known to hold for Jeager graphs and for some further classes of cubic graphs (see, Bermond-Fouquet-Habib-Peroche,  Wormald, Jackson-Wormald, Fouquet-Thuillier-Vanherpe-Wojda). In this talk we will present a proof of Wormald's conjecture for all large connected cubic graphs.
This is joint work with Shoham Letzter, Alexey Pokrovskiy, and Liana Yepremyan.


Paul Balister (Oxford), Monotone cellular automata

A monotone cellular automaton or generalised bootstrap percolation is a very special class of 2-state cellular automata in which "active" or "infected" states stay infected, and adding more infected sites cannot reduce subsequent infections. A great deal of work has been done on such models, in particular on the question of when such models "percolate" or fill the space Z_n^d with infected sites when the initial configuration is random with sites infected independently with probability p(n). There is a sharp threshold function p(n) for the probability that the model percolates, the form of which was previously conjectured and we have now proven. I will talk about what is known about this threshold, and what one can't know --- the exponent on the threshold being uncomputable in general.
Joint work with Bela Bollobás, Robert Morris and Paul Smith.


Julia Wolf (Cambridge), Irregular triads in 3-uniform hypergraphs

Abstract: Szemerédi's celebrated regularity lemma states, roughly speaking, that the vertex set of any large graph can be partitioned into a bounded number of sets in such a way that all but a small proportion of pairs of sets from this partition induce a `regular' graph. The example of the half-graph shows that the existence of irregular pairs cannot be ruled out in general.
Recognising the half-graph as an instance of the so-called 'order property' from model theory, Malliaris and Shelah proved in 2014 that if one assumes that the large graph contains no half-graphs of a fixed size, then it is possible to obtain a regularity partition with no irregular pairs. In addition, the number of parts of the partition is polynomial in the regularity parameter, and the density of each regular pair is either close to zero or close to 1.
This beautiful result exemplifies a long-standing theme in model theory, namely that so-called stable structures (which are characterised by an absence of large instances of the order property), are extremely well-behaved.
In this talk I will present recent joint work with Caroline Terry (OSU), in which we define a higher-arity generalisation of the order property and prove that its absence characterises those large 3-uniform hypergraphs whose regularity decompositions allow for particularly good control of the irregular triads.


David Wood (Monash), Universality in minor-closed graph classes

Abstract: Stanislaw Ulam asked whether there exists a universal countable planar graph (that is, a countable planar graph that contains every countable planar graph as a subgraph). János Pach (1981) answered this question in the negative. We strengthen this result by showing that every countable graph that contains all countable planar graphs must contain an infinite complete graph as a minor. On the other hand, we construct a countable graph that contains all countable planar graphs and has several key properties such as linear colouring numbers, linear expansion, and every finite n-vertex subgraph has O(n1/2) treewidth (which implies the Lipton-Tarjan separator theorem). More generally, for every fixed positive integer t we construct a countable graph that contains every countable Kt-minor-free graph and has the above key properties. Joint work with Tony Huynh, Bojan Mohar, Robert Samal and Carsten Thomassen.