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 on Zoom.
the PhD seminar takes place on Fridays at 12.00 on Zoom (the duration of the seminar will be 25 or 50 minutes, please see below for details).

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

IMPORTANT - Due to the ongoing COVID-19 epidemic seminars will now take place online.

Upcoming speakers:

The seminar series will re-start in October 2021.

Previous seminars in the series:

Friday 18 June - Nicolás Sanhueza-Matamala (Czech Academy of Sciences)

Cycle decompositions in 3-uniform graphs
We show that %%3%%-graphs on %%n%% vertices whose codegree is at least %%(2/3+o(1))n%% can be decomposed into tight cycles and admit Euler tours, subject to the trivial necessary divisibility conditions. We also provide a construction showing that our bounds are best possible up to the %%o(1)%% term. All together, our results answer in the negative some recent questions of Glock, Joos, Kühn, and Osthus. Joint work with Simón Piga (Hamburg).

Thursday 17 June - Paul Harrenstein (University of Oxford)

A Mathematical Analysis of an Election System Proposed by Gottlob Frege
by Paul Harrenstein, Martin Lackner and Marie-Louise Lackner
In 1998 a long-lost proposal for an election law by Gottlob Frege (1848– 1925) was rediscovered in the Thüringer Universitäts- und Landesbibliothek in Jena, Germany. The method that Frege proposed for the election of representatives of a constituency features a remarkable concern for the representation of minorities. Its core idea is that votes cast for unelected candidates are carried over to the next election, while elected candidates incur a cost of winning. In this talk we show that this sensitivity to past elections guarantees a proportional representation of political opinions in the long run. We find that through a slight modification of Frege’s original method even stronger proportionality guarantees can be achieved. This modified version of Frege’s method also provides a novel solution to the apportionment problem, which is distinct from all of the best-known apportionment methods, while still possessing noteworthy proportionality properties.

Friday 11 June - Shunhua Jiang (Columbia University)

Solving Tall Dense SDPs in the Current Matrix Multiplication Time
In this talk I will introduce a new interior point method algorithm that solves semidefinite programming (SDP) with variable size %%n \times n%% and %%m%% constraints in the (current) matrix multiplication time %%m^{\omega}%% when %%m \geq \Omega(n^2)%%.
Our algorithm improves the state-of-the-art SDP solver [Jiang, Kathuria, Lee, Padmanabhan and Song, FOCS 2020], and it is optimal because even finding a feasible matrix that satisfies all the constraints requires solving an linear system in %%m^{\omega}%% time. Our algorithm is based on two novel techniques: 1. Maintaining the inverse of a Kronecker product using lazy updates. 2. A general amortization scheme for positive semidefinite matrices. Based on a joint work with Baihe Huang, Zhao Song, and Runzhou Tao.

Thursday 10 June - Sam Fiorini (Université libre de Bruxelles)

Integer programs with bounded subdeterminants and two nonzeros per row or column
We give strongly polynomial-time algorithms for integer linear programs defined by integer coefficient matrices whose subdeterminants are bounded by a constant and that contain at most two nonzero entries in each row or column.
The core of our approach is the first polynomial-time algorithm for the maximum weight stable set problem on graphs that do not contain more than $k$ vertex-disjoint odd cycles, where $k$ is any constant. Previously, polynomial-time algorithms were only known for $k=0$ (bipartite graphs) and for $k=1$. This is joint work with Gwenaël Joret (Brussels), Stefan Weltge (Munich) and Yelena Yuditsky (Brussels).

Tuesday 8 June - Annika Heckel (LMU)
Round the World Relay in Combinatorics

How does the chromatic number of a random graph vary?
How much does the chromatic number of the random graph G(n, 1/2) vary? Shamir and Spencer proved that it is contained in some sequence of intervals of length about n1/2. Alon improved this slightly to n1/2 / log n. Until recently, however, no lower bounds on the fluctuations of the chromatic number of G(n, 1/2) were known, even though the question was raised by Bollobás many years ago. I will talk about the main ideas needed to prove that, at least for infinitely many n, the chromatic number of G(n, 1/2) is not concentrated on fewer than n1/2-o(1) consecutive values.
I will also discuss the Zigzag Conjecture, made recently by Bollob\'as, Heckel, Morris, Panagiotou, Riordan and Smith: this proposes that the correct concentration interval length 'zigzags' between n1/4+o(1)) and n1/2+o(1), depending on n.
Joint work with Oliver Riordan.

Friday 4 June - Yannick Mogge (TUHH)

