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 and the PhD seminar takes place on Fridays from 12.00 - 13:00. (Occasionally seminars are held on Wednesdays from 15.30 - 16.30 or at other times - these will be noted below).

N.B. room information is not included below for campus security reasons. If you would like to attend a seminar please contact Emily Jackson, Research Manager, on E.Jackson2@lse.ac.uk, in good time so this can be accommodated.

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

Upcoming Speakers

Thursday 28 March - Olivier Gossner (LSE)

SCAMP

We study (interim correlated) rationalizability in games with incomplete information. For each given game with incomplete information, we show that all hierarchies of iterative deletion of dominated strategies can be captured through an automaton, the strategic automaton. We then prove that a finitely parameterized class of information structures, SCAMP, is sufficient to generate every outcome distribution induced by general common prior information structures. In this parameterized family, a profile of signals is identified to a path over the automaton, and the probability distribution of signal profiles defines a Markov chain.

Thursday 16 May - Anderson Ang (University of Southampton)

Some topics about NNNNNNNN… optimization

This is a two-part talk on some topics in continuous optimization for machine learning, based on my recent joint works with many other people. Part 1 is on Nonnegative Matrix Factorization (NMF). We first give a short review of NMF based on conic and convex geometry, then we present our current work on sum-of-norms NMF that can empirically find the nonnegative rank of the data matrix. Being a Non-convex Non-smooth Non-separable Non-proximable problem, we present a solution strategy based on proximal averaging by the Moreau envelope for solving this NMF problem. Experiment results showcase this NMF model is able to solve rank-deficient NMF problems without knowing the nonnegative rank of the matrix. Part 2 is on Proximal Gradient Descent (PGD). We present our work on a multigrid accelerated PGD that is capable to solve Non-smooth strongly-convex optimization problem with convergence guarantee. In short, the whole idea of multigrid PGD is to collapse the Minkowski sum of subdifferentials into a singleton, based on a newly introduced adaptive restriction operator. On a PDE-induced minimization problem that is strongly-convex-but-unknown-modulus and Lipschitz-smooth-but-unknown-global-Lipschitz-constant, we showcase the proposed method is fast.

Keywords: Non-convex, Non-negative, Non-smooth, Non-separable, Non-proximable, Non-Lipschitz, Non-strongly-convex, Non-differentiable

Previous Seminars - Winter Term 2024

Friday 22 March - Sahar Jahani (LSE)

Automated Equilibrium Analysis of 2x2x2 Games

The set of all Nash equilibria of a non-cooperative game with more than two players is defined by equations and inequalities between nonlinear polynomials, which makes it challenging to compute. This paper presents an algorithm to compute this set for the simplest game with
more than two players with arbitrary (possibly non-generic) payoffs, which has not been done before. We define degeneracy in these games and we prove an upper bound on the number of possible equilibria in non-degenerate games. Furthermore, we introduce new elegant formulas for completely mixed equilibria as well as the visual representations of the best-response correspondences and their intersections in 3D, which defines the Nash equilibrium set. These have been implemented in Python and will be part of a public web-based software for automated equilibrium analysis.

Thursday 21 March - Tara Abrishami (University of Hamburg)

Width parameters and the maximum independent set problem

Width parameters are graph invariants that measure the ''complexity'' of a graph. Treewidth, the most well-known graph width parameter, has important algorithmic implications: problems that are NP-hard in general, such as finding a maximum independent set in a graph, can be solved in polynomial time in graphs of bounded treewidth. However, treewidth does not capture the solvability of maximum independent set very well: there are many graph classes with unbounded treewidth which admit efficient algorithms for the maximum independent set problem. Recently, a number of new graph width parameters have been introduced with the intention of better representing the solvability of maximum independent set. In this talk, I will introduce some of these new width parameters, discuss recent results on a new parameter called induced matching treewidth, and describe several interesting open problems. This talk is based on joint work with Marcin Brianski, Jadwiga Czyżewska, Rose McCarty, Martin Milanic, Pawel Rzazewski, and Bartosz Walczak.

Friday 15 March - Madison Van Dyk (University of Waterloo) **16.00-17.30 Joint CGO-Operations Research Reading Group Seminar**

