Mathematical Institute

University of Oxford

Wednesday 1 June 2016

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

10.30 am
Coffee

11.00 am
**Mihyun Kang (Graz)
**

*
Jigsaw percolation on random hypergraphs*

11.55 am
**János Pach (Budapest/Lausanne)
**

*
Distinct distances: Quo vadis?*

12.50 pm
Lunch

2.15 pm
**
Leslie Goldberg (Oxford)
**

*
Approximately counting list H-colourings
*

3.10 pm
**
Gábor Tardos (Budapest)
**

*
Extremal theory of ordered graphs*

4.05 pm
Tea

4.30 pm
**
Penny Haxell (Waterloo)
**

*
Matchings in tripartite hypergraphs*

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.

**Leslie Goldberg (Oxford),
**
*
Approximately counting list H-colourings
*

An H-colouring of a graph G is a homomorphism from G to H (a map
from the vertices of G to the vertices of H that maps edges of G to edges
of H). The "classification programme" in computational complexity aims to
classify graphs H according to the difficulty of algorithmic problems, for
example, the problem of constructing a homomorphism from an input graph G to
H, or the problem of counting homomorphisms from G to H or (more recently)
the problem of approximately counting these homomorphisms. I will explain
the classifications that are known, focussing especially on "list
H-colouring'', which generalises H-colouring in the same way that "list
colouring'' generalises ordinary (proper) vertex colouring. We still don't
know a complete classification for approximately counting H-colourings, but
for approximately counting list H-colourings, there is more progress. Here
it turns out that there is a trichotomy in the approximation complexity,
based on hereditary graph classes.
The talk will describe joint work with Andreas Galanis and Mark Jerrum.

**Penny Haxell (Waterloo),
**
*
Matchings in tripartite hypergraphs
*

A matching in a hypergraph is a set of disjoint edges. It is a
well-known difficult problem to give good lower bounds on the maximum
size of a matching in a hypergraph in terms of other natural parameters.
Here we focus on the special case of tripartite hypergraphs: those
for which the vertex set can be partitioned into three parts,
such that each edge contains exactly one vertex from each part. If a
tripartite hypergraph is r-regular (meaning that each vertex is in
exactly r edges) with n vertices in each class then it has a
matching of size at least n/2, and this is tight for
certain special hypergraphs. We investigate how this bound can be
improved for all other hypergraphs.

**Mihyun Kang (Graz),
***
Jigsaw percolation on random hypergraphs
*

Jigsaw percolation process on graphs was introduced by Brummit, Chatterjee,
Dey, and Sivakoff. Whether the process percolates may be viewed as a
characterisation of joint connectivity of two graphs on a common vertex set.
In this talk we consider a hypergraph analogue of this process for a family
of possible definitions of connectivity. We provide the asymptotic order of
the critical threshold probability for percolation when both hypergraphs are
chosen binomially at random, generalising a graph result of Bollobás,
Riordan, Slivken, and Smith. (Joint work with Bollobás, Cooley, and Koch.)

**János Pach (Budapest/Lausanne),
**
*
Distinct distances: Quo vadis?*

The landmark result of Guth and Katz (Ann. Math., 2015), which nearly
settled Erdős's conjecture on the minimum number of distinct distances
determined by n points in the plane, raised high hopes for applying
algebraic geometry to other problems in combinatorial geometry. To what
extent have these hopes been fulfilled? After discussing some recent results
on distances between geometric objects, I will highlight a number of open
questions that may be accessible by the new techniques.

**Gábor Tardos (Budapest),
**
*
Extremal theory of ordered graphs
*

Ordered graphs are defined as simple graphs with a linear order on the
vertices. This allows for an extension of the classical (Turán-type)
extremal graph theory to more subtle questions, where a subgraph is
forbidden only with a certain vertex-order. Surveying several papers, I will
present some first steps toward an extremal theory of ordered graphs as well
as lots of open questions. Here is my favorite from Furedi and Hajnal ('92):
G is an ordered bipartite graph (i.e., an ordered graph with no edge
starting at or after the end of another edge) and the underlying graph is
cycle-free. Is the maximal number of edges in a G-free ordered graph on n
vertices almost linear in n?