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 Enfale Farooq, the Research Manager, on E.Farooq@lse.ac.uk

Upcoming speakers

Friday 19 August - Anindya De (University of Pennsylvania)
Hybrid - 14:00 on Zoom, and 32L.G.03

Testing Noisy Linear Equations for Sparsity
Consider the following basic problem in sparse linear regression -- an algorithm gets labeled samples of the form (x, <w.x> + \eps) where w is an unknown n-dimensional vector, x is drawn from a background distribution D and \eps is some independent noise. Given the promise that w is k-sparse, the breakthrough work of Candes, Rhomberg and Tao (2005) shows that w can be recovered with samples and time which scales as O(k log n). This should be contrasted with general linear regression where O(n) samples are information theoretically necessary.
In this talk, we look at this question from the vantage point of property testing and study the decision variant of the following question -- namely, what is the complexity of deciding if the unknown vector w is k-sparse (or at least say 0.01 far from k-sparse in \ell_2 distance). We show that the decision version of the problem can be solved with samples which are independent of n as long as the background distribution D is i.i.d. and the components are not Gaussian. We further show that weakening any of the conditions in this result necessarily makes the complexity scale as log n (thus showing our results are tight).

Joint work with Xue Chen (USTC) and Rocco Servedio (Columbia).

Friday 16 September - Dana Pizarro (Université Toulouse 1 Capitole)
Hybrid - 12:00 on Zoom, and 32L.G.03

Competition and Recall in Selection Problems
In this talk, I will present an extension of the prophet inequality problem to a competitive setting. At every period, a new sample from a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random). As soon as a player gets one sample, he leaves the market, and his payoff is the value of the sample. In a first variant, namely no recall case, the agents can only bid in each period for the current value. In a second variant, the full recall case, the agents can also bid at each period for any of the previous samples that have not been already selected. For each variant, we study the two-player game induced by the optimal stopping problem, focusing on subgame-perfect Nash equilibria. In particular, I will describe the set of subgame-perfect Nash equilibria payoffs, I will compare the two model variants in terms of the payoffs of the players and I will provide tight bounds for the Price of Anarchy and Price of Stability of the former setting when the number of arrivals is two.

Joint work with Fabien Gensbittel and Jérôme Renault (TSE).

Thursday 22 September - Lucas Pahl (University of Bonn)
Hybrid - 14:00 on Zoom, and 32L.G.03

Title and abstract TBC.

Previous seminars in the series:

Friday 17 June - Chhaya Trehan (LSE)

Distributed Expansion Testing of Bounded Degree Graphs
Graph expansion testing is a very important and well studied problem in the area of property testing in the traditional centralised setting. A bounded degree graph %%G = (V,E)%% of degree bound %%d%% is represented by an adjacency list of length at most %%d%% for each vertex %%v \in V%%. A property testing algorithm in the traditional centralised setting is allowed query access to the graph, where each query involves asking the ID of the neighbour at index %%i%% in the adjacency list of some vertex %%v \in V%%. The cost of the algorithm is defined as the number of queries required to decide whether the underlying input graph satisfies a property or is far from it. In this setting, there are known expansion testing algorithms that make %%\tilde O(n^{1/2 + \mu})%% queries for a constant %%\mu \in (0, 1/4)%%. All the algorithms in the traditional setting follow the original query strategy proposed by Glodreich and Ron, where one performs %%\Omega(\sqrt n)%% random walks of appropriate length from a random starting point in the graph and count the overall number of pairwise collisions. In a good expander the walks mix quickly and The algorithms does not observe a lot of pairwise collisions. On a bad expander the algorithm witnesses more than a certain threshold of pairwise collisions. The only known parallel (MPC) algorithm also relies on observing the number of pairwise collisions from a lot more %%O(n)%% random walks, precisely %%2%% walks from every vertex in the graph.

The only known distributed algorithm for this task runs a polynomial number of walks %%O(n^100)%% from a random starting point in the graph. It does not count the number of pairwise collisions but still uses a precomputed spanning tree to collect information from every node to a central point (the root of the spanning tree) to decide if the graph has good expansion or is far from it. In our work we address the question of whether one needs ‘global’ information (and hence a spanning tree) to test the expansion in distributed setting. Can one devise a purely distributed algorithm relying on ‘local’ information (within a constant radius ball of a node) to distinguish between a good expander and the one that is far from it. The partial results we have suggest that a purely local testing criteria is possible even with close to %%\tilde O(n^2)%% number of walks from a random starting point.

As a testing criteria we count for every node %%v \in V%%, the number of walks that end at %%v%% after %%\theta(\log n)%% steps. On a good expander, every node witnesses nearly 'equal’ number of walks with high probability. But if the graph is far from being a good expander, then with good probability, there is at least one node in the graph which witnesses more than a certain number of walks.

