Below you can find information about past seminars in this series, specifically those held in 2011. The seminars are listed in reverse chronological order, most recent first.
Friday 25 November- Mitch Keller (LSE)
Linear Extension Diameter and Reversal Ratio of Posets
Given a partially ordered set P, a linear extension is a total order L on the same set that respects the partial order. In other words, if x < y in P, then x < y in L. The linear extension graph G of a poset P has as its vertices all linear extensions of P, with L_1 and L_2 adjacent in G if and only if they differ only in the transposition of consecutive elements. The linear extension diameter of P, introduced by Felsner and Reuter, is the diameter of its linear extension graph, i.e., the greatest distance (via shortest paths) between two vertices of G. We introduce the reversal ratio of P as the ratio of the linear extension diameter to the number of (unordered) incomparable pairs. We use probabilistic techniques to provide a family of posets for which the reversal ratio O(1/log k). We also examine the questions of bounding the reversal ratio in terms of order dimension and width.
Friday 18 November- Matthew White (Oxford)
Monochromatic cycles in edge-coloured graphs
For any given positive integers d and n, a tight lower bound on the circumference of a graph with order n and minimal degree d was given by Bollobas and Haggkvist. For an edge-coloured graph, the monochromatic circumference is defined to be the length of the longest monochromatic cycle. It is currently not possible to find an exact analogue of the above statement. However, I will find, for all 0<c<1, a lower bound on the monochromatic circumference of a 2-edge-coloured graph with order n and minimal degree at least cn, and show that this bound is asymptotically best possible. I will also touch on more general work about monochromatic cycles in edge-coloured graphs, which is joint with Fabricio Benevides, Tomasz Luczak, Alex Scott and Jozef Skokan.
Friday 11 November- Tom Lidbetter (LSE)
Expanding Search for an Immobile Hider on a Network
A Hider is located at a point H on a rooted network Q. An expanding search is defined as a nested family of connected sets S(t) which specify the area of Q that has been covered by time t, where S(0) is the root of Q. The search time is the minimum value of t for which H is contained in S(t). For a known Hider distribution on a tree, we derive the expanding search that minimises the expected search time. When the Hider distribution is unknown, we consider the zero-sum search game where the Hider picks H, the Searcher S, and the payoff is the search time. We solve the game for trees and for 2-arc-connected networks.
Friday 28 October-Alexey Pokrovskiy (LSE)
Partitioning 3-coloured complete graphs into 3 monochromatic paths
We say that a graph G is vertex-partitioned into subgraphs H, K, ..., J if the subgraphs are vertex-disjoint and cover all the vertices in G. Suppose that the edges of a G are coloured with r colours. How many monochromatic paths are needed to partition the vertices of G? When G is a complete graph, Gyarfas conjectured that r monochromatic paths suffice. In this talk we sketch a proof or the 3-colour case of this conjecture - that any 3 edge coloured complete graph can be vertex-partitioned into 3 monochromatic paths. As an intermediate result, we show that any 2 edge coloured complete graph can be vertex-partitioned into a monochromatic path and a monochromatic balanced complete bipartite graph.
Friday 14 OctoberJoel Ratsaby (Ariel University)
Maximal Width Learning of Binary Functions
The maximal-margin approach of machine learning is the basis of several successful algorithms such as Support Vector Machines which have recently been very popular due to their good generalization ability. In this talk I will describe how this approach may be used for learning directly binary functions from a finite labelled sample $\zeta$ of cardinality $m$. We introduce a new concept of sample {\em width} which is similar to the notion of margin for real-valued functions.Our result shows that learning binary functions by maximizing the width yields improved upper bound on the generalization error. Compared to existing bounds on maximal-margin learners (for instance, via thresholding of real-valued functions) our bound is significantly better and excludes the usual $O(\ln(m))$ factor.
This is joint work with Prof. Martin Anthony from the department of Mathematics, London School of Economics and Political Science.
Friday 7 October- Michael Stiebitz (TU Ilmenau, Germany)
Edge Colouring of Multigraphs: Tashkinov Trees and Goldberg's Conjecture
Abstract
Friday 24 June - Adam Ostaszewski (LSE)
Suppression of bad news in markets: Equilibrium analysis of correlated optimal data censors
Poor forecasts may rationally remain unreported (become 'censored data') by pooling with absence of news ('feigning ignorance'). In equilibrium, what are the effects of like optimal behaviour of correlated sources? In the case of equity valuation we answer by combining classical linear regression with the Black-Scholes put-option formula.
Joint work with Miles Gietzmann (Cass).
Friday 25 March - Philip R. Neary (University of California at San Diego)
Competing Conventions
This paper studies a new coordination game, the Language Game, of a large but finite population. The population is partitioned into two groups of identical agents. Each player shares a common two-action strategy set and interacts pairwise with everyone else. Both symmetric profiles are pareto-efficient strict equilibria, but the groups rank them differently. The profile where successful coordination occurs only within-group, with each group adopting their most preferred action, is also an equilibrium provided the smaller group's preferences are sufficiently strong. In all dynamically stable long run outcomes, players in the same group adopt the same action. Three properties, that do not matter for equilibrium selection in the homogeneous agent models of Kandori, Mailath, and Rob (1993) and Young (1993), do matter in the Language Game. These are: group size, preference over alternative equilibria, and rates of group adaptiveness ("group dynamism"). A relative increase in group dynamism is always weakly beneficial.
Friday 11 March - Derek Wan (LSE)
Rapid Mixing for the Supermarket Model with Memory
In this talk we outline the proof of the rapid mixing result of the supermarket model with memory.
Friday 18 February - Bjarne Toft (University of Southern Denmark)
On Hex and Reverse Hex
Reverse Hex, also known as Rex or Misère Hex, is the variant of Hex in which the player who connects his/her two sides loses. After a brief survey of Hex and Reverse Hex, we update some proofs and results for general nxn-boards. We give a new simple proof of Lagarias and Sleators' theorem on Reverse Hex (each player can prolong the game until the board is full, so the first/second player can always win if n is even/odd), and of Evans' theorem (for even n, opening in the acute corner is a winning move). Also a new simple proof of the fact that Hex (and Reverse Hex) cannot end in a draw is presented.
Friday 11 February - Mitch Keller (LSE)
Online linear discrepancy
The linear discrepancy of a partially ordered set P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h_L(x)-h_L(y)|<= k, where h_L(x) is the height of x in L. We can think of linear discrepancy as a way of measuring how unfair a total ordering of a poset must be in terms of placing incomparable elements far apart. An online algorithm is one that is given information about the problem one piece at a time and must make an irrevocable decision about the new information at each step. In this talk, we consider the problem of determining the linear discrepancy of a poset online. We give an online algorithm for linear discrepancy that produces a linear extension with linear discrepancy at most 3d-1 for any poset with linear discrepancy d. We also show that this is best possible, even for the class of interval orders. For the class of semiorders, we show that this online algorithm performs even better and is best possible.
Friday 28 January - Julian Merschen (LSE)
Games and Perfect Matchings
Nash Equilibria (NE) of bimatrix games can be computed with the classic Lemke-Howson (LH) algorithm by alternatively pivoting in the best reply polytope of the players. For a certain class of games, namely those derived from dual cyclic polytopes, the LH-algorithm displays exponential behaviour. For this class the best reply polytopes can be described by a string of labels and an NE corresponds to a completely labelled Gale String. The string of labels represents an Euler Tour and we show that in the corresponding Euler Graph a perfect matching corresponds to an NE of the bimatrix game. This implies that an NE for this class of games can be found in polynomial time.
Similar to the sign of an NE, we define the sign of a perfect matching, i.e. the sign of the permutation of edges in the matching. The LH-algorithm has the property that when started from one perfect matching M, it finds another perfect matching M' of different sign. A polynomial algorithm for finding a matching of a different sign is, however, not yet known, but we conjecture that this problem is in P. We show that the Euler Tour must be considered in the algorithm and give an approach for a polynomial solution.