Connector-Breaker Games on random boards
A Maker-Breaker game is a two player positional game, in which both players alternatingly claim one or more elements of a given board. One player (Maker) tries to claim all elements of a winning set while the other player (Breaker) tries to prevent her from doing so. The connectivity game is a variant of a Maker-Breaker game in which the board is some graph %%G%% and the winning sets consist of all spanning trees of %%G%%.
By now, the Maker-Breaker connectivity game on a complete graph %%K_n%% or on a random graph %%G\sim G_{n,p}%% is well studied. Recently though, London and Pluhár introduced a new version of this game, in which Maker had to choose her edges in such a way that her graph stays connected throughout the game. They proved, that if Maker is allowed to claim one edge in each round, the threshold biases for the connectivity game played on %%K_n%% and %%G_{n,p}%% differ drastically from their respective values in the Maker-Breaker version, but if played on %%K_n%% and if Maker is allowed to claim two edges in each round, the threshold biases of both versions are of the same order. This led to the question if the threshold probability when playing on %%G_{n,p}%% and if both players are allowed to claim two edges in each round is of the same order as in the usual Maker-Breaker version. We give an answer to this question and prove that this is in fact not the case and determine the threshold probability for winning this game to be of size %%n^{-2/3+o(1)}%%.

This is joint work with Dennis Clemens and Laurin Kirsch.

Friday 28 May - Reka Kovacs (University of Oxford)

Binary Matrix Factorisation via Column Generation
Identifying discrete patterns in binary data is an important dimensionality reduction tool in machine learning and data mining. In this talk, we consider the problem of rank-k binary matrix factorisation (BMF) under Boolean arithmetic: given a binary matrix %%X%% of dimension %%n \times m%% and a fixed positive integer %%k%%, find two binary matrices %%A%% and %%B%% of dimension %%n \times k%% and %%k \times m%% such that the discrepancy between %%X%% and the Boolean product of %%A%% and %%B%% is minimum. We describe a mixed integer linear programming formulation with exponentially many variables and use column generation technique to solve its LP relaxation. The dual bound provided by our formulation is stronger than the bound given by previously available models for BMF. Experimental results on real world datasets demonstrate that our proposed method is effective at producing highly accurate factorisations.

Thursday 27 May - Andrew Lewis-Pye (LSE)

Consensus in the Permissionless Setting
In the distributed computing literature, consensus protocols have traditionally been studied in a setting where all participants are known to each other from the start of the protocol execution. In the parlance of the ‘blockchain’ literature, this is referred to as the permissioned setting. What differentiates the most prominent blockchain protocol Bitcoin from these previously studied protocols is that it operates in a permissionless setting, i.e. it is a protocol for establishing consensus over an unknown network of participants that anybody can join, with as many identities as they like in any role. I’ll talk about recent work with Tim Roughgarden in which we describe a formal framework for the analysis of both permissioned and permissionless systems.

Friday 21 May - Hung Hoang (ETH Zürich)

A Subexponential Algorithm for ARRIVAL
Suppose we run a train on a directed (multi-)graph, where every vertex has out-degree %%2%% and is equipped with a switch. At the beginning, the switch at each vertex points to one of the two outgoing edges. When the train reaches a vertex, it will traverse along the edge pointed by the switch, and then the switch at that vertex shifts to the other outgoing edge. Given such a graph with an origin vertex %%o%% and a destination vertex %%d%%, the problem is to decide if the train starting from %%o%% can reach %%d%%.
The problem above is called ARRIVAL. It is in NP and co-NP, but not known to be in P. The currently best algorithms have runtime %%2^{\Theta(n)}%% where n is the number of vertices. This is not much better than just performing the pseudorandom walk. In this talk, I will present a subexponential algorithm with runtime %%2^{O(\sqrt{n} \log n)}%%. This is joint work with Bernd Gärtner and Sebastian Haslebacher.

Thursday 20 May - Jinyoung Park (Institute for Advanced Study)

On a problem of M. Talagrand
We will discuss some special cases of a conjecture of M. Talagrand relating two notions of “threshold” for an increasing family of subsets of a finite set. The full conjecture implies equivalence of the “Fractional ExpectationThreshold Conjecture,” due to Talagrand and recently proved by Frankston, Kahn, Narayanan, and myself, and the (stronger) “Expectation-Threshold Conjecture” of Kahn and Kalai.

Talagrand showed that his conjecture is true in some special cases and suggested a couple of more challenging test cases. In the talk, I will give more detailed descriptions of this problem, and some proof ideas if time allows.
This is joint work with Keith Frankston and Jeff Kahn.

Friday 7 May - Amarja Kathapurkar (University of Birmingham)