Thursday 16 June - Marco Cheung (Royal Holloway UoL)

Instability and Chaos of Learning-in-Games via Volume Analysis
A fundamental question in game theory is how a Nash equilibrium of a game may be reached under a plausible model of interactions between players. A tempting choice is to model the players as learners, where they use adaptive/learning algorithms (e.g. Multiplicative Weights Update, or MWU) to choose strategies. However, it was empirically observed that MWU is unstable and unpredictable even in very simple games. In this talk, we present a theoretical explanation of these observations. We show that Lyapunov chaos (butterfly effect) occurs persistently when using MWU in general two-person zero-sum games. This result is extended to other learning algorithms including Optimistic MWU and Follow-the-Regularized-Leader algorithms, and to other games including coordination games and graphical constant-sum games. The main technique used is volume analysis, in which volume is adopted as a measure of unpredictability. This talk is based on the joint work with Georgios Piliouras and Yixin Tao.

Thursday 9 June - Gilat Levy (LSE)

Persuasion with Correlation Neglect: A Full Manipulation Result
We consider an information design problem in which a sender tries to persuade a receiver that has "correlation neglect", i.e. fails to under-stand that signals might be correlated. We show that a sender with un-limited number of signals can fully manipulate the receiver. Specifically, the sender can induce the receiver to hold any state-dependent posterior she wishes to. If the sender only wishes to induce a state-independent posterior, she can use fully correlated signals, but generally she needs to design more involved correlation structures.

By Gilat Levy, Ineś Moreno de Barreda, Ronny Razin.

Friday 27 May - Daniel Kadnikov (University of Edinburgh)

A Model of Strategic Decision Making Starting from Information Structure and Choices
Game theory studies normal and extensive form games to model interactive decision making. We propose a third more abstract tree-free approach based only on the information structure and choices (IC-form) and study geometry of binary matrices which any IC-form induces. In fact, orthogonality of two vectors of any such matrix is not coincidental and allows us to recover information and choices from strategies under certain conditions (which are perfect recall and COA-stability). This generalises results obtained in Mailath et al. (Econometrica 1993, JET 1994). We present sets of axioms allowing an IC-form to have normal and extensive form representations. Besides demonstrating fundamental relations between the three forms, this gives an answer to a question opened from the 1970s in control theory, namely, finding axioms under which a certain class of IC-forms is solvable.

(joint with Philipp C. Wichardt)

Wednesday 30 March - Robert Simon (LSE)

A measure theoretic paradox from a continuous colouring rule
Given a probability space %%(X, {\cal B}, m)%%, measure preserving transformations %%g_1, \dots , g_k%% of %%X%%, and a colour set %%C%%, a colouring rule is a way to colour the space with %%C%% such that the colours allowed for a point %%x%% are determined by that point's location and the colours of the finitely %%g_1 (x), \dots , g_k(x)%% with %%g_i(x) \not= x%% for all %%i%% and almost all %%x%%. We represent a colouring rule as a correspondence %%F%% defined on %%X\times C^k%% with values in %%C%%. A function %%f: X\rightarrow C%% satisfies the rule at %%x%% if %%f(x) \in F( x, f(g_1 x), \dots , f(g_k x))%%. A colouring rule is paradoxical if it can be satisfied in some way almost everywhere with respect to %%m%%, but not in {\bf any} way that is measurable with respect to a finitely additive measure that extends the probability measure %%m%% defined on %%{\cal B}%% and for which the finitely many transformations %%g_1, \dots , g_k%% remain measure preserving. Can a colouring rule be paradoxical if both %%X%% and the colour set %%C%% are convex and compact sets and the colouring rule says if %%c: X\rightarrow C%% is the colouring function then the colour %%c(x)%% must lie (%%m%% a.e.) in %%F(x, c(g_1(x) ), \dots , c(g_k(x)))%% for a non-empty upper-semi-continuous convex-valued correspondence %%F%% defined on %%X\times C^k%%? The answer is yes, and we present such an example. We show that this result is robust, including that any colouring that approximates the correspondence by %%\epsilon%% for small enough positive %%\epsilon%% also cannot be measurable in the same finitely additive way. Because non-empty upper-semi-continuous convex-valued correspondences on Euclidean space can be approximated by continuous functions, there are paradoxical colouring rules that are defined by continuous functions.

Thursday 31 March - Vida Dujmović (uOttawa)

Graph Product Structure Theorem
This talk will introduce the product structure theorem. It states that every planar graph is a subgraph of the strong product of a path and a bounded treewidth graph. The theorem has led to resolutions of several open problems on planar graphs. Time permitting, I will also present some of these applications of the product structure theorem. The theorem can also be generalized from planar graphs to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

Friday 25 March - Amedeo Sgueglia (LSE)

