Below you can find information about past seminars in this series, specifically those held in 2012. The seminars are listed in reverse chronological order, most recent first.
Friday 7 December - Yury Person (FU Berlin)
Inclusion Matrices
Let n>= r >= s >= 0. The inclusion matrix M_s^r is a {0,1}-matrix whose rows are indexed by all r-element subsets of [n]:={1,2,..., n} and and columns are indexed by all s-subsets of [n] and the entry corresponding to an r-set R and an s-set S is 1 if S is a subset of R and 0 otherwise.
Gottlieb's theorem from 1966 states that M_s^r has full rank over Q. Peter Keevash asked how many rows one has to delete from M_s^r to reduce its rank by 1. We answer his question for large n and study some generalizations of this problem.
Joint work with Codrut Grosu and Tibor Szabó.
Friday 30 November – Steffen Issleib (LSE)
Some results in cooperative game theory - Shpaley's value and the egalitarian allocation
I will talk about the main results of Lloyd Shapley regarding cooperative game theory and introduce another solution concept from Dutta and Ray called the egalitarian allocation. I will then link both to evolution in coperative game theory and give some examples. I will link to the work I am undertaking, mainly introducing the subject and producing some results with examples.
Friday 16 November - Ahmad Abu-Khazneh (LSE)
Some computational results on Ryser's conjecture for intersecting hypergraphs
We discuss Ryser's conjecture for intersecting hypergraphs and present some computational results and insights, focusing on the case with 6 partitions.
Friday 9 November - Marta Casetti (LSE)
NP-completeness of planar 3-dimensional matching
We present a result by Dyer and Frieze (1986) about the NP-completeness of a particular restriction of the problem 3-dimensional matching, that is achieved through a series of interesting reductions.
Friday 26 October - David Ferguson (LSE)
The Fractional chromatic number of triangle-free subcubic graphs
When considering the chromatic number of certain graphs, one may notice colourings which are best possible (in that they use as few colours as possible) but which are in some sense wasteful. For instance, $C_7$ cannot be properly coloured with two colours but can be coloured using three colours in such a way that the third colour is used only once. If, however, our aim is instead to assign multiple colours to each vertex such that adjacent vertices receive disjoint lists of colours, then we could double-colour $C_7$ using five (rather than six) colours and triple-colour it using seven (rather than nine) colours in such a way that each colour is used exactly three times.
Thus, asking for the minimum of the ratio of colours required to the number of colours assigned to each vertex gives us a natural generalisation of the chromatic number.
In this talk, I will give an introduction to Fractional colouring before proceeding to discuss joint work with Dan Kráľ and Tomá\vs Kaiser in which we prove that that fractional chromatic number of any subcubic triangle-free graph is at most 32/11.
Friday 12 October - Alexey Pokrovskiy (LSE)
Covering coloured graphs with cycles and paths
A conjecture of Erdős, Gyárfás, and Pyber says that the vertices of every r-edge coloured complete graph can be covered with r vertex-disjoint monochromatic cycles. This conjecture is know to hold only for r = 2. It turns out that for 3 or more colours, the conjecture is, in fact, false. However, there are weaker versions of the original conjecture which may still hold. For example, it may be possible to cover an r coloured complete graph with r disjoint monochromatic paths. Or it may be possible to cover almost all the vertices of an r coloured complete graph with r disjoint monochromatic cycles. We will discuss how to prove these weaker versions when r = 3. Some of the intermediate results we use have applications in Ramsey Theory for determining certain 2-colour Ramsey Numbers.
Friday 11 May - Horst Martini (University of Technology, Chemnitz, Germany)
Some problems and results in Minkowski Geometry - no abstract available.
Friday 9 March - Tom Lidbetter (LSE) and Filippo Casati (LSE)
Each PhD student will give a short talk based on their current area of research - no abstracts available.
Friday 24 February - Somkiat Trakultraipruk (LSE)
Connectedness of Tken Graphs with Labelled Tokens
Let~$G$ be a graph and $k_1,k_2,...,k_p$ positive integers, for some integer~$p\geq2$. We have a number of classes of tokens, say $k_1$ tokens are labelled~1, $k_2$ tokens are labelled~2, etc. Tokens with the same number are indistinguishable. A token configuration is an arrangement of all tokens on vertices of~$G$ such that no two tokens are placed on the same vertex. We define the token graph of~$G$ with the numbers $(k_1,k_2,\ldots,k_p)$ to be the graph whose vertices correspond to token configurations, and two token configurations are adjacent if one can be reached from the other by moving one token along an edge of~$G$. We denote the token graph as $T(G;(k_1,k_2,\ldots,k_p))$, and we always assume that $k_1\geq k_2\geq \cdots \geq k_p$. In this paper, we answer the question: When is $T(G;(k_1,k_2,\ldots,k_p))$ connected?
Friday 10 February - Various
Mid-term Day Dreams
Three speakers reflected on an interesting problem of their choice - no abstract available.
Friday 3 February - Tugkan Batu (LSE)
Property Testing of Extractors
In this talk, I will describe some work in progress on a problem of property testing of extractors, which are bipartite graphs with a random-like property. Let G be a bipartite graph, with bipartition (U,V) such that |U|=N, |V|=M, and every vertex in U has fixed degree D. Then, G is called a (K,\epsilon)-extractor if, for every subset A of U such that |A|>K, choosing a random vertex u in A and a random neighbour of u gives a distribution that is within \epsilon of the uniform distribution on V in the variation distance. The property testing of extractors is defined as the problem of distinguishing extractors from bipartite graphs that require at least \delta ND edge modifications to be turned into extractors. We study the sample complexity of this problem and characterise it to be \Theta(NM/K).
Friday 27 January - Pablo Soberón Bravo (UCL)
Some generalisations of Radon's theorem
We will discuss some generalisations of the well known Radon's Theorem and how they can be mixed together. More precisely, we will see how colourful theorems, Tverberg's theorem and recent results on tolerance conditions behave together.