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)
**

*
Improper relaxations of Hadwiger's Conjecture*

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),
**
*
Improper relaxations of Hadwiger's Conjecture
*

Hadwiger's Conjecture asserts that every K_t-minor-free graph has a
proper (t-1)-colouring. This talk is about improper relaxations of
Hadwiger's Conjecture. We prove that every K_t-minor-free graph is
(2t-2)-colourable with monochromatic components of order at most
⌈(t-2)/2⌉. This result has no more colours and much smaller monochromatic
components than all previous results in this direction. We then prove
that every K_t-minor-free graph is (t-1)-colourable with monochromatic
degree at most t-2. This is the best known degree bound for such a
result. Both these theorems are based on a simple decomposition result
of independent interest. Improper colourings are interesting for other
graph classes. For example, Archdeacon (1987) proved that graphs
embeddable on a fixed surface can be 3-coloured with bounded
monochromatic degree. We generalise this theorem for graphs excluding
a complete bipartite graph, leading to new improper colouring results
for graphs with linear crossing number, graphs with given stack- or
queue-number, linklessly or knotlessly embeddable graphs, graphs with
given Colin de Verdière parameter, and graphs with given thickness
(with relevance to the earth-moon problem). This is joint work with
Jan van den Heuvel (arXiv:1704.06536) and Patrice Ossona de Mendez and
Sang-il Oum (arXiv:1611.09060).