Multistage Maker-Breaker Games
We consider a new procedure, which we call Multistage Maker-Breaker Game. Maker and Breaker start from %%G_0:=K_n%% and play several stages of a usual Maker-Breaker game where, for %%i \ge 1%%, the %%i%%-th stage is played as follows. They claim edges of %%G_{i-1}%% until all edges are distributed, and then they set%%G_i%% to be the graph consisting only of Maker's edges. They will then play the next stage on %%G_i%%.
This creates a sequence of graphs %%G_0 \supset G_1 \supset G_2 \supset \dots%% and, given a monotone graph property, the question is how long Maker can maintain it, i.e. what is the largest %%k%% such that Maker has a strategy to guarantee that %%G_k%% satisfies such property. We will answer this question for several graph properties and pose a number of interesting questions that remain open.

This is joint work with Juri Barkey, Dennis Clemens, Fabian Hamann, and Mirjana Mikalački.

Thursday 24 March - Katherine Staden (Open University)

The Erdős-Rothschild problem
Questions about forbidden subgraphs form a central part of extremal graph theory. In this talk I will discuss a colourful problem of this sort: the Erdős-Rothschild problem from 1974. Consider an n-vertex graph G whose edges are coloured with s colours so that there is no monochromatic clique of size k, and call such a colouring of G valid. The problem is to determine the maximum number of valid colourings over all n-vertex graphs G. It is in general wide open and an exact (or even asymptotic) answer is only known for a few pairs (k,s). In this talk I will discuss new exact results, and intriguing connections to algebra and designs.

Joint work with Oleg Pikhurko.

Friday 18 March - Johannes Brustle (LSE)

The Competition Complexity of Dynamic Pricing
We study the competition complexity of dynamic pricing relative to the optimal auction in the fundamental single-item setting.
In prophet inequality terminology, we compare the expected reward %%A_m(F)%% achievable by the optimal online policy on %%m%% i.i.d.~random variables drawn from %%F%% to the expected maximum %%M_n(F)%% of %%n%% i.i.d.~draws from the same distribution. We ask how big does %%m%% have to be to ensure that %%(1+\varepsilon) A_m(F) \geq M_n(F)%% for all %%F%%.
We resolve this question and exhibit a stark phase transition: When %%\varepsilon = 0%% the competition complexity is unbounded. That is, for any %%n%% and any %%m%% there is a distribution %%F%% such that %%A_m(F) < M_n(F)%%. In contrast, for any %%\varepsilon > 0%%, it is sufficient and necessary to have %%m = \phi(\varepsilon)n%% where %%\phi(\varepsilon) = \Theta(\log \log 1/\varepsilon)%%. Therefore, the competition complexity not only drops from being unbounded to being linear, it is actually linear with a very small constant.

Thursday 17 March - Laura Sanita (University of Waterloo)

On the Simplex method for 0/1 polytopes
The Simplex method is one of the most popular algorithms for solving linear programs, but despite decades of study, it is still not known whether there exists a pivot rule that guarantees it will always reach an optimal solution with a polynomial number of steps.
In fact, a polynomial pivot rule is not even known for linear programs over 0/1 polytopes (0/1-LPs), despite the fact that the diameter of a 0/1 polytope is bounded by its dimension.
This talk will focus on the behavior of the Simplex method for 0/1-LPs, and discuss simple pivot rules that are guaranteed to require only a polynomial number of non-degenerate pivots.

Joint work with: Alexander Black, Jesus De Loera, Sean Kafer.

Friday 11 March - Stijn Cambie (University of Warwick)

Packing list-colourings for small maximum degree
List colouring is an influential and classic topic in graph theory, which is related to e.g. frequency assignment, resource allocation and scheduling problems. Sometimes it is natural to consider multiple of these and the best one can aim for is a packing of disjoint solutions/list colourings. We investigate this natural strengthening, the list packing problem. This study was already suggested 25 years ago by Alon, Fellows and Hare.
Dvorak and Postle also considered a correspondence version of list colouring, nowadays sometimes called DP-colouring. So we also can consider the related correspondence packing version. It turns out that there are relations with existing conjectures stated with independent transversals.
In this talk, we give an introduction/recap to the concepts and some intuition behind it, and focus on some precise maximum degree versions.
As such, we complement the talk of Ewan Davies from the 10th of December with a self-contained presentation.

Thursday 10 March - Christoph Hertrich (LSE)

Towards Lower Bounds on the Depth of ReLU Neural Networks
We contribute to a better understanding of the class of functions that is represented by a neural network with ReLU activations and a given architecture. Using techniques from mixed-integer optimization, polyhedral theory, and tropical geometry, we provide a mathematical counterbalance to the universal approximation theorems which suggest that a single hidden layer is sufficient for learning tasks. In particular, we investigate whether the class of exactly representable functions strictly increases by adding more layers (with no restrictions on size). We also present upper bounds on the sizes of neural networks required for exact function representation. This is joint work with Amitabh Basu, Marco Di Summa, and Martin Skutella.

