One-Day Meeting in Combinatorics
Mathematical Institute
University of Oxford

Wednesday 23 May 2018

A One-Day Meeting in Combinatorics will be held in the Mathematical Institute, University of Oxford on Wednesday 23 May 2018. A provisional schedule and abstracts can be found below.

Schedule

10.30 am                      Coffee

11.00 am                      Benny Sudakov (Zurich)
                                     Rainbow structures, Latin squares & graph decompositions

11.55 am                      Paul Wollan (Rome)
                                     A “grid” theorem for vertex minors and rankwidth

12.50 pm                      Lunch

2.15 pm                        Maria Chudnovsky (Princeton)
                                     Coloring graphs with forbidden induced subgraphs

3.10 pm                        Kristina Vušković (Leeds)
                                     Clique cutsets beyond chordal graphs

4.05 pm                        Tea

4.30 pm                        Daniel Kral (University of Warwick)
                                     Graph limits and extremal combinatorics


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

Daniel Kral (University of Warwick), Graph limits and extremal combinatorics

The theory of graph limits aims at providing analytic tools to model and study large graphs. Such tools have found many applications in various areas of computer science and mathematics. We start with providing a brief introduction to this area, which will include the closely related flag algebra method, which changed the landscape of extremal combinatorics. We will then focus on the uniqueness of optimal configurations in extremal combinatorics. An empirical experience suggests that optimal solutions to extremal graph theory problems can be made asymptotically unique by introducing additional constraints. We will show that this phenomenon is not true in general. In particular, we will disprove the following conjecture of Lovasz, which is often referred to as saying that "every extremal graph theory problem has a finitely forcible optimum": every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints such that the resulting set is satisfied by an asymptotically unique graph. The talk is based on joint work with Andrzej Grzesik and Laszlo Miklos Lovasz.


Maria Chudnovsky(Princeton), Coloring graphs with forbidden induced subgraphs

The problem of testing if a graph can be colored with a given number k of colors is NP-complete for every k>2. But what if we have more information about the input graph, namely that some fixed graph H is not present in it as an induced subgraph? It is known that the problem remains NP-complete if H is not a subgraph of a path, and the question has been extensively studied in the case when H is a path. Only two cases remain open: 3-coloring a graph with no induced t-vertex path when t>=8, and 4-coloring a graph with no induced 6-vertex path. Recently in joint work with Sophie Spirkl and Mingxian Zhong we settled one of these two problems and found a polynomial-time algorithm to determine if a graph with no induced 6-vertex path admits a 4-coloring (and finds such a coloring if it exists). In this talk we will survey what is known on the topic, and discuss the main ideas of our recent algorithm.


Benny Sudakov (Zurich), Rainbow structures, Latin squares & graph decompositions

A subgraph of an edge-coloured graph is called rainbow if all its edges have distinct colours. The study of rainbow subgraphs goes back to the work of Euler on Latin squares. Since then rainbow structures were the focus of extensive research and found applications in design theory and graph decompositions. In this talk we discuss how probabilistic reasoning can be used to attack several old problems in this area. In particular we show that well known conjectures of Ryser, Hahn, Ringel, and Graham-Sloane hold asymptotically. Based on joint works with Alon, Montgomery, and Pokrovskiy.


Paul Wollan (Rome), A “grid” theorem for vertex minors and rankwidth

The classic grid theorem, due to Robertson and Seymour, states that every graph with sufficiently large treewidth contains the k x k grid as a minor, in effect showing that grids form a family of canonical graphs which force large treewidth. We consider the analogous statement for rankwidth and cut-rank decompositions where one recursively decomposes a graph along edge cuts inducing bipartite subgraphs with low rank adjacency matrices. We show that there exists a similar canonical family of graphs, which we call paths of half-graphs, such that that any graph with sufficiently large rankwidth must contain a large path of half-graphs. This is joint work with Jim Geelen, O-joung Kwon, and Rose McCarty.


Kristina Vušković (Leeds), Clique cutsets beyond chordal graphs

Truemper configurations (i.e. thetas, pyramids, prisms and wheels) have played an important role in the study of several complex hereditary graph classes such as perfect graphs and even-hole- free graphs, appearing both as excluded configurations, and as configurations around which graphs can be decomposed. In this talk, we present results about several classes of graphs defined by excluding all Truemper configurations except certain wheels. We give clique cutset decomposition theorems for these classes, which we use to obtain several algorithmic consequences.