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.1.01 (Tower Two, Clement's Inn - entrance through Tower One), unless stated below. Please contact the seminar administrator on seminar@maths.lse.ac.uk, for further information about any of these seminars.

Upcoming Speakers:

Thursday 28 May - CANCELLED

Thursday 4 June - Sebastian Siebertz (TU Berlin)
Algorithmic graph structure theory for sparse graphs -- An overview and recent advances

Algorithmic graph structure theory attempts to explain for natural and important classes of graphs what kind of problems can be solved efficiently on these graphs and develop the corresponding graph structural and algorithmic techniques. A prototypical example from algorithmic graph structure theory is Courcelle's Theorem, stating that all properties of graphs of bounded tree-width that are definable in monadic second-order logic are decidable in linear time. Other important classes with good algorithmic properties are classes of bounded degree, planar graphs, and more generally, classes that exclude a fixed (topological) minor and many more.

As diverse as the examples above of graph classes with a rich algorithmic theory may appear, a feature all these classes have in common is that they are relatively sparse, i.e. graphs in these classes have a relatively low number of edges compared to the number of vertices. This suggests that this sparsity might be an underlying reason why many problems can be solved efficiently on these classes of graphs, even though they otherwise do not have much in common.

Nowhere dense classes were introduced by Nešetřil and Ossona de Mendez as a formalisation of classes of sparse graphs, which generalise all of the above graph classes. Nowhere density turns out to be a very robust concept with several seemingly unrelated natural characterisations and each characterisation yields different algorithmic techniques. We have shown that all properties of graphs that are definable in first-order logic are decidable in almost linear time on any nowhere dense class of graphs. It has been shown before that the first-order model-checking problem cannot be solved efficiently on any somewhere dense class which is closed under subgraphs (under a reasonable complexity theoretic assumption). This supports the intuition that nowhere dense classes are the natural limit for many algorithmic techniques for sparse graph classes.

In this talk, I am going to give an overview over characterisations of nowhere dense graphs and show examples of how these characterisations were recently used to obtain new algorithmic results.

Thursday 11 June - Milan Vojnovic (Microsoft Research)
Title and abstract TBC

Thursday 18 June -  Andre Nies (University of Auckland)
Title and abstract TBC

Thursday 25 June -  Sylvain Sorin (University of Paris 6)
On some advances in zero-sum repeated games

The purpose of this survey talk is to:

  1. present briefly the topic and the main issues
  2. describe some new approaches, results and directions of research. Topics include: uniform and asymptotic analysis, approachability, Shapley operator, stochastic games and games with incomplete information, link with games in continuous time, differential games and games with vanishing stage duration.

Thursday 2 July - seminar details TBA

Previous seminars in this series:

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