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


8 December 2015

Prof Peter Keevash University of Oxford

Title: TBC


Previous discrete geometry and combinatorics seminars

Page last modified on 23 nov 15 10:22