Lunchtime Seminars in 2010

Friday 10 December

Steffen Issleib (LSE)
 

Mathematical techniques for solving "learning with trial and error" games

Friday 26 November

Laura Delaney (Trinity College Dublin)

 Valuing Voluntary Disclosure using a Real Options Approach

This paper outlines a real options approach to valuing those announcements which are made by firms outside their legal requirements. Information will be disclosed if the manager of the firm is sufficiently certain that the market response to the announcement will have a positive impact on the value of the firm. The problem is also analysed from (i) a potential shareholder's and (ii) an existing shareholder's perspective. The main finding is that the threat of a corporate control challenge imposed upon the manager better aligns his incentives with those of the existing shareholder. This is shown in two ways; firstly, the manager discloses his information earlier and secondly, the agency costs which the shareholder may incur are noticeably reduced. An implication of this result is that the traditional net present value (NPV) approach is not such a poor proxy for valuing voluntary disclosure as the standard real-options theory would suggest.

Friday 5 November 

Ahmad Abu-Khazneh (LSE) 

Parallel Information Sets and Strategies in Extensive Games   

We discuss game trees with imperfect information, called
extensive games, and the complexity of representing
strategies in such games.  Central is the concept of
parallel information sets, which give rise to a possible
exponential complexity.  

Friday 29 October

Alexey Pokrovskiy (LSE)

Edge growth in graph powers

For a graph G, its rth power, G^r, is constructed by placing an edge between two vertices if they are within distance r of each other. In this talk I will address the question of "how few new edges can the rth power of a graph have?". The main result I show is that, for regular graphs, either the rth power is complete or a positive proportion of new edges are added. I will give a tight lower bound on how small the ratio e(G^r)/e(G) can be for regular graphs. 

 Friday 22 October

Somkiat Trakultraipruk (LSE)

Connectedness of Token Graphs with Labelled Tokens

For a positive integer k and a graph G, we define the token graph (with labelled tokens) T(G; k) to be the graph whose vertices correspond to configurations of k labelled tokens placed at distinct vertices of G, and two configurations are adjacent in T(G; k) if one configuration can be reached from the other by moving one token along an edge of G. In this talk, we show some results related to the question: When is T(G; k) connected?

 Friday 15 October

Konrad Swanepoel (LSE)

Using the Brunn-Minkowski inequality, equitable colourings, the rank lemma and convex optimisation

In the study of the local structure of Steiner minimal trees in normed spaces, the following extremal problem arises:
Let d, k, m be integers and assume that d > 1 and 1 < k < m - 1. In a d-dimensional normed space, find the largest number m of unit vectors such that the sum of any k of them has norm at most 1. I'll derive an upper bound for m in terms of d and k. I'll also consider the case where the unit vectors are required to add up to o. Here I'll sketch the proof of a sharp upper bound. The proofs use a mixture of volume arguments, graph theory, linear algebra and convexity. 

 Friday 25 June

Alexey Pokrovskiy (LSE)

Hereditary properties of graphs

A graph property is just some set of graphs. The property is called hereditary if it is closed under taking induced subgraphs, i.e., if G posseses the property, then any graph obtained from G by vertex deletions will still possess the property. Examples include k-partite graphs, forests and line graphs. Many questions in graph theory can be phrased in terms of properties. It turns out that certain things can be said about hereditary properties in general. In particular the speed of a property is defined as the number of n-vertex graphs posessing the property. If the property is hereditary then there are surprisingly few things that this function can be. I will survey results in this area and the techniques used to prove them.  

 Friday 18 June

Marta Casetti (LSE)

Finding Gale Strings

 The problem 2-NASH of finding a Nash equilibrium of a bimatrix game belongs to the complexity class PPAD. This class comprises computational problems that are known to have a solution by means of a path-following argument. For bimatrix games, this argument is provided by the Lemke-Howson algorithm. It has been shown that this algorithm is worst-case exponential with the help of dual cyclic polytopes, where the algorithm can be expressed combinatorially via labelled bitstrings defined by the "Gale evenness condition" that characterize the vertices of these polytopes. We define the combinatorial problem ANOTHER GALE STRING whose solutions define the Nash equilibria of games defined by cyclic polytopes, including games where the Lemke-Howson algorithm takes exponential time. Proving that this problem is PPAD-complete would imply that 2-NASH is PPAD-complete, in a much simpler way than the currently known proofs, including the original proof by Chen and Deng. However, we show that ANOTHER GALE STRING is solvable in polynomial time by a simple reduction to PERFECT MATCHING in graphs, making it unlikely to be PPAD-complete.

 Friday 11 June