Spanning trees in dense directed graphs
In 2001, Komlós, Sárközy and Szemerédi proved that for sufficiently large n, every n-vertex graph with minimum degree at least %%n/2 + o(n)%% contains a copy of every %%n%%-vertex tree with maximum degree at most %%O(n/log n)%%. We prove the corresponding result for directed graphs. That is, we show that for sufficiently large %%n%%, every n-vertex directed graph with minimum semidegree at least %%n/2 + o(n)%% contains a copy of every %%n%%-vertex oriented tree whose underlying maximum degree is at most %%O(n/log n)%%. This improves a recent result of Mycroft and Naia, which requires the oriented trees to have underlying maximum degree at most %%\Delta%%, for any constant %%\Delta%% and sufficiently large %%n%%. In contrast to the previous work on spanning trees in dense directed or undirected graphs, our approach does not use Szemerédi's regularity lemma. This is joint work with Richard Montgomery.

Thursday 6 May - Tom Lidbetter (Rutgers)

A Polyhedral Approach to Some Max-min Problems
We consider a max-min variation of the classical problem of maximizing a linear function over the base of a polymatroid. In our problem we assume that the vector of coefficients of the linear function is not a known parameter of the problem but is some vertex of a simplex, and we maximize the linear function in the worst case. Equivalently, we view the problem as a zero-sum game between a maximizing player whose mixed strategy set is the base of the polymatroid and a minimizing player whose mixed strategy set is a simplex. We show how to efficiently obtain optimal strategies for both players and an expression for the value of the game. Furthermore, we give a characterization of the set of optimal strategies for the minimizing player. We consider four versions of the game and discuss the implications of our results for problems in search, sequential testing and queueing. This is joint work with Lisa Hellerstein.

Thursday 1 April - Fatma Kılınç-Karzan (CMU)

Exactness in SDP Relaxations of Quadratically Constrained Quadratic Programs
Quadratically constrained quadratic programs (QCQPs) are a fundamental class of optimization problems. In a QCQP, we are asked to minimize a (possibly nonconvex) quadratic function subject to a number of (possibly nonconvex) quadratic constraints. Such problems arise naturally in many areas of operations research, computer science, and engineering. Although QCQPs are NP-hard to solve in general, they admit a natural family of tractable convex relaxations. In this talk, we will study the standard semidefinite program (SDP) relaxation for general QCQPs and examine when this relaxation is exact. By analyzing the "geometry" of the SDP relaxation, we will give both sufficient conditions and necessary conditions for different types of "exactness" conditions, and discuss a number of implications of these results for various applications.

This is joint work with Alex L. Wang and C.J. Argue.

Friday 26 March - Matías Pavez Signé (Universidad de Chile)

On the Erdős-Sós conjecture for bounded degree trees
In 1964, Erdős and Sós conjectured that any graph with average degree greater than %%k-1%% must contain a copy of every tree with %%k%% edges. In this talk, I will show a solution to this conjecture for trees with bounded maximum degree and dense host graphs. In particular, this implies a bound on the multi-colour Ramsey number for trees with bounded maximum degree.

Thursday 25 March - Edith Elkind (University of Oxford)

United for Change: Deliberative Coalition Formation to Change the Status Quo
We study a setting in which a community wishes to identify a strongly supported proposal from a space of alternatives, in order to change the status quo. We describe a deliberation process in which agents dynamically form coalitions around proposals that they prefer over the status quo. We formulate conditions on the space of proposals and on the ways in which coalitions are formed that guarantee deliberation to succeed, that is, to terminate by identifying a proposal with the largest possible support. Our results provide theoretical foundations for the analysis of deliberative processes, in particular in systems for democratic deliberation support, such as, for instance, LiquidFeedback or Polis.

Based on joint work with Davide Grossi, Nimrod Talmon, Udi Shapiro and Abheek Ghosh.

Friday 19 March - Jan van den Brand (KTH)

Unifying Matrix Data Structures: Simplifying and Speeding up Iterative Algorithms
Many algorithms use data structures that maintain properties of matrices undergoing some changes. The applications are wide-ranging and include for example matchings, shortest paths, linear programming, semi-definite programming, convex hull and volume computation. Given the wide range of applications, the exact property these data structures must maintain varies from one application to another, forcing algorithm designers to invent them from scratch or modify existing ones. Thus it is not surprising that these data structures and their proofs are usually tailor-made for their specific application and that maintaining more complicated properties results in more complicated proofs. In this talk, I present a unifying framework that captures a wide range of these data structures. The simplicity of this framework allows us to give short proofs for many existing data structures regardless of how complicated the to be maintained property is. We also show how the framework can be used to speed up existing iterative algorithms, such as the simplex algorithm.

Thursday 18 March - Yixin Tao (LSE)

