Home > Department of Mathematics > Seminars > Seminar on Discrete Mathematics and Game Theory
How to contact us

Department of Mathematics
Columbia House
London School of Economics
Houghton Street
London WC2A 2AE, UK


Email: maths.info@lse.ac.uk
Tel: +44(0)207 955 7732/7925
Connect with LSE Maths: Twitter


Click here for information on how to get to LSE using public transport and maps of the campus

Seminar on Discrete Mathematics and Game Theory

Below you'll find the programme for the Seminar on Discrete Mathematics and Game Theory. The Seminar normally takes place on Thursdays from 2.00 pm - 3.00 pm in room TW2.3.01 (Tower Two, Clement's Inn - entrance through Tower One), unless stated below. Questions, suggestions, etc., about the seminar can be forwarded to
the seminar administrator (Room COL 3.14), by sending an e-mail to: seminar@maths.lse.ac.uk.

Upcoming Speakers: 

Thursday 8 October - Ben Barber, Birmingham
Edge decompositions of graphs

An F-decomposition of a graph G is a partition of E(G) into copies of F.  Determining whether a graph has an F-decomposition is NP-complete, but it is much easier to find 'fractional' decompositions.  I'll explain the connection between these ideas and how it can be exploited to attack Nash-Williams' conjecture that every large graph on n vertices with minimum degree at least 3n/4, e(G) divisible by 3 and every degree even has a triangle decomposition.

Thursday 15 October - Mykhaylo Tyomkyn (Birmingham)
Title and abstract TBC

Thursday 22 October - Anthony Nixon (Lancaster)
Rigidity of graphs on expanding spheres

A graph G is rigid if some (equivalently, all) generic realisation of G, in Euclidean space, admits no edge-length preserving continuous deformation of its vertices. For realisations in 1D the answer is simple and for 2D there is an elegant description of rigidity purely in terms of the graph, however for higher dimensions there is no known combinatorial characterisation. I will describe the basic theory of rigid graphs.

I will then move on to recent joint work with Bernd Schulze, Shin-Ichi Tanigawa and Walter Whiteley. We consider graphs realised on concentric d-spheres in d+1 dimensions where the radii of the spheres are allowed to vary independently. I will discuss, in terms of the dimension and the number of spheres varying at different rates, when combinatorial descriptions of rigidity are possible and when they are not. The appropriate combinatorial objects will be count matroids arising from submodular functions using coloured graphs.

Thursday 29 October
Speaker, title and abstract TBC

Tuesday 3 November 3.00-4.00pm - Andres Perea (Maastrict)
*** Please note change of usual date and time - event held in TW2.3.01 as normal***
Title and abstract TBC

Thursday 12 November
Speaker, title and abstract TBC

Thursday 19 November
Speaker, title and abstract TBC

Thursday 26 November - Yufei Zhao (Oxford)
Title and abstract TBC

Thursday 3 December
Speaker, title and abstract TBC

Thursday 10 December
Speaker, title and abstract TBC

Previous seminars in this series:

2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004 and before