Seminar and PhD Seminar on Combinatorics, Games and Optimisation

Below you'll find the programme for the Seminar and PhD Seminar on Combinatorics, Games and Optimisation.

This seminar series covers many of the research areas in the Department: discrete mathematics, algorithms, game theory and operational research.

Unless stated below, this Seminar normally takes place:

on Thursdays from 14:00 - 15:00
the PhD seminar takes place on Fridays from 12.00 - 13:00

Questions, suggestions, etc., about the seminar can be forwarded to Emily Jackson, Research Manager, on E.Jackson2@lse.ac.uk

Upcoming speakers

Thursday 28 September - Christian Coester (University of Oxford)

The Randomized k-Server Conjecture is False!

The randomized k-server conjecture, which had been open for over three decades, states that there exists an O(log k)-competitive randomized algorithm for the k-server problem. In this talk, I will present our recent joint work with Sébastien Bubeck and Yuval Rabani, where we refute this conjecture by giving a lower bound of Omega((log k)^2). Our work also settles the competitive ratio of metrical task systems to be Theta((log n)^2) on the hardest metric spaces and Theta(log n) on the easiest metric spaces of n points. In particular, this yields the first improvement over the previous “coupon collector” lower bound since the introduction of the model in 1987.

Friday 29 September - David Hannon (Queen Mary University of London)

Optimal Impartial Selection

We consider directed graphs without loops, and rules that select a subset of the vertices in any graph. A selection rule is impartial if the selection of a vertex is independent of its outgoing edges and we also aim to make our selection rule competitive, that is, select vertices with high indegree. This models peer selection where vertices are candidates and directed edges represent votes. We wish to select highly voted candidates such that a candidate cannot influence their own selection. We will introduce mechanisms that achieve this goal and show some impossibility results.

Friday 6 October - Siyue Liu (Carnegie Mellon University/ LSE)

Approximately Packing Dijoins via Nowhere-Zero Flows

(Abstract in LaTex) In a digraph, a dicut is a cut where all the arcs are in one direction. A dijoin is a subset of arcs that intersect each dicut. Woodall conjectured in 1976 that in every digraph, the size of a minimum dicut equals to the maximum number of disjoint dijoins. Even the following weaker statement is still open. Let $f$ be the largest function such that every digraph with minimum dicut size $\tau$ contains $f(\tau)$ disjoint dijoins. It is open if when $\tau$ goes to infinity $f(\tau)$ also goes to infinity. It is not even known whether such $f(\tau)$ can be at least $3$ when $\tau$ goes to infinity.

By building connections with nowhere-zero $k$-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\frac{\tau}{k}$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero $k$-flow. The existence of nowhere-zero $6$-flows in $2$-edge-connected graphs proved by Seymour directly leads to the existence of $\frac{\tau}{6}$ disjoint dijoins in any digraph with minimum dicut size $\tau$ which can also be found in polynomial time. The existence of nowhere-zero circular $(2+\frac{1}{p})$-flows in $6p$-edge-connected graphs proved by Lov\'asz et al. directly leads to the existence of $\frac{\tau p}{2p+1}$ disjoint dijoins in any digraph with minimum dicut size $\tau$ whose underlying undirected graph is $6p$-edge-connected. This is joint work with G\'erard Cornu\'ejols and R. Ravi.

Friday 13 October - Ilay Hoshen (Tel Aviv University)

Simonovits's Theorem in Random Graphs

(Abstract in LaTex) Let $H$ be a graph with chromatic number $\chi(H) = r+1$. Simonovits's theorem states that the unique largest $H$-free subgraph of $K_n$ is its largest $r$-partite subgraph if and only if $H$ is edge-critical. We show that the same holds with $K_n$ replaced by $G_{n,p}$ whenever $H$ is also strictly 2-balanced and
\begin{align*}
p \geq C n^{-1/m_2(H)} \log(n)^{1/(e(H)-1)},
\end{align*}
for some constant $C > 0$. This is best possible up to the choice of the constant $C$. This (partially) resolves a conjecture of DeMarco and Kahn, who proved the result in the case where $H$ is a complete graph. Moreover, we prove the result with explicit constant $C = C(H)$ that we believe to be optimal. Joint work with Wojciech Samotij.

Previous seminars in the series

Seminar and PhD Seminar on Combinatorics, Games and Optimisation:

2022/23, 2021/22, 2020/21, 2019/20

Seminar on Combinatorics, Games and Optimisation

2018/19, 2017/18, 2016/17, 2015/16

The Seminar on Combinatorics, Games and Optimisation started in 2016. It is a combination of two previous seminar series:

Seminar on Discrete Mathematics and Game Theory:

2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003