Friday 4 March - Bento Natura (LSE)

Wandering through polytopes: New bounds on circuit diameter and curvature of central paths
The polynomial Hirsch conjecture states that the diameter of a polytope is polynomial in the number of its facets. The conjecture is wide open and necessary for the existence of polynomial simplex methods.
Recent years have seen the study of the <i>circuit diameter</i>, which expands the set of potential augmenting directions. In this talk, we present improved polynomial circuit diameter bounds for polytopes which possess a matrix representation with bounded integer entries.
Alternative algorithms to solve linear programs include interior-point-methods, which follow a certain path through the interior of the polytope. The iteration complexity of these methods is closely tied to a notion of total path curvature. We present improved upper bounds on this curvature.

Thursday 3 March - Caroline Terry (OSU)

Constraining irregular triads in 3-uniform hypergraphs
A well-known folklore result says that any %%\epsilon%%-regular partition of a large half-graph must have an irregular pair. A converse to this result was later shown by Malliaris and Shelah: if a graph G contains no half-graph of height k, then it admits a regular partition with no irregular pairs. These results can be rephrased neatly in terms of hereditary properties. A hereditary graph property is a class of finite graphs closed under induced subgraphs and isomorphism. Then the results above give a combinatorial characterization when a hereditary graph property %%H%% has the property that all graphs in %%H%% admit regular decompositions with no irregular pairs.
In this talk we present joint work with Julia Wolf which gives a new generalization of these results to the setting of 3-uniform hypergraphs, with respect to the strong regularity for 3-uniform hypergraphs first developed by Frankl and Gowers. In particular, we give a combinatorial characterization of the hereditary properties of 3-uniform hypergraphs which admit regular decompositions with error sets that are “constrained” by certain lower arity sets.

Friday 25 February - Joanna Lada (LSE)

Minimum degree thresholds for colour-biased Hamilton cycles in dense graphs
This talk concerns problems of the following form: Given a host graph %%G%% and any %%r%%-colouring of its edges, and given a target graph %%H%%, can one guarantee to find a copy of %%H%% in %%G%% which uses significantly more than %%\frac{E(H)}{r}%% edges of one colour?
The study of problems of this kind was initiated by Erdős in the 1960s, albeit in the context of graph discrepancy- equivalent to the special case %%r=2%%. Since then a number of results have been found for different classes of graphs %%G%% to contain a high-discrepancy copy of a graph %%H%% including spanning trees, paths and Hamilton cycles.
However, only recently has attention been directed to the %%r>2%% case. In this talk, we generalise a result of Balogh, Csaba, Jing, Pluhár (2020) to obtain a tight minimum degree threshold for colour-biased Hamilton cycles in %%r%%-coloured graphs %%G%%. We will also touch on subsequent improvements made by Gishboliner, Krivelevich and Michaeli (2020), and, time permitting, a random graph version of the result by the same authors.
This talk is based on joint work with Andrea Freschi, Andrew Treglown (University of Birmingham) and Joseph Hyde (Warwick University).

Thursday 24 February - Letícia Mattos (FU Berlin)

Clique packings in random graphs
Let u(n,p,k) be the k-clique packing number of the random graph G(n,p), that is, the maximum number of edge-disjoint k-cliques in G(n,p). In 1992, Alon and Spencer conjectured that for p = 1/2 we have u(n,p,k) = Ω(n²/k²) when k = k(n,p) - 4, where k(n,p) is minimum t such that the expected number of t-cliques in G(n,p) is less than 1. This conjecture was disproved a few years ago by Acan and Kahn, who showed that in fact u(n,p,k) = O(n²/k³) with high probability, for any fixed p ∈ (0,1) and k = k(n,p) - O(1).
In this talk, we show a lower bound which matches Acan and Kahn's upper bound on u(n,p,k) for all p ∈ (0,1) and k = k(n,p) - O(1). To prove this result, we follow a random greedy process and use the differential equation method. This is a joint work with Simon Griffiths and Rob Morris.

** CANCELLED ** Friday 18 February - Johannes Brustle (LSE)

Thursday 17 February - Bernhard von Stengel (LSE)

Zero-Sum Games and Linear Programming Duality
This is a largely expository talk on the close connection between the minimax theorem for zero-sum games and LP duality, the strong duality theorem of linear programming. Both are central theorems in game theory and operations research.
The mathematical essence of the minimax theorem is about nonnegative solutions of a vector x to homogeneous linear equations Ax=0, whereas that of LP duality is about nonnegative solutions x to inhomogeneous equations Ax=b. It is stubbornly hard (and work in progress) to go from Ax=0 to Ax=b without proving LP duality more or less already, because in the equation Ax-bt=0 the scalar t cannot easily be forced to be positive even if such a solution exists.
We outline the classic, often beautiful proofs of these theorems.