Fast Combinatorial Algorithms for Efficient Sortation

Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes. In practice, such consolidation requires parcel-sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that, in the general model, it is NP-hard to determine whether a feasible sortation plan exists. We discuss several special settings, where (near-)feasibility of a given sortation instance can be determined efficiently. The algorithms we propose are fast, and construct solutions as well as combinatorial witness set type lower-bounds that are reminiscent and extend those used in early work on degree-bounded spanning trees and arborescences. This is joint work with Kim Klause, Jochen Koenemann, and Nicole Megow. To appear in IPCO 2024.

Friday 15 March - Laurentiu Ploscaru (University of Birmingham)

A bipartite version of the Erdos-McKay conjecture

A set of vertices in a graph is said to be 'homogeneous' if it is a clique or an independent set. An old conjecture of Erdős and McKay states that if all homogeneous sets in an n-vertex graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,..., \Omega(n^2)}. We prove a bipartite analogue of this conjecture: if all balanced homogeneous sets in an n by n bipartite graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,...,\Omega(n^2)}. Based on joint work with Eoin Long (Birmingham).

Friday 8 March - Michal Feldman (Tel-Aviv University)

Ambiguous contracts

In this work we explore the deliberate infusion of ambiguity into the design of contracts. We show that when the agent is ambiguity-averse and chooses an action that maximizes their max-min utility, then the principal can strictly gain from using an ambiguous contract. We provide insights into the structure of optimal contracts, and establish that optimal ambiguous contracts are composed of simple contracts. We also provide a geometric characterization of ambiguity-proof classes of contracts. Finally, we show that when the agent considers mixed strategies, then there is no advantage in using an ambiguous contract.

Friday 8 March - Estelle Varloot (University of Liverpool) **11.00-12.00**

Level-strategyproof Belief Aggregation Mechanisms

In the problem of aggregating experts' probabilistic predictions or opinions over an ordered set of outcomes, we introduce the axiom of level-strategyproofness (level-SP) and argue that it is natural in several real-life applications and robust as a notion. It implies truthfulness in a rich domain of single-peaked preferences over the space of cumulative distributions. This contrasts with the existing literature, where we usually assume single-peaked preferences over the space of probability distributions instead. Our main results are (1) explicit characterizations of all level-SP methods with and without the addition of other axioms (certainty preservation, plausibility preservation, proportionality); (2) comparisons and axiomatic characterizations of two new and practical level-SP methods: the proportional-cumulative and the middlemost-cumulative; (3) an application of the proportional-cumulative to construct a new voting method that extends majority judgment and where voters can express their uncertainties/doubts about the merits/qualities of the candidates/alternatives to be ranked.

Thursday 7 March - Nemanja Draganic (University of Oxford)

Hamiltonicity of expanders: optimal bounds and applications

An n-vertex graph G is a C-expander if |N(X)|≥C|X| for every X ⊆ V(G) with |X|<n/2C and there is an edge between every two disjoint sets of at least n/2C vertices. We show that there is
some constant C > 0 for which every C-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in (n,d,λ)-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications. Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.

Wednesday 6 March - Meike Neuwohner (LSE)

Improved Approximation Algorithms for Weighted k-Set Packing

Abstract

Friday 1 March - R Ravi (Carnegie Mellon University) **16.00-17.30 Joint CGO-Operations Research Reading Group Seminar**

Models and Algorithms for Information Freshness in Graphs

I will describe two related formulations of information dissemination under a telephone model in graphs. After drawing out the relations between them, I plan to present an algorithm for a new variant (called Average Broadcast Time) described in this SODA 23 paper “Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models” by Chen, An, Niaparast, Ravi, and Rudenko. The talk will describe joint work with several graduate students over the years.

Friday 1 March - Miriam Fischer (Imperial College London)

Fair interventions in weighted congestion games

