BannerDM1400x300

Seminar on Combinatorics, Games and Optimisation

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

Upcoming Speakers:

Thursday 12 December - Spyros Angelopoulos (CNRS and Sorbonne University)
Venue: NAB.2.16 from 14:00 - 15:30

Online Computation with Untrusted Advice
The advice model of online computation captures the setting in which an online algorithm is given some partial information concerning the request sequence. This paradigm allows to establish tradeoffs between the amount of this additional information and the performance of the online algorithm. However, unlike real life in which advice is a recommendation that we can choose to follow or to ignore based on trustworthiness, in the current advice model, the online algorithm typically treats it as infallible. This means that if the advice is corrupt or, worse, if it comes from a malicious source, the algorithm may perform poorly. In this work, we study online computation in a setting in which the advice is provided by an untrusted source. Our objective is to quantify the impact of untrusted advice so as to design and analyze robust online algorithms that are resilient and perform well even when the advice is generated in a malicious, adversarial manner. We show how the new paradigm can be applied to well-studied online problems such as ski rental, online bidding, bin packing, and list update.

Joint work with Christoph Dürr, Shendan Jin, Shahin Kamali and Marc Renault.

Previous seminars in the series:

Michaelmas Term

Thursday 5 December - Victor Verdugo (LSE)

Prophet Inequalities and Mechanism Design
In many situations finding the optimal revenue pricing policy requires to solve a hard optimisation problem. Posted price mechanism are simple and efficiently implementable. In this talk I'll show the connection between this type of mechanisms and optimal stopping rules for online selection problems, and how the guarantees from one problem to the other are preserved.

Thursday 28 November - László Végh (LSE)

An improved constant-factor approximation algorithm for the asymmetric travelling salesman problem
In this talk, I will speak about a recent result by Vera Traub and Jens Vygen. For the asymmetric variant of the classical travelling salesman problem, the first constant-factor approximation algorithm was given in our 2018 paper with Ola Svensson and Jakub Tarnawski. The result used a combination of combinatorial and linear programming tools, and reduced the problem to more structured special cases in a number of reduction steps.
The approximation ratio in the first version of our paper was 5500, which we later improved to 506. The new paper by Traub and Vygen dramatically improves this to 22. Whereas they follow the same overall strategy as our previous paper, they manage to find substantial simplifications in the chain of reductions that not only improve the performance guarantee, but also make the result more accessible.

Thursday 21 November - Joonkyung Lee (Universität Hamburg)