Friday 11 February - Eoin Hurley (Universität Heidelberg)

Sufficient Conditions for Perfect Mixed Tilings
We develop a method to study sufficient conditions for perfect mixed tilings. Our framework allows the embedding of bounded degree graphs H with components of sublinear order. As a corollary, we recover and extend the work of Kühn and Osthus regarding sufficient minimum degree conditions for perfect F-tilings (for an arbitrary fixed graph F) by replacing the F-tiling with the aforementioned graphs H. Moreover, we obtain analogous results for degree sequences and in the setting of uniformly dense graphs. Finally, we asymptotically resolve a conjecture of Komlós in a strong sense.

Thursday 10 February - Mehdi Makhul (Johannes Kepler University)

Probabilities of incidence between lines and a plane curve over finite fields
In this talk, we study the probability for a random line to intersect a given plane curve, over a finite field, in a given number of points over the same field. In particular, we focus on the limits of these probabilities under successive finite field extensions. We will compute these limits under a mildly stronger condition, known as simple tangency. Finally, Veronese maps allow us to compute similar probabilities of intersection between a given curve and random curves of a given degree.

Wednesday 9 February - Candida Bowtell (University of Oxford)

The n-queens problem
How many ways are there to place n queens on an n by n chessboard so that no two can attack one another? What if the chessboard is embedded on the torus? Let Q(n) be the number of ways on the standard chessboard and T(n) the number on the toroidal board. The toroidal problem was first studied in 1918 by Pólya who showed that T(n)>0 if and only if n is not divisible by 2 or 3. Much more recently Luria showed that T(n) is at most ((1+o(1))ne^{-3})^n and conjectured equality when n is not divisible by 2 or 3. We prove this conjecture, prior to which no non-trivial lower bounds were known to hold for all (sufficiently large) n not divisible by 2 or 3. We also show that Q(n) is at least ((1+o(1))ne^{-3})^n for all natural numbers n which was independently proved by Luria and Simkin and, combined with our toroidal result, completely settles a conjecture of Rivin, Vardi and Zimmerman regarding both Q(n) and T(n).
In this talk we'll discuss our methods used to prove these results. A crucial element of this is translating the problem to one of counting matchings in a 4-partite 4-uniform hypergraph. Our strategy combines a random greedy algorithm to count `almost' configurations with a complex absorbing strategy that uses ideas from the methods of randomised algebraic construction and iterative absorption.

This is joint work with Peter Keevash.

Friday 4 February - Karl Stickler (LSE)

Persistency of linear programming relaxations for the stable set problem
The Nemhauser-Trotter theorem states that the standard linear programming (LP) formulation for the stable set problem has a remarkable property, also known as (weak) persistency: for every optimal LP solution that assigns integer values to some variables, there exists an optimal integer solution in which these variables retain the same values.
While the standard LP is defined by only non-negativity and edge constraints, a variety of stronger LP formulations have been studied and one may wonder whether any of them has this property as well.
In this talk we discuss that any stronger LP formulation that satisfies mild conditions cannot have the persistency property on all graphs, unless it is always equal to the stable-set polytope.

Friday 28 January - Pranshu Gupta (TUHH)

Ramsey simplicity of random graphs
We say that a graph G is q-Ramsey for another graph H if in any q-edge-colouring of G there is a monochromatic copy of H. The classic Ramsey problem asks for the minimum number of vertices in a graph G that is q-Ramsey for H. This central line of research was then broadened in the seminal work of Burr, Erdős, and Lovász to include the investigation of other extremal parameters of Ramsey graphs, including the minimum degree of minimal Ramsey graphs.
It is not hard to see that if G is minimally q-Ramsey for H we must have δ(G) >= q(δ(H) - 1) + 1, and we say that a graph H is q-Ramsey simple if this bound can be attained. Grinshpun showed that this is typical of rather sparse graphs, proving tha the random graph G(n,p) is almost surely 2-Ramsey simple when log n / n << p << n^{-2/3}. In this paper, we explore this question further, asking for which pairs p = p(n) and q = q(n,p) we can expect G(n,p) to be q-Ramsey simple. We resolve the problem for a wide range of values of p and q; in particular, we uncover some interesting behaviour when n^{-2/3} << p << n^{-1/2}.

This is a joint work with Simona Boyadzhiyska, Dennis Clemens, and Shagnik Das.

Thursday 20 January - Lisa Sauermann (MIT)

On polynomials that vanish to high order on most of the hypercube
Motivated by higher vanishing multiplicity generalizations of Alon's Combinatorial Nullstellensatz and its applications, we study the following problem: for fixed k and n large with respect to k, what is the minimum possible degree of a polynomial P in R[x_1,...,x_n] such that P(0,…,0) is non-zero and such that P has zeroes of multiplicity at least k at all points in {0,1}^n except the origin? For k=1, a classical theorem of Alon and Füredi states that the minimum possible degree of such a polynomial equals n. We solve the problem for all k>1, proving that the answer is n+2k−3. Joint work with Yuval Wigderson.