On the existence of Pareto Efficient and envy-free allocation
Envy-freeness and Pareto Efficiency are two major goals in welfare economics. The existence of an allocation that satisfies both conditions has been studied for a long time. Whether items are indivisible or divisible, it is impossible to achieve envy-freeness and Pareto Efficiency ex-post even in the case of two people and two items. In contrast, in this talk, I'll present the following result, for any cardinal utility functions (including complementary utilities for example) and for any number of items and players, there always exists an ex-ante mixed allocation which is envy-free and Pareto Efficient, assuming the allowable assignments and utility functions satisfy an anonymity property. I'll also talk about the communication complexity for finding a Pareto Efficient and envy-free allocation. This is joint work with Richard Cole.

Friday 12 March - Samuel Mohr (Masaryk University)

Quasirandom Latin squares
A Latin square is an %%n\times n%% matrix filled with values of %%\{1, \dots, n\}%% in such a way that each row and each column contains each value exactly once, respectively. We present a limit theory of Latin squares developed by Garbe et al.~[arXiv:2010.07854], paralleling the recent limit theories of dense graphs and permutations. Moreover, we prove that a Latin square is quasirandom if and only if the density of every %%2\times 3%% pattern is %%1/720+o(1)%%. This result is the best possible in the sense that %%2\times 3%% cannot be replaced with %%2\times 2%% or %%1\times n%% for any %%n%%. This is joint work with Jacob W.~Cooper, Daniel Kráľ, and Ander Lamaison.

Thursday 11 March - Sophie Spirkl (University of Waterloo)

The Erdos-Hajnal conjecture for the five-cycle
The Erdos-Hajnal conjecture states that for every graph H there exists c > 0 such that every n-vertex graph G either contains H as an induced subgraph, or has a clique or stable set of size at least n^c. I will talk about a proof of this conjecture for the case H = C5 (a five-cycle), and related results. The proof is based on an extension of a lemma about bipartite graphs due to Pach and Tomon.

This is joint work with Maria Chudnovsky, Alex Scott, and Paul Seymour.

Friday 5 March - Jane Gao (University of Waterloo)

The sandwich conjecture of random regular graphs
Random regular graphs are extensively studied, whose analysis typically involves highly nontrivial enumeration arguments, especially when the degree grows fast as the number of vertices grows. Kim and Vu made a conjecture in 2004 that the random regular graph can be well approximated by the random binomial random graphs, in the sense that it is possible to construct %%G(n,d)%%, %%G(n,p_1)%% and %%G(n,p_2)%%, where %%d\sim np_1\sim np_2%%, in the same probability space so that with high probability %%G(n,p_1)\subseteq G(n,d)\subseteq G(n,p_2)%%. This is known as the sandwich conjecture. In this talk I will discuss some recent progress in this conjecture.

Thursday 4 March - Dion Gijswijt (Delft Institute of Applied Mathematics)

Constructing tree decompositions for graphs of bounded gonality
Divisorial gonality is a graph parameter that has its origins in algebraic geometry. It is a combinatorial analogue and lower bound for gonality of algebraic curves. In terms of the classical chip-firing game of Björner-Lovász-Shor it relates to chip configurations that result in a finite game, even after adding a chip at an arbitrary position.
In this talk we will show that gonality is an upper bound for the treewidth. Moreover, we give an algorithmic proof that produces a tree-decomposition of width equal to the gonality. We will conclude with some open problems.

Joint work with: Hans Bodlaender, Josse van Dobben de Bruyn, and Harry Smit.

Friday 26 February - Felix Clemen (UIUC)

Connecting discrete geometry with hypergraph Turán theory
A triangle %%T'%% is epsilon-similar to another triangle %%T%% if their angles pairwise differ by at most epsilon. Given a triangle %%T%%, %%\varepsilon>0%% and a natural number %%n%%, Bárány and Füredi asked to determine the maximum number of triangles being %%\varepsilon%%-similar to %%T%% in a planar point set of size %%n%%. We determine this quantity for almost all triangles %%T%%. Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof. This is joint work with József Balogh and Bernard Lidický.

Friday 19 February - Sahar Jahani (LSE)

Modelling the facility-location problem as a non-cooperative game and finding the Nash equilibria
In this seminar, we will talk about a planar location-price game in which two competing firms try to maximize their profits by selecting their locations and setting the delivered prices. Assuming that the firms set the equilibrium prices in the second stage, the game is reduced to a location game for which the existence of at least one pure Nash equilibrium is proved. Then we will talk about an algorithm to find all Nash equilibria that exploits the Weber points of the demand set’s partitions and seeks the Local and Global equilibria of the game between them.

Thursday 18 February - Kristina Vuskovic (University of Leeds)

