Discrete Geometry and Combinatorics Seminar Autumn 2015

All seminars (unless otherwise stated) will take place on Tuesdays at 5.00pm in Room 707 in the Mathematics Department (25 Gordon Street). There will be tea afterwards in Room 606 in the Mathematics Department (25 Gordon Street) - see how to find us for further details. If you require any more information on the Discrete Geometry and Combinatorics seminars please contact Dr John Talbot e-mail: j.talbot AT ucl.ac.uk or tel: 020-7679-4102.

20 October 2015

Jan Foniok, Manchester Metropolitan University

Title: Hedetniemi's graph-colouring conjecture and adjoint functors

Hedetniemi's conjecture links the chromatic number of the product of two graphs to the chromatic numbers of the two factors: namely, that \chi(G \times H) = \min\{\chi(G),\chi(H)\}.

Simple to formulate, yet the conjecture seems hard to solve, having been open for almost 50 years now. I will present an approach using adjunction in the categories of graphs or digraphs and homomorphisms (but no prior knowledge of category theory is assumed). My objective is mainly to stimulate interest in the topic that may lead to new, productive ideas.

3 November 2015

Ewan Davies, LSE

Title: Independent Sets, Matchings, and Occupancy Fractions

We use a new technique to prove a strengthening of Jeff Kahn's theorem that disjoint unions of K_{d,d}'s maximise the number of independent sets in a bipartite d-regular graph. In probabilistic language, we show that for bipartite d-regular graphs and all λ, the occupancy fraction of the hard-core model with fugacity λ is maximised by K_{d,d}. The method can be extended to non-bipartite graphs, applied to matchings where the analogue of Kahn's result was not previously known, and used to provide lower bounds. For this talk the focus is on the background and the key idea: defining and solving an optimisation problem over distributions of local random variables that use the model directly.

17 November 2015

Laszlo Vegh, LSE

Title: A strong polynomial algorithm for generalised flow maximisation


24 November 2015

David Ellis, QMUL

Title: Stability results for some geometric inequalities, via entropy


1 December 2015

Konrad Swanrpoel, LSE

Title: Thin cones and distinct distances in normed spaces


8 December 2015

Prof Peter Keevash University of Oxford

Title: Counting design

A Steiner Triple System on a set X is a collection T of 3-element subsets of X such that every pair of elements of X is contained in exactly one of the triples in T. An example considered by Plücker in 1835 is the affine plane of order three, which consists of 12 triples on a set of 9 points. Plücker observed that a necessary condition for the existence of a Steiner Triple System on a set with n elements is that n be congruent to 1 or 3 mod 6. In 1846, Kirkman showed that this necessary condition is also sufficient. In 1974, Wilson conjectured an approximate formula for the number of such systems. We will outline a proof of this conjecture, and a more general estimate for the number of Steiner systems. Our main tool is the technique of Randomised Algebraic Construction, which we introduced to resolve a question of Steiner from 1853 on the existence of designs.