Friday 10 December - Ewan Davies (CU Boulder)
Hybrid - 12:00 on Zoom, and 32L.G.15 (LSE students and staff only)

Colouring, transversals and packing
Current techniques for graph colouring seem unable to take full advantage of the structure of bipartite graphs, leading to a paucity of results for bipartite graphs that improve upon what we know about triangle-free graphs. For example, the list-chromatic number of a bipartite graph of maximum degree d is known to be at most (1+o(1)) d/ log d, which can be shown using only triangle-freeness. Motivated by this, and by a hitherto overlooked comment in a paper of Alon, Fellows and Hare, we initiate the study packings of list colourings and strengthen a number of well-known results on list colouring to this substantially more challenging setting.

Thursday 9 December - Kanstantsin Pashkovich (University of Waterloo)
Hybrid - 14:00 on Zoom, and 32L.B.09 (LSE students and staff only)

Dynamic Pricing in Combinatorial Markets with Multidemand Players
Online markets are a part of everyday life, and their rules are governed by algorithms. Assuming participants are inherently self-interested yet truthful, well designed rules can help to increase social welfare. Many algorithms for online markets are based on prices: the seller is responsible for posting prices while buyers make purchases which are most profitable given the posted prices. To make adjustments to the market the seller is allowed to update prices at certain timepoints.
Despite the fact that each buyer acts selfishly, the seller's goal is often assumed to be that of social welfare maximization. Berger, Eden and Feldman recently considered the case of a market with only three buyers where each buyer has a fixed number of goods to buy and the profit of a bought bundle of items is the sum of profits of the items in the bundle. For such markets, Berger et.al. showed that the seller can maximize social welfare by dynamically updating posted prices before arrival of each buyer. We show that dynamically updating posted prices we can reach social welfare in multidemand markets with at most four players and also in further settings of the market.
(Joint work with Xinyue Xie)

Friday 3 December - Clément Legrand-Duchesne (LaBRI)

Recoloring version of Hadwiger's conjecture
Las Vergnas and Meyniel conjectured in 1981 that all the t-colorings of a K_t-minor free graph are Kempe equivalent. This conjecture can be seen as a reconfiguration counterpoint to Hadwiger's conjecture, although it neither implies it or is implied by it. We prove that for all positive epsilon, for all large enough t, there exists a graph with no K_{(2/3 + epsilon)t} minor whose t-colorings are not all Kempe equivalent, thereby strongly disproving this conjecture, along with two other conjectures of the same paper.

Thursday 2 December - Shoham Letzter (UCL)

Immersion of complete digraphs
We say that a (di)graph G immerses a (di)graph H is there is an injection f from V(H) to V(G), and a collection of pairwise edge disjoint paths, indexed by the edges of H, such that the path corresponding to uv starts at f(u) and ends at f(v). Say that a digraph is Eulerian if the in-degree of u equals its out-degree, for every vertex u.
We prove that there exists a constant C such that every Eulerian digraph with minimum in-degree at least Ct immerses a complete digraph on t vertices, answering a question of DeVos, McDonald, Mohar and Scheide (2012).
This is joint work with António Girão.

Wednesday 1 December - Gerard Cornuejols (Carnegie Mellon University)

Total Dual Dyadicness
A rational number is dyadic if it is an integer multiple of 1/2^k for some nonnegative integer k. Dyadic numbers are important for numerical computations because they have a finite binary representation, and therefore dyadic numbers can be represented exactly on a computer in floating-point arithmetic. In this talk we discuss when a linear system Ax <= b is totally dual dyadic, that is, for all integral vectors w for which min ( yb : yA = w, y >= 0} has a solution, it has a dyadic optimal solution. This is joint work with Ahmad Abdi, Bertrand Guenin and Levent Tuncel.

Friday 26 November - Domenico Mergoni (LSE)

Ramsey number for square of paths
The Ramsey number R_2(G) is the minimum n such that any 2-edge coloured K_n contains a monochromatic copy of G.
The Ramsey number of paths was determined very early on, but surprisingly very little is known about the Ramsey number for the powers of paths. In this seminar we investigate this problem for the square of long paths.
Joint work with P. Allen, J. Skokan, B. Roberts.

Thursday 25 November - Stefan Weltge (Technical University of Munich)

