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:

Thursday 20 January - Lisa Sauermann (MIT)
14:00 on Zoom

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.

Thursday 27 January - Candida Bowtell (University of Oxford)
14:00 on Zoom

Title and abstract TBC.

Previous seminars in the series:

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:

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