Mathematical Institute

University of Oxford

Wednesday 24 May 2017

A One-Day Meeting in Combinatorics will be held in the
Mathematical Institute, University of Oxford on **Wednesday 24 May 2017**.
Schedule and abstracts can be found below.

10.30 am
Coffee

11.00 am
**Christina Goldschmidt (Oxford)
**

*
Critical random graphs with i.i.d. random degrees having power-law tails*

11.55 am
**Bruce Reed (CNRS/McGill)
**

*
The typical structure of graphs in a hereditary family*

12.50 pm
Lunch

2.15 pm
**
Daniela Kuhn (Birmingham)
**

*
The existence of designs -- beyond quasirandomness
*

3.10 pm
**
David Wood (Monash)
**

*
Defective colouring of graphs excluding a subgraph or minor*

4.05 pm
Tea

4.30 pm
**
Paul Seymour (Princeton)
**

*
Rainbow paths*

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.

**Christina Goldschmidt (Oxford),
**
*
Critical random graphs with i.i.d. random degrees having power-law tails
*

Consider a graph with label set {1, 2, ..., n} chosen
uniformly at random from those such that vertex i has degree D_i, where
D_1, D_2, ..., D_n are i.i.d. strictly positive random variables. The
threshold for the emergence of a giant component in this setting is well
known to be E[D^2] = 2 E[D], and we assume additionally that P(D = k) ~ c k^{-(α + 2)} as k tends to infinity, for some
α in (1,2) and some constant c >0. In this situation, it turns out that the
largest components have sizes on the order of n^{α/(α+1)}.
Building on earlier work of Joseph, we show that the components
have scaling limits which are absolutely continuous with respect to the
corresponding limits for critical Galton-Watson trees with offspring
distribution in the domain of attraction of an α-stable law. This
gives a natural generalisation of the scaling limit for the Erdõs-Renyi
random graph, and complements recent work on random graph scaling limits of
various authors including Bhamidi, Broutin, Duquesne, van der Hofstad, van
Leeuwaarden, Riordan, Sen, M. Wang and X. Wang.
This is joint work in progress with Guillaume Conchon-Kerjan (ENS Paris).

**Daniela Kuhn (Birmingham),
**
*
The existence of designs -- beyond quasirandomness
*

The Existence conjecture for combinatorial designs has its roots in the 19th
century, and was recently proved by Peter Keevash. We give a new proof of
this result, based on the method of iterative absorption. In fact, a
`regularity boosting technique’ allows us to extend our main decomposition
result beyond the quasirandom setting and thus to generalise the results of
Keevash. In particular, we obtain a resilience version and version for
hypergraphs of large minimum degree. In this talk, I will present our new
results, give a brief outline of the history of the Existence conjecture and
provide an overview of our methods. This is joint work with Stefan Glock,
Allan Lo and Deryk Osthus.

**Bruce Reed (CNRS/McGill),
***
The typical structure of graphs in a hereditary family
*

A family is hereditary if it is closed under the taking of
induced subgraphs, or equivalently characterized by a list of forbidden
induced subgraphs. If this list consists of just one graph H, then the
graphs in the family are called H-free. We discuss a conjecture of Reed and
Scott on the structure of typical H-free graphs, and its proof for various
specific H. We discuss related work including the result, joint with Pach
and Yuditsky, that almost every string graph is the intersection graph of a
family of convex sets.

**Paul Seymour (Princeton),
**
*
Rainbow paths
*

Fix a vertex-colouring of a graph G (in any number of colours). An
induced subgraph H of G is *rainbow* if all its vertices have
different colours. There must be a rainbow two-vertex path (unless G
has no edges), but what if G has huge chromatic number and bounded clique
number? Is there then anything bigger that it must contain as a rainbow
induced subgraph? (Yes; for instance it must contain a rainbow
three-vertex induced path, and proving this is a nice little puzzle.)
We give a complete answer -- any path, and any induced subgraph of
a path, and nothing else.
Joint work with Alex Scott.

**David Wood (Monash),
**
*
Defective colouring of graphs excluding a subgraph or minor
*

Archdeacon (1987) proved that graphs embeddable on a fixed
surface can be 3-coloured so that each colour class induces a subgraph
of bounded maximum degree. Edwards, Kang, Kim, Oum and Seymour (2015)
proved that graphs with no K_{t+1}-minor can be t-coloured so that
each colour class induces a subgraph of bounded maximum degree. We
prove a common generalisation of these theorems with a weaker
assumption about excluded subgraphs. This result leads to new
defective colouring results for several graph classes, including
graphs with linear crossing number, graphs with given thickness (with
relevance to the earth-moon problem), graphs with given stack- or
queue-number, linklessly or knotlessly embeddable graphs, graphs with
given Colin de Verdière parameter, and graphs excluding a complete
bipartite graph as a topological minor. This is joint work with
Patrice Ossona de Mendez and Sang-il Oum.