Binary scalar products
Let %%A,B \subseteq \mathbb{R}^d%% both span %%\mathbb{R}^d%% such that %%\langle a,b \rangle \in \{0,1\}%% holds for all %%a \in A%%, %%b \in B%%. We show that %%|A| \cdot |B| \le (d+1)2^d%%. This allows us to settle a conjecture by Bohn, Faenza, Fiorini, Fisikopoulos, Macchia, and Pashkovich (2015) concerning 2-level polytopes. Such polytopes have the property that for every facet-defining hyperplane %%H%% there is a parallel hyperplane %%H'%% such that %%H \cup H'%% contain all vertices. The authors conjectured that for every %%d%%-dimensional %%2%%-level polytope %%P%% the product of the number of vertices of %%P%% and the number of facets of %%P%% is at most %%d2^{d+1}%%, which we show to be true. This is joint work with Andrey Kupavskii.

Friday 19 November - Jane Tan (University of Oxford)

How to make graph reconstruction harder
The %%\ell%%-deck of a graph %%G%% is the multiset of all induced subgraphs of %%G%% on %%\ell%% vertices. Kelly and Ulam's classical reconstruction conjecture states that all graphs on %%n\geq 3%% vertices are uniquely determined by (or \emph{reconstructible} from) their %%(n-1)%%-decks. This conjecture is very much open, and has blossomed into a rich area with many variants being actively studied. The main focus of this talk is one in which we make the problem even harder by considering smaller cards (i.e. taking %%\ell%% small). We will show that trees are reconstructible from their %%\ell%%-decks when %%\ell\geq (8/9+o(1))n%%, improving on a result of Giles from 1976 which required %%\ell \geq n-2%%. This is good news for a conjecture of N\'ydl, although we have some bad news for that conjecture as well. If time allows, we will also survey progress on another variant in which we are missing some cards from the deck. Based on joint work with Carla Groenland, Andrey Kupavskii, Tom Johnston and Alex Scott.

Thursday 18 November - Matthias Englert (University of Warwick)

Improved Approximation Guarantees for Shortest Superstrings using Cycle Classification by Overlap to Length Ratios
In the Shortest Superstring problem, we are given a set of strings and we are asking for a common superstring that has the minimum number of characters. The Shortest Superstring problem is NP-hard and several constant-factor approximation algorithms are known.
Of particular interest is the GREEDY algorithm, which repeatedly merges two strings of maximum overlap until a single string remains. The GREEDY algorithm, being simpler than other well-performing approximation algorithms for this problem, has a long history going back to the 1980s. Tarhio and Ukkonen (TCS 1988) conjectured that GREEDY gives a 2-approximation. Blum, Jiang, Li, Tromp, and Yannakakis (STOC 1991) proved that the superstring computed by GREEDY is a 4-approximation, and this upper bound was improved to 3.5 by Kaplan and Shafrir (IPL 2005).
We show that the approximation guarantee of GREEDY is at most 3.425, making the first progress on this question since 2005. Furthermore, we prove that the Shortest Superstring can be approximated within a factor of 2.475, improving slightly upon the currently best approximation algorithm of about 2.478 by Mucha (SODA 2013).

Friday 12 November - Irene Gil-Fernández (University of Warwick)

New lower bounds on kissing numbers and spherical codes in high dimensions
Let the kissing number %%K(d)%% be the maximum number of non-overlapping unit balls in %%\mathbb R^d%% that can touch a given unit ball. Determining or estimating the number %%K(d)%% has a long history, with the value of %%K(3)%% being the subject of a famous discussion between Gregory and Newton in 1694. We give an improvement to the previously best known bound of Jenssen, Joos and Perkins for %%K(d)%% as %%d%% goes to infinity, by a factor of %%\log(3/2)/\log(9/8)+o(1)=3.442...%%. Our proof is based on the novel approach from Jenssen, Joos and Perkins that uses the hard core sphere model of an appropriate fugacity. Similar constant-factor improvements in lower bounds are also obtained for general spherical codes, as well as for the expected density of random sphere packings in the Euclidean space %%\mathbb R^d%%.
The talk is based on joint work with Jaehoon Kim, Hong Liu and Oleg Pikhurko.

Friday 5 November - Peleg Michaeli (Carnegie Mellon University)

Discrepancies of Spanning Trees
Discrepancy theory is concerned with colouring elements of a ground set so that each set in a given set system is as balanced as possible. In the graph setting, the ground set is the edge set of a given graph, and the set system is a family of subgraphs. In this talk, I shall discuss the discrepancy of the set of spanning trees in general graphs, a notion that has been recently studied by Balogh, Csaba, Jing and Pluhár. More concretely, for every graph G and a number of colours r, we look for the maximum D such that in any r-colouring of the edges of G one can find a spanning tree with at least (n-1+D)/r edges of the same colour. As our main result, we show that under very mild conditions (for example, if G is 3-connected), the discrepancy equals, up to a constant factor, to the minimal integer s such that G can be separated into r equal parts by removing s vertices. This strong and perhaps surprising relation between this extremal quantity and a geometric quantity allows us to estimate the spanning-tree discrepancy for many graphs of interest. In particular, we reprove and generalize results of Balogh et al. and obtain new ones. For certain graph families, we also get tight asymptotic results.

