Below you'll find the program for the PhD Seminar on Combinatorics, Games and Optimisation (formally known as the Lunchtime Seminar: 2006-2016). The Seminar normally takes place on Fridays from 12.00 pm - 1.00 pm in room 32L.B.09 (32 Lincoln's Inn Fields, LSE).
Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator, by sending an e-mail to: seminar@maths.lse.ac.uk
Upcoming Speakers:
Friday 18 November - Carlos Hoppen (UFRGS, Brazil)
Properly coloured spanning trees in an edge coloured random graph
Given a number of colours $k \geq 1$, we consider the probability space $\mathcal{G}_{n,p}^k$ of edge-coloured random graphs, whose elements are produced by first generating a graph $G$ in the Erd\H{o}s-R\'{e}nyi probability space $\mathcal{G}_{n,p}$ and then colouring each edge of $G$ independently and uniformly with a colour from the set $[k]=\{1,\ldots,k\}$. We determine the threshold function $p=p_k(n)$ for the property that such an edge-coloured random graph contains a properly coloured spanning tree, for all fixed $k \geq 3$. It turns out to coincide with the connectivity threshold, which is $\log(n)/n$. This contrasts with the case $k=2$, where the threshold is known to be $2\log(n)/n$ in light of recent work by Espig, Frieze and Krivelevich [Elegantly colored paths and cycles in edge colored random graphs, arXiv:1403.1453]. Among other ingredients, this involves a new result about maximum matchings in $\mathcal{G}_{n,p}$.
This is joint work with Pu Gao (Monash University, Australia) and Juliana Sanches (UFRGS)
Friday 25 November - Natasha Morrison (Oxford)
Maximising the number of induced cycles in a graph
How many induced cycles can a graph on n vertices contain? For sufficiently large n, we determine the maximum number of induced cycles and the maximum number of even or odd induced cycles. We also characterize the graphs achieving this bound in each case. This answers a question of Tuza, and a conjecture of Chvatal and Tuza from 1988.
This is joint work with Alex Scott.
Friday 2 December - cancelled for internal PhD seminar
Friday 9 December - TBC
Previous seminars in this series: 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006