In this talk I present joint work with Martin Gairing and Dario Paccagnan. We study the power and limitations of fair interventions in weighted congestion games. Specifically, we focus on interventions that aim at improving the equilibrium quality (price of anarchy) and are fair. Within this setting, we provide three key contributions:1) We show that no fair intervention can reduce the price of anarchy below a given factor depending solely on the class of latencies considered. This lower bound is unconditional, i.e., it applies regardless of how much computation interventions are allowed to use. 2) We propose a taxation mechanism that is fair and show that the resulting price of anarchy matches this lower bound, while the mechanism can be efficiently computed in polynomial time. 3) We complement these results by showing that no intervention (fair or not) can achieve a better approximation if polynomial computability is required. We do so by proving that the minimum social cost is NP-hard to approximate below a factor identical to the one previously introduced. Our results also show that the randomized algorithm proposed by Makarychev and Sviridenko [JACM’2018] for the class of optimization problems with a “diseconomy of scale” is optimal, and provide a novel way to derandomize its solution via equilibrium computation.

Thursday 29 February - Andreas Feldmann (University of Sheffield)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

We study the parameterized complexity of the well-studied Steiner Forest problem in several graph classes of bounded width. The problem takes an edge-weighted graph and pairs of vertices as input, and the aim is to find a minimum cost subgraph in which each given vertex pair lies in the same connected component. It is known that this problem is APX-hard in general, and NP-hard on graphs of treewidth 3, treedepth 4, and feedback vertex set size 2. However, Bateni et al. [JACM, 2011] gave an approximation scheme with a runtime of n^O((k^2)/ε) on graphs of treewidth k. Our main result is a much faster efficient parameterized approximation scheme (EPAS) with a runtime of 2^O((k^2)/ε log(k/ε)) n^O(1). If k instead is the vertex cover number of the input graph, we show how to compute the optimum solution in 2^O(k log k) n^O(1) time, and we also prove that this runtime dependence on k is asymptotically best possible, under ETH. Furthermore, if k is the size of a feedback edge set, then we obtain a faster 2^O(k) n^O(1) time algorithm, which again cannot be improved under ETH.