Even-hole-free graphs with bounded degree have bounded treewidth
The class of even-hole-free graphs (i.e. graphs that do not contain a chordless cycle on an even number of vertices) has been studied since the 1990's, initially motivated by their structural similarity to perfect graphs. It is known for example that they can be decomposed by star cutsets and 2-joins into graphs that are line graphs of a tree plus at most two vertices, which has led to, for example, their polynomial time recognition. Nevertheless, the complexity of a number of classical computational problems remain open for this class, such as the coloring and stable set problems.
In this talk we show that even-hole-free graphs with bounded degree have bounded treewidth, resolving a conjecture of Aboulker, Adler, Kim, Sintiari and Trotignon. This implies that many algorithmic problems can be solved in polynomial time for this class. Furthermore, it shows that even-hole-freeness is testable in the bounded degree graph model of property testing.
Treewidth is a parameter that emerged out of the study of minor closed classes of graphs (i.e. classes closed under vertex and edge deletion, and edge contraction). It in some sense describes the global structure of a graph. Roughly, a graph has treewidth k if it can be decomposed by a sequence of noncrossing cutsets of size at most k into pieces of size at most k+1. The study of hereditary graph classes (i.e. those closed under vertex deletion only) reveals a different picture, where cutsets that are not necessarily bounded in size (such as star cutsets, 2-joins and their generalization) are required to decompose the graph into simpler pieces that are structured but not necessarily bounded in size. A number of such decomposition theorems are known for complex hereditary graph classes, including for even-hole-free graphs, perfect graphs and others. They do not describe the global structure in the sense that a tree decomposition does, since the cutsets guaranteed by these decomposition theorems are far from being noncrossing. In the case of even-hole-free graphs of bounded degree we show how these cutsets can be partitioned into a bounded number of well-behaved collections, which allows us to bound the treewidth of such graphs.

This is joint work with Tara Abrishami and Maria Chudnovsky.

Friday 12 February - Lucas Slot (Centrum Wiskunde & Informatica)

Sum-of-squares hierarchies for binary polynomial optimization
We consider the hierarchy of sum-of-squares approximations for the problem of computing the minimum value of a polynomial %%f%% over the %%n%%-dimensional boolean hypercube. This hierarchy provides lower bounds for each order %%r%% and is known to be exact at (roughly) order %%\frac{n+d}{2}%%, where %%d%% is the degree of %%f%%. We provide an asymptotic analysis for the quality of the bound in the regime where the order %%r%% is approximately equal to %%tn%% for some scalar %%0<t<\frac12%%, showing that the relative error is in the order %%\frac12 - \sqrt{t(1-t)}%%. Our analysis relies on constructing suitable feasible solutions using polynomial kernels, which we obtain by exploiting symmetry and Fourier analysis on the Boolean cube. A crucial tool is relating the sum-of-squares hierarchy to another hierarchy of measure-based *upper* bounds (also introduced by Lasserre), and to exploit a link to extremal roots of orthogonal polynomials (in this case the Krawtchouk polynomials). Our error analysis in fact also applies to this second hierarchy.

This is based on joint work with Monique Laurent.

Thursday 11 February - Emilio Pierro (LSE)

Finite Simple Groups and Generalised Polygons
The classification of generalised polygons which admit the distance-transitive action of a finite simple group has been long known. In this talk we discuss what can be said when the assumption of distance-transitivity is weakened to point-primitivity. Our side-aim is to show how the Classification of Finite Simple Groups can be applied to other areas of mathematics. Some of this is joint work with Cheryl Praeger and Stephen Glasby, the remainder is joint work with Tomasz Popiel.

Friday 5 February - Sophie Huiberts (Centrum Wiskunde & Informatica)

On the Integrality Gap of Binary Integer Programs with Gaussian Data
We bound the integrality gap of binary integer programs max c^T x, Ax≤b, x∈{0,1}^n where A and c have independent Gaussian entries. By a recent breakthrough work of Dey, Dubey and Molinaro (SODA 2021), this implies that branch and bound requires n^poly(m) time on random Gaussian IP's with good probability. When m is fixed, this quantity is polynomial.

Thursday 4 February - Lap Chi Lau (University of Waterloo)

A spectral approach to network design
We present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding problems, which were studied in spectral sparsification and in discrepancy theory. We extend these results to incorporate additional non-negative linear constraints, and show that they can be used to significantly extend the scope of network design problems that can be solved. Our algorithm for spectral rounding is an iterative randomized rounding algorithm based on the regret minimization framework. We may also discuss other applications of the spectral rounding results, including weighted experimental design and additive spectral sparsification

Friday 29 January - Alp Müyesser (FU Berlin)

Rainbow factors and trees
Generalizing a conjecture of Aharoni, Joos and Kim asked the following intriguing question. Let H be a graph on m edges, and let G_i (1<=i<=m) be a sequence of m graphs on the common vertex set [n]. What is the weakest minimum degree restriction we can impose on each G_i to guarantee a rainbow copy of H? Joos and Kim answered this question when H is a Hamilton cycle or a perfect matching. We provide an asymptotic answer when H is an F-factor, or a spanning tree with maximum degree o(n/log n). This is joint work with Richard Montgomery and Yani Pehova.