Convex graphon parameters and graph norms
Sidorenko's conjecture states that the number of a bipartite graph $H$ in a graph~$G$ is asymptotically minimised when $G$ is a quasirandom graph. A notorious example that this conjecture remains open is the case $H=K_{5,5}\setminus C_{10}$. It has been even unknown whether this graph possesses the weakly norming property, a strictly stronger property than satisfying the conjecture.
We take a step towards understanding the graph $K_{5,5}\setminus C_{10}$ by proving that it is not weakly norming. More generally, we show that `twisted' blow-ups of cycles, which include $K_{5,5}\setminus C_{10}$ and $C_6\square K_2$, are not weakly norming. This answers two questions of Hatami, who asked whether the two graphs are weakly norming. The method relies on analysing Hessian matrices defined by graph homomorphisms, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that $K_{t,t}$ minus a perfect matching, proven to be weakly norming by Lov\'asz, is not norming for every~$t>3$. Joint work with Bjarne Sch\"ulke.

Thursday 14 November - Eliza Jablonska (University of Cracow)

On generically Haar-"small" sets in Abelian Polish groups
A subset A of an Abelian Polish group X is Haar-null (following Christensen) if there are a Borel set B covering A and a Borel probability measure m on such that m(x +B)=0 for all x in X.
Dodos proves that for every Haar-null Borel subset A of X the set of all test measures

            T(A):={m ∈ P(X)  :  m(x+A)=0 for all ∈ X}

is dense, coanalytic, and either meagre or co-meagre in the space P(X) of all probability Borel measures on X (with Lévy-Prokhorov metric).
Christensen's measure-theoretic notion has a topological analogue due to Darji: a subset A of X is Haar-meagre if there are a Borel set B covering A, a compact metric space K and a continuous function f: KX such that

             f⁻¹(B+x) is meagre in K for all ∈ X 

We prove an analogue of the Dodos theorem: for every Haar-meager Borel subset A, the set of all witness functions

            W(A):={ f ∈ C(2^{ω},X) :  f⁻¹(x+A) is meagre in 2^{ω} for all ∈ X}

is dense, coanalytic, and either meager or comeager in in the space C(2^{ω}, X) of all continuous functions f: 2^{ω} → X with the supremum metric. The first step is to show that the compact metric space K in Darji's definition can always be replaced by the Cantor cube 2^{ω}.

Wednesday 13 November - Gyorgy Turan (UIC)

Interpretability in machine learning
In many applications of machine learning,  learned models or their decisions need to be interpretable (or explainable, comprehensible). For example, `why was my credit application rejected?'.  Neural networks, for example, are typically not interpretable, while decision trees are more so.  We give a general overview of the topic, and discuss some recent projects.
The theoretical part is about efficient approximation of Bayesian networks with `interpretable' models.

Thursday 7 November - Miquel Oliu-Barton (Université Paris-Dauphine)

A Solution for Stochastic Games
Shapley (1953) introduced stochastic games in order to model dynamic interactions in which the environment changes in response to the players' behavior, and proved that finite competitive stochastic games admit a λ-discounted value for any discount rate λ. The case where λ is close to zero is of particular interest, as it corresponds to an interaction in the long run, far from opportunistic behavior. Bewley and Kohlberg (1976) proved that the λ-discounted values converge as λ goes to zero. Building on this result, Mertens and Neyman (1981) proved that finite competitive stochastic games admit a value, and that the value coincides with the limit of the λ-discounted values as λ goes to zero. Finding a tractable formula for the value of finite competitive stochastic games was a major open problem for nearly 40 years. The present contribution resolves this problem.

Joint work with Luc Attia.

Friday 1 November - Anupam Gupta (CMU)

K-way-cuts in graphs
For an undirected graph, a k-way cut is a set of edges whose deletion breaks the graph into at least k pieces. How fast can we find a minimum-weight k-way cut? And how many minimum k-way cuts can a graph have? The two problems seem to be closely linked --- in 1996 Karger and Stein showed how to find a minimum k-way cut in time approximately n^{2k-2}, and also that the number of minimum k-way cuts is at most n^{2k-2}. Both these results are not known to be tight, except for the case of k=2, that of finding graph min-cuts.
In this talk, we report on recent progress beating these bounds. We discuss how extremal bounds for set systems, when combined with other ideas, can improve on the Karger-Stein bound.

This is joint work with Euiwoong Lee (NYU) and Jason Li (CMU).

Thursday 31 October - Hervé Moulin (University of Glasgow)

Guarantees in Fair Division, under informational parsimony
Steinhaus's Diminishing Share (DS) algorithm (generalizing Divide & Choose D&C), as well as Dubins and Spanier's Moving Knife (MK) algorithm, guarantee to all participants a Fair Share of the manna (its worth at least 1/n-th of that of the whole manna) while eliciting parsimonious information from them. However DS and MK are only defined when 1. preferences are represented by additive utilities; and 2. every part of the manna to be divided is desirable to every participant (a cake), or every part is unpleasant to everybody (a chore).
Our n-person Divide & Choose rule takes care of issue 2 when utilities are additive: it requires no trimming or padding, and works for mixed manna with subjective goods and bads. It also implements the canonical approximation of the Fair Share (up to one item) when we allocate indivisible items.
Issue 1 is much deeper, it challenges us to define a Fair Share Guarantee when 1/n-th of the whole manna makes no sense. The same D&C rule implements such a bound, for very general preferences restricted by a continuity assumption but no monotonicity whatsoever. The minMax utility of an agent is that of his best share in the worst possible partition. It is lower than his Maxmin utility (that of his worst share in the best possible partition), that cannot be guaranteed to all agents.
When the manna contains only goods, or only bads, the minMax Guarantee can be improved in infinitely many ways. Our Bid & Choose rules improve upon the MK rules by fixing a benchmark value of shares, and asking agents to bid the smallest size of an acceptable share. The resulting Guarantees fall between their minMax and Maxmin.

Joint work with Anna Bogomolnaia.

Friday 25 October - Liana Yepremyan (LSE)

On the size Ramsey number of graphs with bounded degree and bounded treewidth
A graph $G$ is Ramsey for a graph $H$ if every red/blue edge-colouring of the edges of $G$ contains a monochromatic copy of $H$. We consider the following question: if $H$ has bounded treewidth, is there a `sparse' graph $G$ that is Ramsey for $H$? We show that if the maximum degree and treewidth of $H$ are bounded, then there is a graph $G$ with $O(|V(H)|)$ edges that is Ramsey for $H$. This was previously known for the smaller class of graphs $H$ with bounded bandwidth by the work of by Clemens, Jenssen, Kohayakawa, Morrison, Mota, Reding and Roberts. We actually prove a more general off-diagonal version of the above result: For graphs $H_1$ and $H_2$, the \emph{size Ramsey number} $\hat{r}(H_1, H_2)$ is the minimum number of edges in a graph $G$ such that every red/blue-colouring of the edges of $G$ contains a red copy of $H_1$ or a blue copy of $H_2$. We prove that if $H_1$ and $H_2$ both have $n$ vertices, bounded degree and bounded treewidth, then $\hat{r}(H_1, H_2)= O(n)$. 

