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