|
12th December 2008
|
Derek Wan (LSE)
The Supermarket Model with Memory
Abstract
In this talk, I will first introduce the Supermarket model and discuss its key results and methods. This will lead onto a discussion of the same model with the introduction of memory.
|
|
5th December 2008
|
Steffen Issleib (LSE)
Bounds on mixing time via coupling
Abstract
The talk will be on long term behaviour of Markov chains, in particular the speed of convergence to the stationary measure. Here I will focus on the Curie-Weiss model with external field. First I will give an introduction to the concept of coupling and via examples introduce mixing time and total variation distance. Then I will talk about the use of coupling in the calculation of both theoretical bounds on the mixing time and in the implementation of Monte Carlo Simulations.
|
|
28th November 2008
|
Julian Merschen (LSE)
Computing an Optimal Strategy for One-Player Simple Stochastic Games in Strongly Polynomial Time
Abstract
We introduce simple stochastic games (SSG) and give reasons why it is of interest to find the optimal strategy when considering a one-player SSG. In this setup, the optimal strategy can be found by solving a linear program (LP). We show that the constraint matrix of the corresponding linear program contains entries only from the set {-2,0,1,2}. We introduce Vavasis' and Ye's layered interior point algorithm, the running time of which is polynomial and only depends on the encoding of the constraint matrix of the corresponding LP. For one-player SSG we show that we can always bound the encoding of the constraint matrix by O(n2), where n is the number of vertices of the one-player SSG. This implies that the problem of finding the optimal strategy in the one-player SSG can be found in O(n5.5), which is strongly polynomial.
|
|
21st November 2008
|
Tony Forbes
Beyond Zoe's Design
Abstract
A Steiner system S(t,k,v) is a block design consisting of a set of v points and a set of k-element sets of points, called blocks, where each t-element set of points is contained in precisely one block.
I shall be discussing the construction of Steiner S(2,4,v) systems where the points are coloured subject to the rule that each block contains three points of one colour and one point of a different colour. Clearly, the trivial S(2,4,4) can be 2-coloured in this manner. Moreover, there is a construction that produces an (m+1)-coloured S(2,4,3v+1) from an m-coloured S(2,4,v) system, and hence we have an infinite sequence v = 4, 13, 40, 121, ... for which these designs are known.
The existence of S(2,4,v) systems not included in this sequence has been an interesting problem in design theory for over 25 years. Recently, constructions have been successful in a few isolated cases, such as Zoe's Design (v=61) and the Design of the Century (v=100). However, we are still nowhere near a satisfactory solution to the problem. In this talk I shall present what I believe might be a possible way to make further progress.
|
|
14th November 2008
|
Marta Casetti (LSE)
PPAD completeness of equilibrium computation
|
|
7th November 2008
|
Viresh Patel (LSE)
A Hypergraph Extension of Turán's Theorem
Abstract
An r-uniform hypergraph (referred to henceforth as an r-graph) H=(V(H),E(H)) is a set of vertices V(H), together with a set of edges E(H) ⊆ V(H)(r), where V(H)(r) is the set of subsets of V of size r. Thus a 2-uniform hypergraph is a graph. We say that an r-graph H is a subgraph of an r-graph F if there exists an injection θ: V(H) → V(F) such that θ maps each edge of H onto an edge of F. We say that F is H-free if H is not a subgraph of F.
Given an r-graph H, let ex(n,H) denote the largest number of edges an n-vertex r-graph can have if it is H-free. The Turán density of an r-graph H is
π(H) = limn → ∞ ex(n,H) ⁄ (nr) .
For r=2 the Erdös-Stone theorem gives the value of π(H) for all non-bipartite graphs H, however for r > 2, the problem of determining Turán densities has proven to be hard. Indeed, until recently, only a finite number of Turán densities were known. I shall present a result of Mubayi, which, for each fixed r, gives the Turán densities of an infinite number of r-graphs.
|
|
31st October 2008
|
Hessah Al-Motairi (LSE)
A model for capacity increase with the option to abandon
Abstract
We consider the problem of determining the optimal investment level that a firm should maintain in the presence of random price or demand fluctuations. The project's capacity level can be increased at any time and at given proportional costs. Also, the can be irreversibly abandoned at any time. The objective is to determine the projects capacity level and the project's abandonment time that maximize the associated expected, discounted payoff.
|
|
17th October 2008
|
Marco Timmer
Rendezvous on a discrete labelled interval
Abstract
In a rendezvous problem two players have the common goal to meet as soon as possible. The players are initially located on a search space (in this case a discrete labelled interval) according to a probabilities supported on this search space. The main question is such problems is ``how should the players behave to minimize their expected meeting time?'' So in fact we are interested in optimal search strategies describing their optimal behavior.
We consider two versions of the problem inspired by and based on work of Alpern and Howard. In the first version the players are placed on the interval according to the same probability distribution and moreover they must adopt the same strategy. In the second version the players are in general placed on the interval according to distinct probability distributions and they are allowed to adopt different search strategies. The first version is called the symmetric problem and the second version is called the asymmetric problem.
In the talk the problem is introduced. After that, new work for both the symmetric and the asymmetric versions of the problem is presented. This work includes a dynamic programming approach for the symmetric problem, the optimal search strategies for a particular class of distributions in the asymmetric problem and also an analysis between the symmetric problem and the asymmetric problem with equal distributions.
|
|
10th October 2008
|
Tobias Müller (TU Eindhoven)
A local limit theorem for the critical random graph
Abstract
The Erdös-Rényi random graph G(n,p) is constructed on a set of n vertices, where each of the possible edges is included with probability p independently of all other edges. In their seminal work around 1960, Erdös and Rényi showed that if we take p=c/n (with c>0 fixed) then the largest component of G(n,p) has Θ( log n ) vertices if 0<c<1 and Θ(n) vertices if c > 1. They also noted that if p=1/n then the largest component is of order n2/3.
Since then many authors have considered the random graph inside the ``critical window'', when p=1/n+λ n-4/3 for some fixed λ. It is known that for such p the k largest components all have Θ( n2/3 ) vertices for any fixed k, and that the vector (n-2/3L1(G(n,p)), ..., n-2/3Lk(G(n,p)) ) has a continuous limiting distribution for all k (where Li denotes the i-th largest component).
In this work we shall derive an explicit expression for the joint probability density function of limiting distribution of this random vector and a possibly useful differential equation that the probability density function of limiting distribution of n-2/3 L(G(n,p)) satisfies in this range.
This is a joint work with Remco van der Hofstad and Wouter Kager.
|
|
13th June 2008
|
Ross Kang (McGill)
Acyclic and frugal colourings of graphs
Abstract
Given a graph G = (V, E), a proper vertex colouring of V is t-frugal if no colour appears more than t times in any neighbourhood and is acyclic if each of the bipartite graphs consisting of the edges between any two colour classes is acyclic. For graphs of bounded maximum degree, Hind, Molloy and Reed (Combinatorica, 1997) studied proper t-frugal colourings and Yuster (Discrete Math, 1998) studied acyclic proper 2-frugal colourings. In this paper, we expand and generalise this study. In particular, we consider vertex colourings that are not necessarily proper, and in this case, we find qualitative connections with colourings that are t-improper -- colourings in which the colour classes induce subgraphs of maximum degree at most t -- for choices of t near to d.
This is joint work with Tobias Müller (TU Eindhoven).
|
|
9th May 2008
|
Balázs Montágh (UCL)
New applications of finite geometry in extremal graph theory
Abstract
One of the most important questions of extremal graph theory is to find the maximal size of a graph on n vertices such that no s vertices have t common neighbours. For s=2, the main term was established by Füredi in 1996. Observing his apparently isolated, algebraic construction from a geometrical point of view, we present a generalization of his method and some applications on related questions.
|
|
2nd May 2008
|
Mareike Massow (TU Berlin)
Diametral Pairs of Linear Extensions
Abstract
We consider the problem LINEAR EXTENSION DIAMETER: Given a finite poset P and a parameter k, are there two linear extensions of P which have distance at least k? The distance of two linear extensions L, L' is the number of pairs of elements of P that appear in different orders in L and L'. We show that LINEAR EXTENSION DIAMETER is NP- complete.
Two linear extensions of P maximising the distance form a diametral pair. In 1999, Felsner and Reuter conjectured that in every diametral pair at least one of the two linear extensions reverses a critical pair of P. We give a counterexample disproving this conjecture. On the other hand, we show that the conjecture holds for almost all posets.
This is joint work with Graham Brightwell.
|
|
14th March 2008
|
Polly Lon (LSE)
A Leaveble Singular Stochastic Control Model with Application to the Goodwill Problem
Abstract
We consider a stochastic system whose uncontrolled state dynamics are modelled by a general one-dimensional Ito diffusion. In this control problem, we aims at maximising a performance criterion that rewards high values of the utility derived from the system's controlled state. e.g. the image at a product in a market. But penalise any expenditure of control effect. e.g. raise the product's image through advertising.
|
|
7th March 2008
|
Mareike Massow (TU Berlin)
On Linear Extension Graphs and a Generalization
Abstract
Given a finite poset P, we consider its linear extension graph, which has a vertex for each linear extension (LE) of P, with two vertices being adjacent exactly if the corresponding LEs differ only by the reversal of an adjacent pair of elements.
We consider the reconstruction problem: Given an LE-graph, we want to reconstruct the posets inducing this graph. I will also present a conjecture and partial results on diametral LEs, that is, LEs corresponding to a diametral pair of vertices in the LE-graph. Finally, I want to talk about a graph on the acyclic orientations of a mixed graph, a concept generalizing LE-graphs.
This is joint work with Stefan Felsner.
|
|
29th February 2008
|
Wan Huang (LSE)
Computing Extensive Form Correlated Equilibrium
Abstract
In this paper we develop a polynomial-time algorithm for finding the extensive form correlated equilibrium (EFCE) for multiplayer extensive games with perfect recall. The EFCE concept is defined by von Stengel and Forges (2007). Our algorithm extends the constructive existence proof and polynomial-time algorithms for finding correlated equilibria in the class of succinctly representable games by Papadimitriou and Roughgarden (2007). We describe the set of EFCE with polynomial number of consistency and incentive constraints for multiplayer perfect-recall extensive games without chance moves. The algorithm employs linear programming duality, the ellipsoid algorithm, and Markov chain steady state computations. We explain how to apply this algorithm to multiplayer perfect-recall extensive games with chance moves. We also describe a possible interpretation of the variables in the dual system.
|
|
22nd February 2008
|
Lubos Thoma (University of Rhode Island)
On acyclic orientations of graphs
Abstract
I will discuss acyclic orientations of graphs. The talk will focus on some properties of random graphs which imply, in particular, improvements of results of Bollobás, Brightwell, and Nesetril and of Fisher, Fraughnaugh, Langley, and West related to acylic orientations. Joint work with V. Rödl
|
|
15th February 2008
|
David Ferguson (LSE)
Ramsey numbers of cycles
|
|
8th February 2008
|
Peter Allen (LSE)
Sparse graph embeddings
|
|
1st February 2008
|
Graham Brightwell (LSE)
Polyhedra, Perfect Graphs, and Partial Orders
Abstract
We discuss some aspects of the relationship between these three topics. A theorem of Stanley states that two polytopes associated with a partial order have the same volume: I aim to give a fairly simple proof.
|
|
25th January 2008
|
Luis Cereceda (LSE)
Perfect matchings in hypercubes extend to Hamilton cycles
Abstract
The d-dimensional hypercube Qd is the graph with the set of all binary vectors of length d as its vertex set, and an edge between any two vertices that differ in precisely one coordinate. A matching M in a graph G is a subset of the edge set of G with the property that every vertex of G is incident with at most one edge of M. The matching is said to be perfect if every vertex of G is incident with some edge of M. A Hamilton cycle in a graph is a cycle containing all vertices of the graph.
In 1996, Kreweras conjectured that for d ≥ 2, any perfect matching of Qd extends to a Hamilton cycle. In this talk we will examine a recent result of Fink which proves this conjecture.
|
|
11th January 2008
|
Marianne Fairthorne (LSE)
Introduction to the supermarket model
|