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

Schedule

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.


Abstracts

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