Below you'll find the program 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 CON 1.06 (Connaught House|), unless stated below. Please contact the seminar administrator on seminar@maths.lse.ac.uk|, for further information about any of these seminars.
Upcoming Speakers:
2012
Thursday 1 March
Peter Keevash| (Queen Mary)
TBA
Friday 2 March, 12.05pm, STC.S421 (St Clements)
Penny Haxell |(Waterloo)
On packing and covering in hypergraphs
We discuss some recent developments on the following long-standing problem known as Ryser's conjecture. Let $H$ be an $r$-partite $r$-uniform hypergraph. A matching in $H$ is a set of disjoint edges, and we denote by $\nu(H)$ the maximum size of a matching in $H$. A cover of $H$ is a set of vertices that intersects every edge of $H$. It is clear that there exists a cover of $H$ of size at most $r\nu(H)$, but it is conjectured that there is always a cover of size at most $(r-1)\nu(H)$.
Thursday 8 March
Giacomo Zambelli | (LSE)
TBA
Friday 16 March, 12.05pm, STC.S421 (St Clements)
Garth Dales| (Leeds)
Second duals of algebras of continuous functions and measures
We first look at algebras of continuous functions on a compact space K, and their second duals. This is the algebra of continuous functions on the hyper-Stonean cover of K, which we shall describe. Then we shall consider the second dual of algebras of measures on a locally compact group (usually the circle group), and see the extent to which there is a product on this second dual that throws light on the original algebra. The story involves Stone-Cech compactifications, Borel functions, and ultrafilters.
The talk is related to a joint memoir:
H. G. Dales, A. T.-M. Lau, and D. Strauss, Second duals of measure algebras, Dissertationes Math., to appear soon
Friday 11 May, 12.05pm, STC.S421 (St Clements)
Horst Martini |(Chemnitz)
TBA
Thursday 31 May
Doreen Thomas| (University of Melbourne)
Relay augmentation for the lifetime extension of a wireless sensor network
In wireless sensor networks a key objective is to optimise the lifetime of individual nodes. In most wireless sensor networks the bulk of a sensor's energy consumption is attributable to communication and the energy consumption is proportional to some power of the communication distance. Hence those nodes communicating over the longest links are likely to die first and we may consider these links to be the bottlenecks.
This talk considers the problem of adding a fixed number of relays to a wireless sensor network so that the longest link in the associated transmission network is minimised. In addition, the network should also be highly connected in the sense that it can continue to operate if one or more of the nodes or links is compromised. This can be modelled as an optimisation problem known as the bottleneck c-connected Steiner network problem. We show that in the case c = 2 this problem can be exactly and efficiently solved using the combinatorial structure of the well-known block cut-vertex decomposition of graphs, and geometric properties of the 2-relative neighbourhood graphs and farthest colour Voronoi diagrams. We discover new properties of optimal bottleneck Steiner 2-connected networks, and produce polynomial-time exact algorithms when we add no more than two Steiner points. More generally, this talk demonstrates the important role graph theory and geometry can play in the efficient design of wireless sensor networks.
This work is done in collaboration with Marcus Brazil and Charl Ras at The University of Melbourne.
Previous seminars in this series: 2012|, 2011|, 2010|, 2009|, 2008|, 2007|, 2006|, 2005|, 2004 and before|.