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.

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.

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