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

Abstract:

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

Abstract:

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

Abstract:

TBC

## 24 November 2015

### David Ellis, QMUL

##### Title: Stability results for some geometric inequalities, via entropy

Abstract:

TBC

## 1 December 2015

### Konrad Swanrpoel, LSE

##### Title: Thin cones and distinct distances in normed spaces

Abstract:

TBC

## 8 December 2015

### Prof Peter Keevash University of Oxford

##### Title: Counting design

Abstract:

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.