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 firstname.lastname@example.org, for further information about any of these seminars.
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:
present briefly the topic and the main issues
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