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

Schedule

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.


Abstracts

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