Nick Bingham (LSE)

Law of Averages, Law of Errors, ... 

The Law of Averages is known to the man/woman in the street -- `fair coins come down heads about half the time', etc. Mathematically, this is the Law of Large Numbers (LLN) -- or rather, a LLN. The gist of this is that independent errors tend to cancel. There is a whole class of theorems making this precise, under a wide variety of conditions.

The Law of Errors is unknown to the man in the street, but familiar to the physicist in the street, as `errors are normally distributed about the mean'. Mathematically, this is the Central Limit Theorem (CLT) -- or rather, a CLT. Again, there is a whole class of theorems making this precise, again under a wide variety of conditions (and addressing the various obvious questions -- why normal, etc.).

The third of the classical trilogy is the Law of the Iterated Logarithm (LIL), known to the probabilist in the street (such as myself).
Then nowadays there is a fourth leg to this piece of furniture -- the Large Deviations Principle (LDP).
The talk is a general overview of such limit theorems in probability theory, and their applications. 

Friday 8 May

David Ferguson (LSE)

A removal lemma for systems of polynomial equations over finite fields

Recently, Kral', Serra and Vena and, independently, Shapira proved that (for X_1,...,X_m subsets of the finite field F_q and A a (k × m) matrix with coefficients in F_q and rank k) if the linear system Ax = b has o(q^{m-k}) solutions with x_i \in X_i, then one can destroy all these solutions by deleting o(q) elements from each X_i. Both groups of authors used coloured versions of the hypergraph removal lemma but for hypergraphs with different degrees of uniformity.

Using similar methods, we prove that, if an equation of the form: x_1x_2...x_{p_1} + x_{p_1 +1}x_{p_1 +2}...x_{p_2} + ...+ x_{p_s+1}x_{p_s +2}...x_{m-1} + x_m = b has o(q^{m-1}) solutions with x_i \in X_i then one can destroy all these solutions by deleting o(q) elements from each X_i.  

(Joint work with Dan Král', Univerzita Karlova v Praze)

Friday 12 March

 Zibo XU (LSE)

 A Stochastic Ramsey Theorem 

 A PDF of the abstract for this talk can be found here. 

Friday 6 February

Adam Ostaszewski (LSE)

Analysis on Normed Groups 

An algebraic group G may be endowed with a topology bestowing some continuity on the group multiplication (x,y) → xy. In a topological group there is joint continuity as well as continuity of inversion. The most recent work (Bouziad, succeeding Ellis and Namioka) has focussed on separate continuity implying joint continuity, which I briefly review.

The main topic is the less well understood setting of a norm on G for which (i) ||x||=0 iff x=e, (ii) ||xy||≤||x||+||y||, and (iii) ||x^{-1}||=||x||.
This permits one-sided continuity of shifts. Normed groups arise naturally in the study of autohomeomorphisms and provide a very rich structure for analysis.

Three examples: A squared Pettis theorem holds. The Effros open mapping theorem holds. Locally compact normed groups support an invariant Haar measure.

They are a natural context for regular variation.
They exhibit a Cauchy dichotomy: being either topological, or pathological.

Friday 19 February

Jozef Skokan (LSE)

Multicolour Ramsey numbers for Odd Cycles 

For a graph L and an integer k>1, R_k(L) denotes the corresponding Ramsey number: the smallest integer N for which for any edge-colouring of the complete graph K_N by k colours there exists a colour i for which the corresponding colour class contains L as a subgraph. In 1973, Bondy and Erdös proved that for an odd cycle C_n on n vertices we have R₂( C_n)=2n-1 and conjectured that R_k( C_n)= 2^k-1(n-1)+1 for n>3. They also provided an upper bound R_k( C_n) < (k+2)!n. This conjecture is confirmed only for k=3 if n is very large large. We will show that R_k( C_n)< k3^k-1n+o(n), where o(1)→0 as n→∞.

Friday 12 February

Steffen Issleib (LSE)

Friday 5 February

Derek Wan (LSE)

The Supermarket Model with Memory: Rapid Mixing by Coupling

 Friday 29 January

Graham Brightwell (LSE)