Friday 23 February - Fei Wu (King's College London)

Strategic Bidding Wars in On-chain Auctions

The Ethereum block construction market has changed significantly since the emergence of Proposer-Builder Separation. Validators access blocks through a marketplace, where block builders bid for the right to construct the block and earn MEV (Maximal Extractable Value) rewards in a competition, known as the MEV-boost auction. While more than 90% of blocks are currently built through the auction process, trade-offs between builders’ strategic behaviors and auction design remain poorly understood.

We introduce a game-theoretic model for MEV-Boost auctions and use simulations to study different builders’ bidding strategies observed in practice. We study various strategic interactions and auction setups and evaluate how the interplay between critical elements such as access to MEV opportunities and improved network connectivity impact bidding performance and strategy effectiveness.

Thursday 22 February - Olaf Parczyk (FU Berlin)

Maximal diameter of simplicial d-complexes

The diameter of a simplicial d-complex is the diameter of its dual graph. We improve the best known lower bounds for the maximum diameter of a strongly connected simplicial d-complex. For d=2 we even obtain optimal constructions matching the trivial upper bound. This is joint work with Tibor Szabó and Silas Rathke.

Wednesday 21 February - Thomas Sauerwald (University of Cambridge)

Balanced Allocations: The Power of Choice versus Noise

In the balanced allocation problem we wish to allocate m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and average load. For the one-choice protocol, where each ball is allocated to a random bin, the gap diverges for large m. However, for the two-choice protocol, where each ball samples two bins and is placed in the least loaded of the two, it was shown that gap is only O(log log n) for all m. This dramatic improvement is widely known as ``power of two choices’’, and similar effects have been observed in hashing and routing.

In this talk, we will first give some intuition why two-choice maintains such a good balance in theory and practice. Then we will present new results in settings where the load information is incomplete or subject to some noise. Roughly speaking, our results demonstrate that if the noise is not too strong, then the performance of two-choice is not affected too much. However, we will also explore a setting with strong noise where having more choices leads to a worse performance. This is based on joint works with Dimitrios Los and John Sylvester.

Friday 16 February - Luming Zhang (LSE)

Stretching demi-bits and more on non-deterministic secure pseudorandomness

Super-bits and demi-bits are variants of pseudorandom generators which are secure against nondeterministic statistical tests. They were introduced to rule out certain approaches to proving strong complexity lower bounds beyond the limitations set out by the Natural Proofs barrier of Rudich and Razborov. Whether demi-bits are stretchable at all had been an open problem since its introduction. We answer this question affirmatively by showing that: every demi-bit can be stretched into sublinear many demi-bits. I may talk more about our contribution to non-deterministic secure pseudorandomness if time permits. [2304.14700] Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness (arxiv.org)

Thursday 15 February - Ehud Shapiro (Weizmann Institute of Science and LSE)

Grassroots Digital Democracy: Transferring power and wealth from global platforms to the people

The digital realm today is dominated by two architectures: Centralized autocratic global platforms that have adopted surveillance-capitalism as their business model; and up-and-coming blockchain-based global platforms that are decentralized but fundamentally plutocratic. Global platforms exacerbate inequality and undermine the fabric of human society by depleting the social, economic, civic, and political capital of local communities, worldwide. The talk will review the work of my group at Weizmann with colleagues around the world on a third, alternative architecture for the digital realm, termed grassroots digital democracy. The architecture and its engendered grassroots applications (including social networking; cryptocurrencies; social contracts) aim to provide scalable foundations for grassroots digital economies that can emerge without initial capital or external credit, and for sovereign democratic digital communities, both operating solely on the networked smartphones of their members, independently of any global resources and platforms. The publications that form the basis of the talk are collectively available here.

Friday 9 February - Namrata (University of Warwick)

Kneser graphs are Hamiltonian

For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5, 2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n = 2k + 1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph J(n, k, s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly s. Clearly, we have K(n, k) = J(n, k, 0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

Thursday 8 February - Andrea Freschi (University of Birmingham)

Hamilton cycles with large oriented discrepancy

Given graphs G and H, what is the largest t such that in any 2-colouring of the edgesof G, there is a copy of H in G with at least t edges in the same colour? This topic was firstraised by Erd˝os in the 1960s and has attracted renewed attention in recent years. Gishboliner,Krivelevich and Michaeli considered an analogous question for Hamilton cycles in oriented graphs.They conjectured that if G is an oriented graph on n vertices and δ(G) ≥ n/2 then G contains aHamilton cycle with at least δ(G) edges pointing in the same direction. In this talk we present aproof of this conjecture, as well as an overview of the recent developments in the area.This is based on joint works with Allan Lo and Joseph Hyde, Joanna Lada and Andrew Treglown.

Wednesday 7 February - Martin Bullinger (University of Oxford)

Online Coalition Formation under Random Arrival or Coalition Dissolution

Coalition formation considers the question of how to partition a set of n agents into disjoint coalitions according to their preferences. We consider a cardinal utility model with additively separable aggregation of preferences and study the online variant of coalition formation, where the agents arrive in sequence. The goal is to achieve competitive social welfare. In a purely deterministic model, the natural greedy algorithm is known to achieve an optimal competitive ratio, which heavily relies on the range of utilities.

We complement this result by considering two related models. First, we study a model where agents arrive in a random order. We find that the competitive ratio of the greedy algorithm is of order 1/n^2, whereas an alternative algorithm, which is based on alternating between waiting and greedy phases, can achieve a competitive ratio of of order 1/n. Second, we relax the irrevocability of decisions by allowing to dissolve coalitions into singleton coalitions. We achieve the asymptotically optimal competitive ratio of of order 1/n by drawing a close connection to a general model of online matching. Hence, in both models, we obtain a competitive ratio that does not only get rid of the utility dependencies in the base model but even essentially matches the best possible approximation ratio by polynomial-time algorithms.

This is joint work with René Romen. The paper is available on arXiv: https://arxiv.org/abs/2306.16965. A preliminary version of this paper has appeared in the Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023).

Friday 2 February 2024 - Alexandra Lassota (Eindhoven University of Technology), 4.00-5.30pm

Small Lecture on Block-Structured Integer Programs

Integer Programs (IPs) are an ubiquitous and potent modeling tool, but in general also NP-hard to solve. Thus, special cases are studied that are solvable in polynomial time. One important case is that of block-structured IPs. The simplest class of such IPs have a constraint matrix consisting of independent sub-matrices that are linked by either few variables (2-stage stochastic IPs) or few constraints (n-fold IPs) This talk gives an overview on the results of these IPs (including our brand-new SODA results) and outlines the most important techniques to achieve them.

Friday 2 February 2024 - Alex Malekshaian (KCL)

Counting antichains in the Boolean lattice

An old question of Dedekind asks for the number of antichains in the Boolean lattice on $n$ elements. After a long series of partial results, this was answered asymptotically by Korshunov in the 1980s. Using methods from probability and statistical physics, we refine his asymptotics, giving a formula to arbitrary exponential precision. We also give asymptotics for the number of antichains of a given, large size. As a corollary, we derive a 'sparse' version of the classical theorem of Sperner which states that the largest antichain is precisely the middle layer: we determine the threshold for the size at which an antichain is almost surely contained in the middle layer.

Joint work with Matthew Jenssen and Jinyoung Park.

Thursday 1 February - Robert Hancock (University of Oxford)

A resolution of the Kohayakawa Kreuter conjecture for almost all pairs of graphs

We study asymmetric Ramsey properties of the random graph G(n,p). For r ≥ 2 and a graph H, Rödl and Rucinski (1993-5) provided the asymptotic threshold for G(n,p) to have the following property: whenever we r-colour the edges of G(n,p) there exists a monochromatic copy of H as a subgraph. In 1997, Kohayakawa and Kreuter conjectured an asymmetric version of this result, where one replaces H with a set of graphs H_1,...,H_r and we seek the threshold for when every r-colouring contains a monochromatic copy of H_i in colour i for some i ∈ {1,...,r}.

The 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij in 2020. We extend upon the many partial results for the 0-statement, by resolving it for almost all cases. We reduce the remaining cases to a deterministic colouring problem. Our methods also extend to the hypergraph setting. Joint work with Candida Bowtell (University of Warwick) and Joseph Hyde (University of Victoria).

Friday 26 January - George Chionas (University of Liverpool)

Who gets the MEV? A Dynamical Sharing Blockchain Mechanism

Maximal Extractable Value (MEV) has emerged as a new frontier in the design of blockchain systems. The marriage between decentralization and finance gives the power to block producers not only to select and add transactions to the blockchain but, crucially, also to order them so as to extract additional value. However, the additional value comes from the economic activity of users. In this work, we propose to make the MEV extraction rate part of the protocol design space. Our aim is to leverage this parameter to maintain a healthy balance between block producers (who need to be compensated) and users (who need to feel encouraged to transact). Inspired by the principles introduced by EIP-1559 for transaction fees, we design a dynamic mechanism which updates the MEV extraction rate with the goal of stabilizing it at a target value. We analyze the evolution of this dynamic mechanism under various market conditions and provide formal guarantees about its long-term performance.

Friday 19 January 2024 - Joachim Spoerhase (University of Sheffield)

Parameterized Approximation Schemes for Clustering with General Norm Objectives

This paper considers the well-studied algorithmic regime of designing a (1+epsilon)-approximation algorithm for a k-clustering problem that runs in time f(k,epsilon)poly(n) (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable previous results of this kind include EPASes in the high-dimensional Euclidean setting for k-center as well as k-median, and k-means. However, existing EPASes handle only basic objectives (such as k-center, k-median, and k-means) and are tailored to the specific objective and metric space. Our main contribution is a clean, simple, and unified algorithm that yields an EPAS for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, l-centrum, ordered k-median, socially fair k-median aka robust k-median, or more generally monotone norm k-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics), and which is (almost) entirely oblivious to the underlying objective and metric space. Key to our approach is a new concept that we call bounded epsilon-scatter dimension -- an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension.

This is joint work with Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, and Roohani Sharma.

Thursday 18 January 2024 - Olivier Gossner, Matoula Kotsialou, Bernhard von Stengel, Adam Ostaszewski, Bob Simon (LSE)

Research Catch-Up Session

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.

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.

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