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:
Questions, suggestions, etc., about the seminar can be forwarded to Emily Jackson, Research Manager, on E.Jackson2@lse.ac.uk
Upcoming Speakers
Thursday 7 December - Maria Chudnovsky (Princeton University)
Induced Subgraphs and Tree Decompositions
Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last several of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.
Wednesday 13 December - Ryan Martin (Iowa State University)
Counting Cycles in Planar Graphs
Basic Tur\'an theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Tur\'an question asks how many copies of a fixed subgraph $H$ the graph can have, given certain restrictions. There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of ${\bf N}_{\mathcal P}(n,H)$, which denotes the maximum number of copies of $H$ in an $n$-vertex planar graph. In particular, we will focus on the case where $H$ is a cycle. It was determined that ${\bf N}_{\mathcal P}(n,C_{2m})=(n/m)^m+o(n^m)$ for small values of $m$ by Cox and Martin and resolved for all $m$ by Lv, Gy\H{o}ri, He, Salia, Tompkins, and Zhu. The case of $H=C_{2m+1}$ is more difficult and it is conjectured that ${\bf N}_{\mathcal P}(n,C_{2m+1})=2m(n/m)^m+o(n^m)$. We will discuss recent progress on this problem, including verification of the conjecture in the case where $m=3$ and $m=4$ and a lemma which reduces the solution of this problem for any $m$ to a so-called ``maximum likelihood'' problem. The maximum likelihood problem is, in and of itself, an interesting question in random graph theory.
This is joint work with Emily Heath and Chris (Cox) Wells.
Previous Seminars in the Series
Friday 1 December 16.00 – 17.30 - Kristóf Bérczi (ELTE, Budapest)
Reconfiguration of basis pairs in regular matroids
Determining the exchange distance of two matroid basis sequences appears in several areas of computer science and mathematics. In 1980, White proposed a conjecture for the characterization of two basis sequences being reachable from each other by symmetric exchanges, which received a significant interest also in algebra due to its connection to toric ideals and Gröbner bases. In this talk, we present a proof of White's conjecture for basis sequences of length two in regular matroids, a problem that was formulated as a separate question by Farber, Richter, and Shan and Andres, Hochstättler, and Merkel. We study the problem from an optimization point of view and give a polynomial algorithm for constructing a sequence of symmetric exchanges that transforms a basis pair into another. As a byproduct, we verify a conjecture of Gabow from 1976 on the serial symmetric exchange property of matroids for the regular case. Joint work with Bence Mátravölgyi and Tamás Schwarcz.
Friday 1 December - Jun Yan (University of Warwick)
An Interesting Forbidden Matrix Problem
An r-matrix is a matrix whose entries belong to the set {0,1,…,r-1}. The forbidden matrix problem studies the quantity forb(m,r,F), which is defined to be the maximum number of distinct columns in an m-rowed r-matrix that does not contain a submatrix that is a row and/or column permutation of F. The r=2 case has been extensively studied, while relatively little is known about the r>=3 cases. In this joint work with Wallace Peaslee and Attila Sali, we study forb(m,r,M), where M is the smallest (0,1)-matrix for which the exact value of this forbidden number is not known. We significantly improve known bounds on forb(m,r,M) and, in the process, link this problem to another curious optimisation problem involving edge multiplicities of certain multigraphs.
Thursday 30 November - Marcelo Campos (University of Oxford)
Independence number of sparser Cayley graphs
Given a $p$-random $A \subseteq \mathbb{Z}_n$, the random Cayley graph $\Gamma_p$ is defined to have vertex set $\mathbb{Z}_n$ and an edge between two distinct vertices $x, y \in \mathbb{Z}_n$ if $x + y \in A$. For $p=1/2$ Green and Morris showed that the independence number of $\Gamma_{1/2}$ is asymptotically equal to $\alpha(G(n, 1/2))$. In this talk I'll show that the independence number of $\Gamma_p$ matches that of $G(n,p)$ for $p \geq (\log n)^{-1/80}$.
This is joint work with Lucas Aragão, Gabriel Dahia and João Pedro Marciano.
Friday 24 November – Eoin Hurley (University of Amsterdam)
Induced Trees in Sparse Expanders
Inspired by the network routing literature we utilise what we call the "Pre-Emptive Greedy Algorithm" to embed bounded degree induced trees in sparse expanders. This simple proof generalises (with some extra conditions) a powerful theorem of Friedman and Pippenger to the induced setting. It immediately implies that the sparse random graph contains all bounded degree trees (up to some linear order) as induced subgraphs. It further implies that the multicolour induced and size induced ramsey numbers of bounded trees are linear. No such linear bounds were previously known and we hope the theorem will find many more applications.
Thursday 23 November - Alastair Litterick (University of Essex)
Condorcet Domains: Their Enumeration and Structure
In 1785, on the cusp of the French Revolution, the philosopher, mathematician and politician Le Marquis de Condorcet published a seminal essay in which he considered various issues related to ranked-choice voting systems. One such issue is the Condorcet paradox: if election candidates are compared pair-wise, an overall winner may not exist. For instance if three votes are A > B > C, B > C > A and C > A > B, then each candidate loses to another by a two-thirds majority. One way to resolve this paradox is to restrict which votes are allowed: A collection of allowable votes is called a Condorcet domain if each election using these votes will have an overall winner. The question then is: What are the Condorcet domains, among all possible collections of votes? This basic question remains open despite significant advances by many researchers. Even the largest size of a Condorcet Domain is unknown for more than eight candidates. This talk will present recent progress made on questions related to Condorcet domains, through a combination of computational algebra and significant computing power.
This is joint work with Dolica Akello-Egwell, Charles Leedham-Green, Klas Markström and Søren Riis.
Friday 17 November - Yani Pehova (LSE)
The Erdős-Rothschild problem for dichromatic triangles
In 1974 Erdős and Rothschild asked the following question: given integers k, s and a large n, what is the maximum number of s-edge-colourings of an n-vertex graph free of a monochromatic k-vertex clique? A follow up question is to determine which graph(s) attain this maximum. Recent work of Pikhurko, Staden and Yilma shows that in most cases this problem reduces to considering complete multipartite graphs and only counting a natural family of Kk-free "template" colourings of their edge set. Despite this reduction, the Erdős-Rothschild problem has only been solved for some small s and k. Various generalisations of this problem have been considered in the literature, where instead of forbidding monochromatic cliques, we forbid other, non-monochromatic, patterns on a clique. We consider the problem of maximising the number of s-edge-colourings without triangles which see exactly two colours, and show that for every s, the extremal graph is an r-partite Turán graphs where r is easy to compute for any given s.
This is joint work with Pranshu Gupta, Emil Powierski and Katherine Staden.
Thursday 16 November - Thomas Karam (University of Oxford)
On the expressive power of mod-p linear forms on the Boolean cube
Let A_1,..,A_s be a sequence of dense subsets of the Boolean cube {0,1}^n and let p be a prime. We show that if s is assumed to be superpolynomial in n then we can find distinct i,j such that the two distributions of every mod-p linear form on A_i and A_j are almost positively correlated. We also prove that if s is merely assumed to be sufficiently large independently of n then we may require the two distributions to have overlap bounded below by a positive quantity depending on p only.
Friday 10 November - Edward Plumb (LSE)
Learning in Games
We study the dynamics caused by agents who learn while playing games. We show that, even under uncertainty, dynamics locally converge to strict Nash equilibria in repeated games. However, we show that the uniqueness of a strict Nash equilibrium is not sufficient to ensure global convergence in general, but then introduce a class of games where global convergence may be obtained.
Thursday 9 November - Irene Muzi (Birkbeck, University of London)
Improved bound for the directed grid theorem yielding an elementary Erd\H os-P\'osa bound
In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem --- the generalization of the well-known excluded grid theorem to directed graphs --- confirming a conjecture by Reed, Johnson, Robertson, Seymour, and Thomas from the mid-nineties. The theorem states the existence of a function $f$ such that every digraph of directed tree-width $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor, but their function grows non-elementarily with the size of the grid minor. More precisely, it contains a tower whose height depends on the size of the grid.
In this paper we present an alternative proof of the directed grid theorem which is conceptually much simpler, more modular in its composition and also proves an elementary bound for the function $f$. Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy who proved a polynomial bound for the excluded grid theorem for undirected graphs. We translate a key concept of their proof to directed graphs by introducing \emph{cycles-of-well-linked sets (CWS)} and show that any digraph of high directed tree-width contains a large CWS. As it is easily seen that a CWS contains a cylindrical grid, this allows us to improve the proof by Kawarabayashi and Kreutzer from non-elementary to an elementary function.
Since its publication in STOC 2015, the Directed Grid Theorem has found numerous applications of which our result is a direct improvement. As an example, an elementary bound for the Directed Grid Theorem implies a new bound for the Erd\H os-P\'osa property of directed cycles, the first ever elementary bound.
Friday 3 November - Tim Planken (University of Birmingham)
Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets
A range family R is a family of subsets of \mathbb{R}^d, like all halfplanes, or all unit disks. Given a range family R, we consider the m-uniform range capturing hypergraphs H(V,R,m) whose vertex-sets V are finite sets of points in \mathbb{R}^d with any m vertices forming a hyperedge e whenever e = V \cap r for some r in R. Given additionally an integer k, we seek to find the minimum m = m_R(k) such that every H(V,R,m) admits a polychromatic k-coloring of its vertices, that is, where every hyperedge contains at least one point of each color. Clearly, m_R(k) \geq k and the gold standard is an upper bound m_R(k) = O(k) that is linear in k.
A t-shallow hitting set in H(V,R,m) is a subset S of V such that every hyperedge is hit at least once but at most t times by S. In this talk, we show for several range families R the existence of t-shallow hitting sets in every H(V,R,m) with t being a constant only depending on R, which in particular proves that m_R(k) = O(k) in such cases, improving previous polynomial bounds in k. Joint work with Torsten Ueckerdt.
Thursday 2 November - Bart De Keijzer (King's College London)
Multi-Unit Bilateral Trade
We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular.
Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1 − e) approximation mechanism, matching the best known bounds for the single-item setting. Joint work with Matthias Gerstgrasser, Paul Goldberg, Philip Lazos, and Alexander Skopalik, 2020.
Friday 27 October - Domenico Mergoni (LSE)
Many questions and some answers about product-free sets of integers
The topic of sum-free sets of integers has been extensively studied in the past few years. However, no attention has been spent in the study of product-free sets of integers. We aim to start closing this gap with an initial analysis of properties of product-free sets of integers in the deterministic, probabilistic, and perturbed settings.
Thursday 26 October - Marius Tiba (University of Oxford)
Sharp stability for the Brunn-Minkowski inequality for arbitrary sets
The Brunn-Minkowski inequality states that for (open) sets A and B in R^d, we have |A+B|^{1/d} \geq |A|^{1/d}+|B|^{1/d}. Equality holds if and only if A and B are convex and homothetic sets in R^d. In this talk, we present a sharp stability result for the Brunn-Minkowski inequality, concluding a long line of research on this problem. We show that if we are close to equality in the Brunn-Minkowski inequality, then A and B are close to being homothetic and convex, establishing the exact dependency between the three notions of closeness. This is based on joint work with Alessio Figalli and Peter van Hintum.
Wednesday 25 October - Marc Schröder (Maastricht University)
Hotelling's model with network effects
We study a variant of Hotelling's location game (1929). In this game firms have to decide on a location on an interval. Hotelling's famous result says that firms have an incentive to minimize differentiation. We assume a different behavior of the consumers: consumers care about their travel distance as well as the number of other consumers visiting each firm. We see how this change in assumption affects the locations of the firms and observe that the results are very different for congestion than for popularity effects.
Friday 13 October 2023 - 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.
Thursday 12 October 2023 - Dima Shaiderman (Technion Israel Institute of Technology) [Online via Zoom]
Markovian Persuasion
In the classical Bayesian persuasion model, an informed player and an uninformed one engage in a static interaction. This work extends this classical model to a dynamic setting where the state of nature evolves according to a Markovian law, allowing for a more realistic representation of real-world situations where the state of nature evolves over time. In this repeated persuasion model, an optimal disclosure strategy of the sender must balance between obtaining a high-stage payoff and disclosing information that may have negative implications on future payoffs. We discuss optimal strategies under different discount factors and characterize when the asymptotic value achieves the maximal possible value. Joint work with Ehud Lehrer.
Friday 6 October 2023 - 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.
Thursday 5 October 2023 - Coralia Cartis (University of Oxford)
Dimensionality reduction techniques for nonconvex optimization
Modern applications such as machine learning involve the solution of huge scale nonconvex optimization problems, sometimes with special structure. Motivated by these challenges, we investigate more generally, dimensionality reduction techniques in the variable/parameter domain for local and global optimization that rely crucially on random projections.
We describe and use sketching results that allow efficient projections to low dimensions while preserving useful properties, as well as other tools from random matrix theory and conic integral geometry. We focus on functions with low effective dimensionality, a common occurrence in applications involving overparameterized models and that can serve as an insightful proxy for the training landscape in neural networks. We obtain algorithms that scale well with problem dimension, allow inaccurate information and biased noise, have adaptive parameters and benefit from high-probability complexity guarantees and almost sure convergence.
Friday 29 September 2023 - 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.
Thursday 28 September 2023 - 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.
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
Seminar on Operations Research:
2016, 2015, 2014, 2013, 2012, 2011, 2010
PhD Seminar on Combinatorics, Games and Optimisation:
2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012