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 17 October - Anurag Bishnoi (FU Berlin)
Venue: NAB.2.16 from 14:00 - 15:30

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 31 October - Hervé Moulin (University of Glasgow)
Venue: NAB.2.16 from 14:00 - 15:30

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.

Thursday 7 November - Miquel Oliu-Barton (Université Paris-Dauphine)
Venue: NAB.2.16 from 14:00 - 15:30

Title and abstract TBC

Wednesday 13 November - Gyorgy Turan (UIC)
Venue: 32L.LG.14 from 15:30 - 17:00

Title and abstract TBC

Thursday 14 November - Eliza Jablonska (University of Cracow)
Venue: NAB.2.16 from 14:00 - 15:30

Title and abstract TBC

Previous seminars in the series:

Michaelmas Term

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