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