Thursday 28 January - Anthony Bonato (Ryerson University)

The localization game played on graphs
Graph searching investigates combinatorial models for the detection or neutralization of an adversary’s activity on a network. One such model is the \emph{localization game}, where pursuers use distance probes to capture an invisible evader. We present new results on the \emph{localization number} of a graph, which is the minimum number of pursuers needed to capture the evader. We survey what is known and unknown for the localization number, discuss connections with the chromatic number, and give bounds on graph families such as hypercubes, incidence graphs of combinatorial designs, and Kneser graphs.

Thursday 21 January - Rahul Savani (University of Liverpool)

The Complexity of Gradient Descent
We study search problems that can be solved by performing Gradient Descent on a convex polytopal domain and show that this class is equal to the intersection of two well-known classes: PPAD and PLS. As our main underlying technical contribution, we show that computing a Karush-Kuhn-Tucker (KKT) point of a continuously differentiable function over the domain [0,1]^2 is complete for the intersection of PPAD and PLS. This is the first natural problem to be shown complete for this class. Our results also imply that the class CLS (Continuous Local Search) - which was defined by Daskalakis and Papadimitriou as a more "natural" counterpart to the intersection of PPAD and PLS and contains many interesting problems - is itself equal to the intersection of PPAD and PLS.

Joint work with: John Fearnley, Paul W. Goldberg, and Alexandros Hollender. Preprint available here.

Thursday 10 December - Marthe Bonamy (Université de Bordeaux)

Towards polynomial Chi-boundedness of graphs with no long path
There are graphs of arbitrarily high chromatic number which contain no triangle and in fact no short cycle. However, in some graph classes with enough structure, we can show that the chromatic number of the graphs is bounded by some function of their largest clique -- in other words, that class is chi-bounded. One of the first such results was by Gyarfas in 1987: for any t, the class of Pt-free graphs is chi-bounded. The corresponding function is unfortunately exponential, and it remains a major open problem whether we can replace it with a polynomial. Here, we consider a relaxation of this problem, where we compare the chromatic number with the size of the largest balanced biclique contained in the graph as a (not necessarily induced) subgraph. We show that for every t there exists a constant c such that every Pt-free graph which does not contain Kp,p as a subgraph is p^c-colourable. This is joint work with Nicolas Bousquet, Michal Pilipczuk, Pawel Rzazewski, Stéphan Thomassé and Bartosz Walczak.

Friday 4 December - Edin Husić (LSE)

Auction Algorithms for Market Equilibrium with Weak Gross Substitute Demands
We present a simple auction algorithm that obtains an approximate market equilibrium for the exchange market model with divisible goods where the demands of the agents satisfy the weak gross substitutes (WGS) property. As an application of our result, we obtain an efficient algorithm to find an approximate spending-restricted market equilibrium for WGS demands, a model that has been recently introduced as a continuous relaxation of the Nash Social Welfare problem. This is joint work with Jugal Garg and László Végh.

Thursday 3 December - Luke Postle (University of Waterloo)

Further progress towards Hadwiger's conjecture
In 1943, Hadwiger conjectured that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable. Recently, Norin, Song and I showed that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the $O(t\sqrt{\log t})$ bound. Here we show that every graph with no $K_t$ minor is $O(t (\log t)^{\beta})$-colorable for every $\beta > 0$; more specifically, they are $O(t (\log \log t)^{6})$-colorable.

Friday 27 November - Domenico Mergoni (LSE)

About the pentagon conjecture
The Pentagon Conjecture states that every cubic graph of sufficiently high girth admits a homomorphism to the cycle of length 5. We exploit the study of this problem to introduce some interesting approaches for this kind of task. We then use the obtained tools to approach some approximations of the Pentagon Problem.

Thursday 26 November - Liana Yepremyan (LSE)

Ryser's conjecture and more
A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser, Brualdi and Stein from 60s which says that every Latin square of order $n\times n$ contains a transversal of order $n-1$. A closely related problem is 40 year old conjecture of Brouwer that every Steiner triple system of order $n$ contains a matching of size $(n-4)/3$. The third problem we'd like to mention asks how many distinct symbols in Latin arrays suffice to guarantee a full transversal? In this talk we discuss a novel approach to attack these problems. Joint work with Peter Keevash, Alexey Pokrovskiy and Benny Sudakov.

Friday 20 November - Chhaya Trehan (LSE)

