Mathematical Institute

University of Oxford

Wednesday 27 May 2015

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

10.30 am
Coffee

11.00 am
**Amin Coja-Oghlan (Goethe University, Frankfurt)
**

*
Random graph coloring*

11.55 am
**
Louigi Addario-Berry (Montreal)
**

*
Most trees are short and fat*

12.50 pm
Lunch

2.15 pm
**
Maria Chudnovsky (Princeton)
**

*
Coloring square-free perfect graphs
*

3.10 pm
**
Andrew Thomason (Cambridge)
**

*
Quick and Easy containers*

4.05 pm
Tea

4.30 pm
**Paul Seymour (Princeton)
**

*
Consecutive holes*

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.

**Louigi Addario-Berry (Montreal),
**
*
Most trees are short and fat
*

Let T be any critical or subcritical Galton-Watson tree. Write ht(T) for the height of T (the greatest distance of any node from the root) and wid(T) for the width of T (the greatest number of nodes at any level). We study the relation between ht(T) and wit(T).

In the case when the offspring distribution p=(p_i,i≥0) has finite variance, both ht(T) and wid(T) are typically of order vol(T)^{1/2}, and have sub-Gaussian upper tails (A-B, Devroye and Janson, 2013). Heuristically, as the tail of the offspring distribution becomes heavier, the tree T becomes "shorter and bushier." We prove this heuristic is correct: there exist constants c,C > 0, depending only on p_0 and p_1, such that for all a > 0

P(ht(T) > a*wid(T)) < Ce^{-ac}.

This is in general best possible (up to the values of c and C). Given suitable additional information about p, we obtain stronger bounds, in particular obtaining the "correct" bounds for alpha-stable trees (alpha in (1,2]). We also state a combinatorial conjecture which, if true, would yield a substantial strengthening of our main result: informally, the conjecture is that binary trees are the tallest.

**Maria Chudnovsky (Princeton),
**
*
Coloring square-free perfect graphs
*

Perfect graphs are a class of graphs that behave particularly well with respect to coloring. In the 1960's Claude Berge made two conjectures about this class of graphs, that motivated a great deal of research in the field in the second half of the 20th century. One of the conjectures, The Weak Perfect Graph Conjecture, was solved by Laszlo Lovasz in 1972, the other, The Strong Perfect Graph Conjecture, by Robertson, Seymour, Thomas and the speaker in the early 2000's.

The following remained open however: design a combinatorial algorithm that produces an optimal coloring of a perfect graph. Recently, in joint work with Lo, Maffray, Trotignon and Vuskovic we were able to construct such an algorithm under the additional assumption that the input graph is square-free (contains no induced four-cycle). Historically, the class of square-free perfect graphs seems to be a good special case to look at; in particular, this was the last special case of the Strong Perfect Graph Conjecture that was solved before the general one.

**Amin Coja-Oghlan (Goethe University, Frankfurt),
***
Random graph coloring
*

A famous application of the probabilistic method is the randomised construction of a graph with high girth and high chromatic number. For instance, the random graph G(n,m) with m=dn/2 for a fixed d>0 has high girth with a non-vanishing probability. Moreover, for any fixed k the average degree d can be chosen such that the chromatic number exceeds k with high probability. The aim of this talk is to investigate the interplay of short-range and long-range effects among the colors assigned to different vertices of G(n,m).

**Paul Seymour (Princeton),
**
*
Consecutive holes
*

A "hole" in a graph is an induced subgraph which is a cycle of length
at least four. In joint work with Alex Scott, we have proved and strengthened
a well-known conjecture of Gyarfas from 1985. The conjecture was:

*If G is triangle-free and has sufficiently large chromatic number then
it has a hole of length at least 100.*

(100 can be replaced by anything else, of course.) This has been quite a
stubborn problem; all that was previously known was that some hole has length
divisible by three (Bonamy, Charbit and Thomasse), and some hole has odd length
at least seven (joint with Chudnovsky). In particular, until now it was not
known that such graphs have a hole of length more than seven. Gyarfas also
conjectured a strengthening:

*If G is triangle-free and has sufficiently large chromatic number then
it has a hole of odd length at least 100.*

Both of these are true, and something much stronger. We have shown:

*If G is triangle-free and has sufficiently large chromatic number then
there are 100 holes in G whose lengths are consecutive.*

**Andrew Thomason (Cambridge),
**
*
Quick and Easy containers
*

A set of containers for a hypergraph is a collection of subsets of the
vertices, these being called "containers", such that every independent set
is inside a container. The fact that small collections of containers exist
(shown recently by Balogh-Morris-Samotij and by Saxton-Thomason) has found
some applications. We shall outline two ways to find containers: one quick
way, which however gives slightly more containers than necessary, and one
optimal way, which is somewhat easier than existing methods. (Joint with
David Saxton.)