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