Constructing Near-Additive Spanners in Dynamic Streams
Graph spanners are a fundamental and well-studied combinatorial construct with numerous applications. They are particularly useful for computing approximately shortest paths, routing schemes and distance oracles. Given a pair of parameters alpha >=1, \beta >= 0, a spanning subgraph H of an unweighted undirected graph G is called an (\alpha, \beta)-spanner of G if for every pair of vertices (u,v), d_H (u,v) <= \alpha . d_G(u,v) + \beta, where d_G(u,v) and d_H(u,v) stand for distances between u and v in G and H respectively. Elkin and Peleg proved the existence and constructibility of sparse spanners for which the multiplicative term \alpha can be arbitrarily close to 1. Such spanners are called near-additive spanners. Near-additive spanners preserve large distances much more faithfully than the more traditional multiplicative spanners. Multiple algorithms have been devised for the efficient construction of near-additive sparse spanners in sequential, distributed and (static) streaming models of computation. In the streaming model of computation, the vertex set of the input graph is known to the algorithm and the edge set is revealed one at a time. In the dynamic streaming or turnstile setting, edges can be added as well as removed as the stream progresses. We present the first dynamic-streaming algorithms for constructing near-additive spanners. Our algorithm outputs a near-additive spanner with the same stretch and size as the state of the art algorithm due to Elkin and Neiman. This is joint work with Michael Elkin of BGU, Israel.

Thursday 19 November - Matoula Kotsialou (LSE)

Incentivising Participation in Liquid Democracy with Breadth-First Delegation
Liquid democracy allows members of an electorate to either directly vote over alternatives, or delegate their voting rights to someone they trust. Most of the liquid democracy literature and implementations allow each voter to nominate only one delegate per election. However, if that delegate abstains, the voting rights assigned to her are left unused. To minimise the number of unused delegations, it has been suggested that each voter should declare a personal ranking over voters she trusts. We show that even if personal rankings over voters are declared, the standard delegation method of liquid democracy remains problematic. More specifically, we show that whenpersonalrankings over voters are declared, it could be undesirable to receive delegated voting rights, which is contrary to what liquid democracy fundamentally relies on. To solve this issue, we propose a new method to delegate voting rights in an election, calledbreadth-first delegation. Additionally, the proposed method prioritises assigning voting rights to individuals closely connected to the voters who delegate.

This is joint work with Luke Riley.

Friday 13 November - Nóra Frankl (LSE)

VC-saturated set systems
A family of sets is d-saturated, if it has VC-dimension d and adding any new set to the family increases the VC-dimension. We study the minimum cardinality of a d-saturated family on a ground set of size n. For d=1 this minimum is n+1, which is the same as the Sauer-Shelah bound for the maximum cardinality of a family of VC-dimension 1. For d>1 we find upper bounds that do not depend on n, only on d.

Joint work with Sergei Kiselev, Andrey Kupavskii and Balázs Patkós.

Thursday 12 November - Johannes Ruf (LSE)

Hedging with linear regressions and neural networks
We study the use of neural networks as nonparametric estimation tools for the hedging of options. To this end, we design a network, named HedgeNet, that directly outputs a hedging strategy given relevant features as input. This network is trained to minimise the hedging error instead of the pricing error. Applied to end-of-day and tick prices of S&P 500 and Euro Stoxx 50 options, the network is able to reduce the mean squared hedging error of the Black-Scholes benchmark significantly.
We illustrate, however, that a similar benefit arises by a simple linear regression model that incorporates the leverage effect. Finally, we argue that outperformance of neural networks previously reported in the literature is most likely due to a lack of data hygiene. In particular, data leakage is sometimes unnecessarily introduced by a faulty training/test data split, possibly along with an additional ‘tagging’ of data.

https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3580132

https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3486363

(Joint work with Weiguan Wang)

Thursday 5 November - Neil Olver (LSE)

Intersecting multiple matroids via iterative refinement
A classical result by Edmonds says that given two matroids on the same ground set, a set of maximum weight that is independent in both matroids can be found in polynomial time. This is an important generalization of maximum weight bipartite matching. It is also well-known that the problem becomes NP-hard once there are more than two matroids involved.
Here we show how to obtain a factor 2 approximation for three matroids, based on the natural LP relaxation. Previously, a 2+epsilon approximation algorithm was known for any epsilon > 0, using local search methods, and there was no bound better than 3 on the integrality gap of the natural relaxation. Our approach is based on iterative routing, and introduces a new ingredient that we call "iterative refinement"

(Joint work with André Linhares, Chaitanya Swamy and Rico Zenklusen).

Friday 30 October - Amedeo Sgueglia (LSE)

Clique factors in randomly perturbed graphs
We study the model of randomly perturbed dense graphs, which is the union of any n-vertex graph G_α with minimum degree α and the binomial random graph G(n,p). In this talk, we shall examine in detail one of the central question in this area: to determine when G_α ∪ G(n,p) contains clique factors, i.e. spanning subgraphs consisting of vertex disjoint copies of the complete graph K_k. We offer several new sharp and stability results. This is joint work with Julia Böttcher, Olaf Parczyk, and Jozef Skokan.