The talk is based on joint work with Lior Gishboliner and Michael Krivelevich.

Thursday 4 November - Mehmet Ismail (King's College London)

The strategy of conflict and cooperation
In this paper, I introduce a novel framework named cooperative extensive form games, and a novel solution concept, named cooperative equilibrium system. I illustrate that non-cooperative extensive form games are a special case of cooperative extensive form games, in which players can strategically cooperate (e.g., by writing a possibly costly contract) or act independently. To the best of my knowledge, cooperative equilibrium system, which always exists in finite n-person games, gives the first complete solution to the long-standing open problem of "strategic cooperation" first proposed by von Neumann (1928). Finally, cooperative strategic games unify the study of strategic competition as well as cooperation including logrolling and corruption which have been studied in specific frameworks.

Friday 29 October - Vincent Pfenninger (University of Birmingham)

Large monochromatic tight cycles in 2-edge-coloured complete 4-uniform hypergraphs
A 4-uniform tight cycle is a 4-uniform hypergraph with a cyclic ordering of its vertices such that its edges are precisely the sets of 4 consecutive vertices in the ordering.
Given a 2-edge-coloured complete 4-uniform hypergraph, we consider the following two questions.
1) What is the length of the longest monochromatic tight cycle? In other words, what is the Ramsey number for tight cycles?
2) How many tight cycles are needed to partition the vertex set? This is a generalisation of Lehel's conjecture for graphs.
In this talk, I will highlight a common approach, which yields some asymptotic results for these two questions. The approach is based on Łuczak's connected matching method together with a novel auxiliary graph, which I call the blueprint. This is joint work with Allan Lo.

Thursday 28 October - János Flesch (Maastricht University)

A competitive search game with a moving target
We introduce a discrete-time search game, in which two players compete to find an object first. The object moves according to a time-varying Markov chain on finitely many states. The players know the Markov chain and the initial probability distribution of the object, but do not observe the current state of the object. The players are active in turns. The active player chooses a state, and this choice is observed by the other player. If the object is in the chosen state, the active player wins and the game ends. Otherwise, the object moves according to the Markov chain and the game continues at the next period. We show that this game admits a value, and for any error-term epsilon>0, each player has a pure (subgame-perfect) epsilon-optimal strategy. Interestingly, a 0-optimal strategy does not always exist. We derive results on the properties of the value and the epsilon-optimal strategies. We devote special attention to the time-homogeneous case, where additional results hold. We also investigate a related model, where the active player is chosen randomly at each period. In this case, the results are quite different, and greedy strategies (which always recommend to choose a state that contains the object with the highest probability) play the main role.

The talk is based on two papers. The first is joint work with Benoit Duvocelle, Mathias Staudigl, Dries Vermeulen, and the second with Benoit Duvocelle, Hui Min Shi, Dries Vermeulen.

Thursday 14 October - Ahmad Abdi (LSE)

Dyadic Linear Programming
Most linear programming solvers use fixed-precision floating points to approximate the rational numbers. Though successful on most real-world instances, solvers sometimes run into serious issues when carrying out sequential floating-point arithmetic, due to compounded error terms. This practical limitation leads to the following theoretical problem:

Given a linear program, determine whether it admits an optimal solution whose entries have an exact floating-point representation.

This question motivates the study of Dyadic Linear Programming, a problem that sits somewhere between Linear Programming and Integer Linear Programming, and benefits surprisingly from both worlds.
In this talk, I will talk about ongoing projects on this topic, and address some of the basic questions. I will also discuss applications and connections to some classical problems in Combinatorial Optimization, including the Cycle Double Cover Conjecture, and the Generalized Berge-Fulkerson Conjecture.
Based on collaborations with Bertrand Guenin, Gérard Cornuéjols, Zuzanna Palion, and Levent Tunçel.

Thursday 7 October - Franziska Eberle (LSE)

Online Graph Exploration – Old and New Results
Exploring unknown environments is a fundamental task in many domains, e.g., robot navigation, network security, and internet search. In this talk, we give an overview of the current state of the art in online graph exploration in the fixed graph scenario. We provide details and lower bound examples of some algorithms such as the Nearest Neighbour (NN) algorithm with its competitive ratio of O(log n).
Afterwards, we design a general framework to robustify algorithms that carefully interpolates between a given algorithm and NN. We prove new performance bounds that leverage the individual good performance on particular inputs while establishing robustness to arbitrary inputs. This robustification schemes also allows us to initiate the study of a learning-augmented variant of the problem by adding access to machine-learned predictions and naturally integrating these predictions into the NN algorithm. This method significantly outperforms any known online algorithm if the prediction is of high accuracy while maintaining good guarantees when the prediction is of poor quality.

Seminar and PhD Seminar on Combinatorics, Games and Optimisation:

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