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.
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.
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
To come
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.