Thursday 29 October - Amitabh Basu (Johns Hopkins University)

Concrete complexity bounds for optimizing over integers
We discuss the complexity of the two main ingredients in integer optimization algorithms: cutting planes and branch-and-bound. We prove upper and lower bounds on the efficiency of these algorithms, when efficiency is measured in terms of complexity of the LPs that are solved. More precisely, we focus on the sparsity of the LPs and the number of LPs as measures of complexity. We also give general conditions under which combining branching and cutting into a branch-and-cut algorithm can do exponentially better than pure cutting planes or pure branch-and-bound. Time permitting, some connections to mathematical logic and proof complexity will be discussed.

Friday 23 October - Ruilan Wang (LSE)

Identically self-blocking clutters
A clutter is identically self-blocking (ISBC) if it is equal to its blocker. It is proved by Abdi, Cornuéjols and Lee that every nontrivial identically self-blocking clutter is non-ideal. However the proof for this result is rather mysterious, which does not reveal much about the extreme points of the underlying polyhedron associated with the clutter. A minor characterisation conjecture for non-trivial ISBC was therefore proposed in the same paper by Abdi et al., which would be a strengthening of the above mentioned result. In this talk we will look at results on proving some special cases of this conjecture. Along the way, we will also discover an infinite family of ISBC arising from the clutter of st-T-joins and the clutter odd st-walks.

Thursday 22 October - Willemien Kets (University of Oxford)

How (Not) To Eat a Hot Potato
We study a matching problem where players are repeatedly assigned tasks. There are frictions in the matching process: players may be matched with undesirable tasks (``hot potatoes'') even if more attractive tasks (``sweet potatoes'') are available. There is a tradeoff between waiting for sweet potatoes and reducing matching frictions by accepting hot potatoes. Under the optimal mechanism, players accept hot potatoes as long as the relative cost of doing so is not too high. In decentralized settings, externalities and strategic complementarities can lead to welfare loss. We quantify the welfare gain of centralization, which can be substantial even when players are arbitrarily patient.

Friday 16 October - Johannes Brustle (LSE)

Robust Auctions and Uniform Convergence
Our goal is to make progress towards learning auctions from limited access to value distributions. In this setting, we know that the VC dimension cannot be used to efficiently obtain the uniform convergence property with respect to the empirical distribution. In fact a more refined tool, the Rademacher Complexity, also requires an exponential number of sample points in the dimension to satisfy uniform convergence. However, given access to approximations of the true value distributions, we still manage to construct robust auctions that are oblivious to the true distribution, yet yield close to optimal revenue.

Thursday 15 October - Ben Moseley (Carnegie Mellon University)

Combinatorial Optimization Augmented with Machine Learning
Combinatorial optimization often focuses on optimizing for the worst-case. However, the best algorithm to use depends on the "relative inputs", which is application specific and often does not have a formal definition.

The talk gives a new theoretical model for designing algorithms that are tailored to inputs for the application at hand. In the model, learning is performed on past problem instances to make predictions on future instances. These predictions are incorporated into the design and analysis of the algorithm. The predictions can be used to achieve "instance-optimal" algorithm design when the predictions are accurate and the algorithm's performance gracefully degrades when there is an error in the prediction.
The talk will apply this framework to applications in online algorithm design and give algorithms with theoretical performance that goes beyond worst-case analysis. The majority of the talk will focus on load balancing in the restricted assignment machine scheduling model.

Friday 9 October - Zhuan Khye Koh (LSE)

A Strongly Polynomial Label-Correcting Algorithm for Linear Systems with Two Variables per Inequality
In this talk, I will present a strongly polynomial label-correcting algorithm for solving the feasibility of linear systems with two variables per inequality. The algorithm is based on the Newton–Dinkelbach method for fractional combinatorial optimization, and extends previous work of Madani (2002). The key technical idea is a new analysis of the Newton-Dinkelbach method exploiting gauge symmetries of the algorithm. This also leads to an acceleration of the method for general fractional combinatorial optimization problems. Based on joint work with Bento Natura and László Végh.

Thursday 1 October - Maria Chudnovsky (Princeton University)

Induced subgraphs and tree decompositions
Tree decompositions are a powerful tool in structural graph theory, that is traditionally used in the context of forbidden graph minors. Connecting tree decompositions and forbidden induced subgraphs has so far remained out of reach. Recently we obtained several results in this direction; the talk will be a survey of these results.

Seminar and PhD Seminar on Combinatorics, Games and Optimisation:

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