Below you'll find the programme for the Seminar on Combinatorics, Games and Optimisation (a joining together of the former Seminar on Discrete Mathematics and Game Theory and the former Seminar on Operations Research).
This seminar series covers many of the research areas in the Department: discrete mathematics, algorithms, game theory and operational research.
Unless stated below, this Seminar normally takes place:
Questions, suggestions, etc., about the seminar can be forwarded to the seminar administrator, by sending an e-mail to: seminar@maths.lse.ac.uk.
Upcoming Speakers:
Thursday 28 March - Marcin Jurdzinski (University of Warwick)
Venue: 32L.G.08 from 14:00 - 15:30
Universal trees and quasi-polynomial bounds for parity games
Several distinct techniques have been proposed to solve parity games in quasi-polynomial time since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures, and register games. We argue that all those techniques can be viewed as instances of the separation approach to solving parity games---a key component of which is constructing an automaton that separates languages of words encoding plays that are decisively won by either of the two players---thus establishing a single model that unifies the recent approaches to solving parity games efficiently.
Our main technical results are the nearly matching quasi-polynomial upper and lower bounds on the sizes of all separating automata. In particular, the lower bound forms a barrier that the existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games.We obtain our main results by introducing and studying universal ordered trees, a combinatorial object that may be of independent interest. Firstly, we establish the nearly matching quasi-polynomial upper and lower bounds on the size of smallest universal trees. Then we prove that the sizes of the smallest separating automata and of the smallest universal trees coincide---and hence both are quasi-polynomial---by showing how to turn universal as trees into separating automata, and that there is a universal tree hiding in the states of every separating automaton.
The talk is based on joint work with Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Ranko Lazić, and Paweł Parys.
Previous seminars in the series:
Lent Term 2019
Thursday 21 March - Adrian Mathias
Flutters and chameleons
Let K be the collection of infinite sets of natural numbers. A colouring c of K with a finite number of colours is Ramsey if for some infinite A in K and every infinite subset B of A, c(B) = c(A). A non-Ramsey colouring is one for which no such A exists.
Solovay in a famous paper published in 1970 used a strongly inaccessible cardinal to construct a model of ZF + DC in which these principles hold which contradict AC:
LM: every set of real numbers is Lebesgue measurable;
PB: every set of real numbers has the property of Baire;
UP: every uncountable set of real numbers has a perfect subset.
Two other principles to be considered are
RAM: all colourings are Ramsey
NoMAD: there is no maximal infinite family of pairwise almost disjoint infinite sets of natural numbers.
The speaker showed in 1968 that in Solovay's model, RAM holds, and in 1969 that if one started from a Mahlo cardinal, NoMAD would hold in the corresponding Solovay model. It is natural to ask whether these large cardinals are necessary; the inaccessible is necessary for UP (Specker) and LM (Shelah) but not for PB (Shelah).
More recently Toernquist has shown that NoMAD holds in Solovay's original model, and Shelah and Horowitz have extended his work to show that even that inaccessible is unnecessary to get a model of NoMAD. But it has been open for fifty years whether RAM requires an inaccessible.
This talk will be chiefly about flutters and chameleons, which are non-Ramsey sets with elegant properties, constructed using weak forms of AC; surprisingly their existence has been found to follow from various Pareto principles of mathematical economics.
Wednesday 20 March - Davi Silva (Cologne)
Stronger transference principles: preserving more structure
Transference principles (also called dense model theorems) are results which allow us to transfer some combinatorial theorems from the usual positive-density setting to the very sparse setting, provided the sparse objects satisfy some mild boundedness conditions.
In this talk I will give an overview of these results and the main ideas and concepts behind them. I will then explain in which way they can be made stronger, and give some preliminary results obtained in this direction.
Thursday 14 March - Jugal Garg (ISE)
A Strongly Polynomial Algorithm for Linear Exchange Markets
In this talk, I will present the first strongly polynomial algorithm for computing an equilibrium in exchange markets with linear utilities. The exchange market model has been extensively studied since its introduction by Walras in 1874. This problem has a non-separable convex flow formulation and the property that we can find an equilibrium in strongly polynomial time given its support, i.e., the flow variables which are non-zero. Using a variant of Duan and Mehlhorn (DM) algorithm, we gradually reveal new variables that are in the support of every equilibrium. We show that a new variable can be revealed in strongly polynomial time if we start the DM algorithm with the best possible solution corresponding to the current revealed set. Finding the best solution can be reduced to solving a linear program (LP). Even though we are unable to solve this LP in strongly polynomial time, we show that it can be approximated by a simpler LP with two variables per inequality that is solvable in strongly polynomial time and it turns out to be good enough to make the overall algorithm run in strongly polynomial time. This is based on joint work with Laci Vegh.
Thursday 7 March - Simone Cerreia Vioglio (Bocconi)
Robust Opinion Aggregation and its Dynamics
We consider a robustification of the DeGroot's linear model of social learning. By relaxing the assumption of quadratic utility of the agents, we obtain an opinion aggregator that is normalized, monotone, and translation invariant. We directly link these properties to natural conditions of the microfoundation. In addition to the less demanding assumptions on the payoff function of the agents, the opinion aggregator allows for several economically relevant patterns ruled out by the more restrictive linear model. For instance, agents can feature homophily, dislike (or attraction) for extreme opinions as well as discard information obtained from sources that are perceived as redundant. We also show that under these weaker assumptions is still possible to explore the standard questions addressed by the linear model, such as convergence of limit opinions, and the properties of consensus and wisdom for this limit.
Joint work with R. Corrao (MIT) and G. Lanzani (MIT).
Wednesday 6 March - Dani Dorfman (TAU)
A faster deterministic exponential time algorithm for Energy Games and Mean Payoff Games
We present an improved exponential time algorithm for Energy Games, and hence also for Mean Payoff Games. The running time of the new algorithm is O( min( m*n*W, n*m* 2^(n/2)* logW), where n is the number of vertices, m is the number of edges, and when the edge weights are integers of absolute value at most W. The new algorithm is also a pseudopolynomial time algorithm, matching the O(mnW) running time of the fastest known pseudopolynomial time algorithm of Brim et al. on which it is based.It is currently the fastest deterministic algorithm for Energy Games and Mean Payoff Games when 2^(n/2})*n < W < 2^(2^(n/2)). The new algorithm is obtained by introducing a technique of forecasting repetitive actions performed by the algorithm of Brim et al., along with the use of an edge-weight scaling technique.
Thursday 28 February - Yani Pehova (Warwick)
Tilings in graphs with sublinear independence number
A classical theorem of Hajnal and Szemeredi states that if an n-vertex graph G has minimum degree at least (1-1/r)n, then it contains a K_r-factor (that is, n/r vertex-disjoint copies of K_r), provided r divides |G|. Extremal examples for this result, however, contain large independent sets. Forbidding these extremal structures is likely to decrease the minimum degree condition required to force a K_r-factor, and indeed a result of Balogh, Molla and Sharifzadeh shows that if the independence number of G is sublinear, then minimum degree slightly above n/2 suffices to force a triangle-factor. We present an extension of this result for general K_r-factors and graphs of sublinear k-independence number (that is, whose largest K_k-free subsets have sublinear size). Our proof uses the absorbing method, and our absorber construction can be applied in other settings. For example, we are able to recover a recent result of Balogh, Treglown and Wagner on H-factors in dense randomly perturbed graphs. This is joint work with Rajko Nenadov.
Wednesday 27 February - Georg Loho (LSE)
Algorithmic questions around tropical Carathéodory
Since Imre Bárány found the colourful version of Carathéodory's theorem in 1982, many combinatorial generalizations and algorithmic variations have been considered. This ranges from variations of the colour classes to different notions of convexity. We take a closer look at the max-plus or 'tropical' convexity version of this theorem. We provide new insights on colourful linear programming and matroid generalizations from a tropical point of view, by considering additional sign informations. The difficulty of the arising algorithmic questions ranges from greedily solvable to NP-hard.
Thursday 14 February - Cécile Mailler (Bath)
The monkey walk: a random walk with random reinforced relocations and fading memory.
In this joint work with Gerónimo Uribe-Bravo, we prove and extend results from the physics literature about a random walk with random reinforced relocations. The "walker" evolves in $\mathbb Z^d$ or $\mathbb R^d$ according to a Markov process, except at some random jump-times, where it chooses a time uniformly at random in its past, and instatnly jumps to the position it was at that random time. This walk is by definition non-Markovian, since the walker needs to remember all its past.
Under moment conditions on the inter-jump-times, and provided that the underlying Markov process verifies a distributional limit theorem, we show a distributional limit theorem for the position of the walker at large time. The proof relies on exploiting the branching structure of this random walk with random relocations; we are able to extend the model further by allowing the memory of the walker to decay with time.
Wednesday 13 February - Stefano Leonardi (Sapienza Università di Roma)
Algorithmic Mechanism Design for Two-sided Markets
Mechanism design for one-sided markets is an area of extensive research in economics and, since more than a decade, in computer science as well. Two-sided markets, on the other hand, have not received the same attention despite the many applications to Internet advertisement and to the sharing economy.
In two-sided markets, both buyers and sellers act strategically. An ideal goal in two-sided markets is to maximize the social welfare of buyers and sellers with individually rational (IR), incentive compatible (IC) and budget-balanced mechanisms (BB), which requires that the mechanism does not subsidize the market or make an arbitrary profit from the exchange. Unfortunately, Myerson and Satterthwaite proved in 1983 that this goal cannot be achieved even in the bayesian setting and for the simple case of only one buyer and one seller.
In this talk, I’ll discuss meaningful trade-offs and algorithmic approximations of the above requirements by presenting several recent results and some challenging open problems.
Thursday 7 February - Carla Groenland (University of Oxford)
Size reconstructability of graphs
The deck of a graph $G$ is given by the multiset $\{G-v:v\in V(G)\}$ of (unlabelled) subgraphs, which are called cards. The graph reconstruction conjecture states that no two non-isomorphic graphs (on at least three vertices) can have the same deck. The number of edges of a graph can be computed from its deck and Brown and Fenner show that the size of $G$ can be reconstructed as well after any 2 cards have been removed from the deck (for $n\geq 29$). We show that for sufficiently large $n$, the number of edges can be computed whenever at most $\frac1{20}\sqrt{n}$ cards are missing. I will talk about the background of the problem, the main ideas of the proof and my favourite open problems in the area.Joint work with Hannah Guggiari and Alex Scott.
Wednesday 30 January - Victor Verdugo (LSE)
Breaking symmetries to rescue Sum of Squares
The Sum of Squares (SoS) hierarchy gives an automatized technique to create a family of increasingly tight convex relaxations for binary programs. There are several problems for which a constant number of rounds of the hierarchy give integrality gaps matching the best known approximation algorithm. In many other, however, ad-hoc techniques give significantly better approximation ratios. Notably, the lower bounds instances, in many cases, are invariant under the action of a large permutation group. In the first part of the talk I'll provide some background about polynomial optimization and the SoS approach. In the second part, I'll show how symmetries can be broken in order to obtain arbitrarily good approximation ratios for the case of makespan scheduling. On the negative side, SoS fails when symmetries are not broken, and I'll highlight the ideas behind the lower bound.
Wednesday 23 January - Peter Allen (LSE)
Optimal packings of sparse graphs
I will describe (another) randomised approach to finding
perfect packings of sparse graphs in quasirandom or complete host
graphs. The packing algorithm is simple and I will describe it
completely; the analysis is not so simple.
In particular, we prove that Ringel's Conjecture and the Tree Packing
Conjecture are true for almost all trees (or sequences of trees,
respectively).
This is joint work with Julia Boettcher, Dennis Clemens, Jan Hladky,
Diana Piguet and Anusch Taraz.
Michaelmas Term 2018
Thursday 13 December - Vera Traub (Hausdorff Centre for Mathematics)
Beating the integrality ratio for s-t-tours in graphs
Among various variants of the traveling salesman problem, the s-t-path graph TSP has the special feature that we know the exact integrality ratio, 3/2, and an approximation algorithm matching this ratio. In this work, we go below this threshold: we devise a polynomial-time algorithm for the s-t-path graph TSP with approximation ratio 1.497.
Our algorithm can be viewed as a refinement of the 3/2-approximation algorithm by Sebő and Vygen [2014], but we introduce several completely new techniques. These include a new type of ear-decomposition, an enhanced ear induction that reveals a novel connection to matroid union, a stronger lower bound, and a reduction of general instances to instances in which s and t have small distance (which works for general metrics).
This is joint work with Jens Vygen.
Wednesday 12 December - Noam Nisan (Hebrew University of Jerusalem)
The Communication Complexity of Cake-Cutting
This talk concerns the well-studied model of "cake-cutting" for studying questions regarding notions of fair division of resources. We focus on discrete versions rather than using infinite-precision real values, specifically, focusing on the communication complexity. Using general discrete simulations of classical infinite-precision protocols (Robertson-Webb and moving-knife), we roughly partition the various fair-allocation problems into 3 classes: "easy" (constant number of rounds of logarithmic many bits), "medium" (poly-log total communication), and "hard".
Our main technical result concerns two of the "medium" problems (perfect allocation for 2 players and equitable allocation for any number of players) which we prove are not in the "easy" class. Our main open problem is to separate the "hard" from the "medium" classes.
Joint work with Simina Brânzei
Thursday 6 December - Andrés Cristi (Universidad de Chile)
A Near Optimal Mechanism for Energy Aware Scheduling
Consider a cloud server, where clients can submit jobs for processing. The quality of service that each agent receives is given by a private non-decreasing function of the completion time of her job. The server has to process the jobs and charge each agent while trying to optimize the social cost that is defined as the energy expenditure plus the sum of the values of the internal cost functions. The server operator would like to design a mechanism in order to optimize this objective, which ideally is computationally tractable, charges the users “fairly” and the induced game has an equilibrium. We present a mechanism that combines the aforementioned properties with a constant Price of Anarchy. An interesting feature of our mechanism is that it is indirect: each user needs only to declare an upper bound on the completion time of her job, and not the cost function.
This is joint work with Antonios Antoniadis.
Friday 30 November - Benny Sudakov (ETH)
Subgraph statistics
Consider integers $k,\ell$ such that $0\le \ell \le \binom{k}2$. Given a large graph $G$, what is the fraction of $k$-vertex subsets of $G$ which span exactly $\ell$ edges? When $G$ is empty or complete, and $\ell$ is zero or $\binom k 2$, this fraction can be exactly 1. On the other hand if $\ell$ is not one these extreme values, then by Ramsey's theorem, this fraction is strictly smaller than 1.
The systematic study of the above question was recently initiated by Alon, Hefetz, Krivelevich and Tyomkyn who proposed several natural conjectures. In this talk we discuss a theorem which proves one of their conjectures and implies an 0asymptotic version of another. We also make some first steps towards analogous question for hypergraphs. Our proofs involve some Ramsey-type arguments, and a number of different probabilistic tools, such as polynomial anticoncentration inequalities and hypercontractivity.
Joint work with M. Kwan and T. Tran
Wednesday 28 November - Guillem Perarnau Llobet (Birmingham)
Efficient sampling of random colorings
A well-known conjecture in computer science and statistical physics is that Glauber dynamics on the set of k-colorings of a graph G on n vertices with maximum degree \Delta is rapidly mixing for k \ge \Delta+2. In 1999, Vigoda showed rapid mixing of flip dynamics with certain flip parameters on the set of proper k-colorings for k > (11/6)\Delta, implying rapid mixing for Glauber dynamics. In this paper, we obtain the first improvement beyond the (11/6)\Delta barrier for general graphs by showing rapid mixing for k > (11/6 - \eta)\Delta for some positive constant \eta. The key to our proof is combining path coupling with a new kind of metric that incorporates a count of the extremal configurations of the chain. Additionally, our results extend to list coloring, a widely studied generalization of coloring. Combined, these results answer two open questions from Frieze and Vigoda’s 2007 survey paper on Glauber dynamics for colorings. (Joint work with Michelle Delcourt and Luke Postle)
Wednesday 21 November - Iannis Caragiannis (University of Patras)
Fairness in allocation problems
In this talk, we will present variations of the problem of allocating indivisible goods to agents with additive valuations for the goods. We will define basic fairness concepts such as proportionality and envy-freeness and will discuss their properties. Next, we will focus on allocations of maximum Nash welfare, and we will explain how they guarantee approximate notions of envy-freeness. Finally, we will define new fairness concepts that are related to the level of awareness of the agents for the allocation and to their social relations. We will present examples and many open problems. No advanced or special mathematical background is needed to follow the talk.
Thursday 15 November - Tibor Szabó (Freie Universität Berlin)
Optimality of the uniform random strategy
The concept of biased Maker-Breaker games, introduced by Chvátal and Erd\H os, is a central topic in the field of positional games, with deep connections to the theory of random structures. For any given hypergraph H the main questions is to determine the smallest bias q(H) that allows Breaker to force that Maker ends up with an independent set of H. Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies a couple of natural ‘container-type’ regularity conditions about the degree of subsets of its vertices. This will enable us to derive a hypergraph generalization of the H-building games, studied for graphs by Bednarska and Luczak.
Furthermore, we investigate the biased version of generalizations of the van der Waerden games introduced by Beck. We refer to these generalizations as Rado games and determine their threshold bias up to constant factors by applying our general criteria. We find it quite remarkable that a purely game theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, when the generalizations to hypergraphs in the analogous setup of sparse random discrete structures are usually quite challenging.
Wednesday 14 November - Matthias Englert (Warwick)
Polylogarithmic Guarantees for Generalized Reordering Buffer Management
In the Generalized Reordering Buffer Management Problem (GRBM) a sequence of items located in a metric space arrive online, and have to be processed by a set of k servers moving within the space. In a single step the first b still unprocessed items from the sequence are accessible, and a scheduling strategy has to select an item and a server.
Then the chosen item is processed by moving the chosen server to its location. The goal is to process all items while minimizing the total distance travelled by the servers.This problem was introduced by Chan et al. (TCS'12) and has been subsequently studied in an online setting by Azar et al. (STACS'14). The problem is a natural generalization of two very well-studied problems: the k-server problem for b=1 and the Reordering Buffer Management Problem (RBM) for k=1. We consider the GRBM problem on a uniform metric in the online version.
We show how to obtain a competitive ratio of O(log k(log k+loglog b)) for this problem. This is a significant improvement in the dependency on b compared to the previous best bound of O(sqrt(b) log k), and is asymptotically optimal for constant k.
Thursday 8 November - Maryam Sharifzadeh (Warwick)
Number of maximal sum-free subsets of integers and abelian groups.
A set $S$ is sum-free if it does not contain a triple $x,y,z$ such that $x+y=z$ (note $x,y$ may not necessarily be distinct). We say that $S\subseteq [n]$ is a maximal sum-free subset of $[n]$ if it is sum-free and it is not properly contained in another sum-free subset of $[n]$. Cameron and Erd\H{o}s asked whether the number of maximal sum-free subsets of $[n]$ is much smaller than the number of sum-free sets. They also gave a lower bound of $2^{\lfloor n/4 \rfloor }$ for the number of maximal sum-free sets. Together with J\'ozsef Balogh, Hong Liu, and Andrew Treglown, we give an exact solution to the problem: For each $1\leq i \leq 4$, there is a constant $C_i$ such that, given any $n\equiv i \mod 4$, $[n]$ contains $(C_i+o(1)) 2^{n/4}$ maximal sum-free sets. In this talk, I will outline the ideas and techniques used in the proof. I will also discuss some new results on the number of maximal sum-free sets in abelian groups, which are joint work with Hong Liu.
Wednesday 7 November - Brendan Murphy (Bristol)
Solymosi's conjecture for rich lines in general position
We give an explicit construction that disproves a conjecture of Solymosi on the number of lines in general position that contain a near maximal number of points of a Cartesian product set. We will explain how this problem is connected to the sum-product problem, and show why Solymosi's conjecture is plausible. The counter-example we give is motivated by related questions in group theory, and is rather different from the usual examples in arithmetic combinatorics.
Thursday 1 November - Kristof Berczi (Eotvos University)
Improving the integrality gap for multiway cut
In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal so that the total weight of the edges crossing the partition is minimized. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrák while the best known inapproximability factor is 1.2 due to Angelidakis, Makarychev and Manurangsi.
In this talk we show how to improve on the lower bound by constructing an integrality gap instance for the CKR relaxation. A technical challenge in improving the gap has been the lack of geometric tools to understand higher-dimensional simplices. We analyze the gap of the instance by viewing it as a convex combination of 2-dimensional instances and a uniform 3-dimensional instance. One of the byproducts from our proof technique is a generalization of a result on Sperner admissible labelings due to Mirzakhani and Vondrák.
Joint work with Karthakeyan Chanrdasekaran, Tamás Király and Vivek Madan.
Wednesday 31 October - Ágnes Cseh (IE CERS HAS)
The complexity of cake cutting with unequal share
An unceasing problem of our prevailing society is the fair division of goods. The problem of proportional cake cutting focuses on dividing a heterogeneous and divisible resource, the cake, among n players who value pieces according to their own measure function. The goal is to assign each player a not necessarily connected part of the cake that the player evaluates at least as much as her proportional share.
We investigate the problem of proportional division with unequal shares, where each player is entitled to receive a predetermined portion of the cake. Our main contribution is threefold. First we present a protocol for integer demands that delivers a proportional solution in fewer queries than all known algorithms. Then we show that our protocol is asymptotically the fastest possible by giving a matching lower bound. Finally, we turn to irrational demands and solve the proportional cake cutting problem by reducing it to the same problem with integer demands only. All results remain valid in a highly general cake cutting model, which can be of independent interest.
Joint work with Tamás Fleiner. The paper received the best paper award at SAGT 2018.
Thursday 25 October - Bruce Reed (McGill)
ω, Δ, and x
We consider three graph invariants and the relationship between them. The first is the size of the largest clique in a graph G, denoted ω(G). The second is the maximum degree of a vertex of G, denoted Δ(G). The third is the chromatic number of G, denoted x(G).Trivially, ω(G)≤ x(G). Greedy colouring shows x(G)≤ Δ(G)+1. So ω(G)≤ x(G)≤ Δ(G)+1. We discuss a conjecture which states that x lies in the lower half of this range. We also show that when x is sufficiently close to Δ it is determined by a small subgraph and can be computed in polynomial time.
Wednesday 24 October - Varun Kanade (University of Oxford)
Hierarchical clustering: Objectives & Algorithms
Hierarchical clustering is a recursive partitioning of a dataset into clusters at an increasingly finer granularity. Hierarchical clustering has mostly been studied in procedural terms, i.e., a hierarchical cluster tree is obtained using certain bottom-up (agglomerative) or top-down (divisive) heuristics, rather than finding a hierarchical cluster tree as the solution obtained by optimizing some suitable objective. Dasgupta (2016) identified this as a reason why the theory of hierarchical clustering lagged behind that of flat clustering and proposed an objective function. In this talk, we will take an axiomatic approach to identifying suitable objective functions for hierarchical clustering. We will also describe a new random-graph model with a planted hierarchy. New and existing algorithms and their performance in theory and on some preliminary experiments will be discussed.
Based on joint work with Vincent Cohen-Addad, Claire Mathieu and Frederik Mallmann-Trenn.
Thursday 18 October - Leonidas Pitsoulis (Aristotle University of Thessaloniki)
Decomposition of signed-graphic matroids
In this seminar we will present a decomposition theory for the class of signed graphic matroids which are representable either in GF(2) or GF(4). The proposed decomposition differs from previous decomposition results on matroids that have appeared in the literature in the sense that it is not solely based on k-sums such as the decomposition of regular matroids, but also on an operation called star composition. A sketch of the resulting recognition algorithms as well as an excluded minor characterization of the building blocks of the aforementioned decomposition will also be presented.
2018, 2017, 2016
The Seminar on Combinatorics, Games and Optimisation started in 2016. It is a combination of two previous seminar series:
Seminar on Discrete Mathematics and Game Theory:
2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003
Seminar on Operations Research:
2016, 2015, 2014, 2013, 2012, 2011, 2010