This is joint work with Nina Kam\v{c}ev, Anita Liebenau and David Wood.

Thursday 17 October - Anurag Bishnoi (FU Berlin)

Clique-free pseudorandom graphs
One of the outstanding open problems in the theory of pseudorandom graphs is to find a construction of $K_s$-free $(n, d, \lambda)$-graphs, for $s > 3$, with $\lambda = O(\sqrt{d})$ and  the highest possible edge density of $d/n = \Theta(n^{-1/(2s - 3)})$.
For $s = 3$, there is a famous construction of Alon from 1994 that provides such a family of triangle free graphs.
For $s \geq 5$, the best known construction is due to Alon and Krivelevich from 1996 that has edge density $\Theta(n^{-1/(s - 2)})$.
Very recently, Mubayi and Verstraete have shown that a construction with edge density $\Omega(n^{-1/(s + \epsilon)})$, for any $\epsilon > 0$, would imply an improvement in the best known lower bounds on the off-diagonal Ramsey numbers $R(s, t)$, $s$ fixed and $t \rightarrow \infty$.

In this talk I will present a new construction of $K_s$-free pseudorandom graphs with an edge density  of $\Theta(n^{-1/(s - 1)})$, thus improving the Alon-Krivelevich construction but still falling short of improving the lower bounds on Ramsey numbers.

(Joint work with Ferdinand Ihringer and Valentina Pepe)

Thursday 10 October - Ahmad Abdi (LSE)

Graphs, Matroids and Clutters (talk 2)
In a series of two talks, I will try to motivate and describe my area of research, and the mathematical objects that I deal with on a daily basis. The talks will be self-contained and will only assume basic knowledge of Linear Algebra, Polyhedral Theory, and Graph Theory.

The two talks center around the following conjecture that I made together with Gerard Cornuejols and Dabeen Lee:

"Let A be a 0,1 matrix where every row has at least two 1s and the polyhedron { x>=0 : Ax >= 1 } is integral. We conjecture that the columns of A can be partitioned into 4 color classes such that every row gets two 1s with different colors. This is still open even if 4 is replaced by any universal constant."

In the first talk, I will give two other equivalent formulations of this conjecture, one being the blocking version of this conjecture, the other being the "cuboidal" version.

In the second talk, I will talk about how this conjecture extends known prominent results in Graph Theory and Matroid Theory. In particular, we will see how the conjecture extends Jaeger's 8-flow theorem, and how a variation of it extends Tutte's 4-flow conjecture.

Thursday 3 October - Ahmad Abdi (LSE)

Clutters, blockers, and cuboids (talk 1)
In a series of two talks, I will try to motivate and describe my area of research, and the mathematical objects that I deal with on a daily basis. The talks will be self-contained and will only assume basic knowledge of Linear Algebra, Polyhedral Theory, and Graph Theory.

The two talks center around the following conjecture that I made together with Gerard Cornuejols and Dabeen Lee:

"Let A be a 0,1 matrix where every row has at least two 1s and the polyhedron { x>=0 : Ax >= 1 } is integral. We conjecture that the columns of A can be partitioned into 4 color classes such that every row gets two 1s with different colors. This is still open even if 4 is replaced by any universal constant."

In the first talk, I will give two other equivalent formulations of this conjecture, one being the blocking version of this conjecture, the other being the "cuboidal" version.

In the second talk, I will talk about how this conjecture extends known prominent results in Graph Theory and Matroid Theory. In particular, we will see how the conjecture extends Jaeger's 8-flow theorem, and how a variation of it extends Tutte's 4-flow conjecture.

20192018,  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