Below you can find information about past seminars in this series from 2015. The seminars are listed in reverse chronological order, most recent first.
Friday 27 November - Tom Lidbetter (LSE)
Search games with submodular payoff functions
Suppose an element of a finite set X is chosen and a Searcher inspects the elements of the set one by one until he finds the chosen element. For a given ordering x_1,...,x_n of X, the cost paid by the Searcher to find element x_i is f({x_1,...,x_i}), where f is a non-decreasing, submodular set function. We consider the problem faced by the Searcher of choosing an ordering of X to minimise the expected cost of finding an element of X chosen according to some known probability distribution. We give some examples of this problem, including the well-known problem in scheduling theory of minimising the sum of the weighted completion times of a set of jobs with precedence constraints. The latter problem is NP-hard (and therefore so is ours), and we give a 2-approximation to the optimal search strategy, generalising the analogous result for scheduling. The approximation makes use of what may be thought of as a version of "Smith's rule" for optimal scheduling. We go on to consider a zero-sum game where a cost-maximising Hider chooses an element of X, the Searcher chooses an ordering of X and the payoff is the cost to the Searcher in finding the object. We show that any optimal mixed (randomised) strategy of the Hider must lie in a well-known object called the base polyhedron of f.
This is joint work with Robbert Fokkink.
Friday 20 November - Imre Bárány (UCL & Rényi Institute)
Small subset sums
Let B be the unit ball of a norm in the d-dimensional space and assume that V is a finite subset of B, and the sum of the vectors in V is the zero vector. A theorem of Steinitz from 1914 says that there is an ordering v_1,...,v_n of the vectors in V such that every partial sum along this ordering has norm at most 2d. In the lecture several versions and various extensions of this theorem will be explained.
Friday 13 November - R. Ravi (CMU)
***Seminar held jointly with the Operations Research Seminar Series***
Improved Approximations for Graph-TSP in Regular Graphs
A tour in a graph is a connected walk that visits every vertex at least once, and returns to the starting vertex. We describe improved approximation results for a tour with the minimum number of edges in regular graphs. En route we illustrate the main ideas used recently in designing improved approximation algorithms for graph TSP.
Friday 6 November - Matthew Jenssen (LSE) Independent sets, Matchings, and Occupancy Fractions III
This is the final instalment in the trilogy of talks on this topic, however the talk will be self-contained. Previous talks dealt with a new method for upper bounding the number of independent sets and matchings in a graph. Here we will recap the method and show how it can be used to give lower bounds as well. In particular we will reprove a famous result due to Shearer from 1983 concerning the size of independent sets in triangle-free graphs.
Friday 30 October - Bo Chen (Warwick Business School)
Price of Anarchy for Congestion Games with Stochastic Demands
We generalize the notions of user equilibrium, system optimum and price of anarchy to non-atomic congestion games with stochastic demands. In this generalized model, we extend the two bounding methods from Roughgarden and Tardos (Games and Economic Behavior, 2004) and Correa et al. (Games and Economic Behavior, 2008) to bound the price of anarchy, and compare the upper bounds we have obtained. Our results show that the price of anarchy depends not only on the class of cost functions but also demand distributions and, to some extent, the network topology. The upper bounds are tight in some special cases, including the case of deterministic demands.
Joint work with Chenlan Wang and Xuan Vinh Doan of Warwick Business School.
Friday 23 October - Barnaby Roberts (LSE)
Independent sets, Matchings, and Occupancy Fractions II
We study the matching polynomial in d-regular graphs via the monomer-dimer model of statistical physics. In particular we show that the average size of a matching drawn from the monomer-dimer model is maximised over d-regular graphs by a disjoint union of complete bipartite graphs. As a consequence we prove that these graphs also have the most matchings of any d-regular graph on a fixed number of vertices.
This is joint work with Ewan Davies, Matthew Jenssen and Will Perkins.
Friday 16 October - Benny Sudakov (ETH Zürich)
Two short stories in Extremal Combinatorics
In this talk we present variants of two classical extremal problems: estimating Ramsey numbers for cliques and Turán numbers for complete bipartite graphs. Our results (obtained jointly with Conlon and Fox) are proved by basic probabilistic arguments and answer questions of Bollobás, Erd˝os, Foucaud, Hajnal, Krivelevich and Perarnau.
Friday 9 October - Ewan Davies (LSE)
Independent sets, Matchings, and Occupancy Fractions I
We use a new technique to prove a strengthening of Jeff Kahn's theorem that disjoint unions of K_{d,d}'s maximise the number of independent sets in a bipartite d-regular graph. In probabilistic language, we show that for bipartite d-regular graphs and all λ, the occupancy fraction of the hard-core model with fugacity λ is maximised by K_{d,d}.
The method can be extended to non-bipartite graphs, applied to another model from statistical physics where the analogous result was not previously known, and used to provide lower bounds. For this talk the focus is on the background and the key idea: an optimisation problem over distributions of local random variables. My coauthors will discuss further developments in the near future.
Friday 3 July - Paul Duetting (LSE)
Mini-workshop: ‘Impact and Outreach through Posters’
Apart from presentations at workshops and conferences, presenting a poster with your research can be an efficient way to present your research both a specialised and to a broader lay audience. But just as preparing a seminar is not a trivial task, producing a poster involves some serious work as well.
In this mini-workshop I want to discuss the pros and cons of producing a poster, and what makes a good poster. I also want to survey the Different possibilities of producing a poster (from doing it in Latex to Powerpoint), and how LSE can assist you with the production of the poster.
Friday 19 June - Daniel Quiroz (LSE)
The chromatic number of exact distance graph
Given a graph G=(V,E) and a positive integer p, we define the exact distance p graph as the graph having vertex set V and, for vertices x and y in V, the edge xy if and only if the distance between x and y is exactly p (by distance we mean length of shortest path in G).
We consider the chromatic number of exact distance graphs. For p even this number is unbounded even for the class of trees. However, for p odd this number is know to be bounded for many important classes of graphs. A result of Nešetřil and Ossona de Mendez tells us that for every class with bounded expansion this number is bounded. This includes classes with bounded degree and classes closed under talking minors. We present an alternative proof of this result. Our proof relies on the notion of generalized colouring numbers and allows us to obtain better upper bounds for the chromatic number of exact distance graphs for classes such as the class of planar graphs.
This is joint work with Jan van den Heuvel and Hal A. Kierstead.
Friday 12 June - Richard Lang (U Chile)
PhD student of Maya Stein (U Chile)
Monochromatic Cycle Partitions of Bipartite Graphs
Given an arbitrary colouring of the edges of a graph G with r colours, we are interested in determining the smallest number of monochromatic cycles that partition the vertex set of G. (Here, an r-edge-colouring is not necessarily proper, and cycles may be single vertices, edges or the empty set.) Lately, this question received a considerable amount of attention from the community.
In this talk I will give an introduction to the topic and present some results for the case where G is bipartite. This is joint work with Oliver Schaudt and Maya Stein.
Friday 5 June - Maya Stein (U Chile)
3-Coloring of P_7-Free Graphs With and Without Triangles
The topic of the talk is complexity of k-coloring for classes of graphs with forbidden (induced) subgraphs. It is known that if k is at least 3, and H is not a disjoint union of paths, then k-coloring of H-free graphs is NP-complete. The same is true for P_t-free graphs if k is at least 4 and t is at least 6, except for one open case. On the positive side, k-colouring can be solved in polynomial time on P_5-free graphs for any fixed k, and on P_6-free graphs for k=3. This leaves open the complexity of 3-coloring of P_t-free graphs for t at least 7.
In this talk, we describe a polynomial time algorithm for 3-colouring P_7-free graphs, based on joint work with Bonomo, Chudnovsky, Maceli, Schaudt and Zhong, simplifying an earlier unpublished algorithm of the second, third and last author.
Friday 29 May - John Howard (LSE)
Exchanging Goods Using Valuable Money
A group of people wish to use money to exchange goods over a finite number of time periods. They consider using one of the goods as money, but none has suitable characteristics. They understand that traders are prepared to exchange goods for token money only because they believe that in the future they will be able to exchange the money for other goods. So, if society issues fiat money in the form of notes or coins, it will be valueless in the final time period, and hence in all earlier periods.
An alternative would be to allow the traders to create their own money (by writing promissory notes), but then the market equilibrium prices will be determined only up to an arbitrary rescaling. (If a set of prices clears the market, doubling all the prices will also give an equilibrium.) This may not matter in a one-period setting, but if there are several trading periods, it may cause problems.
Is it possible to devise a system which uses money to exchange goods, where money does not enter the traders' utility functions, but which yields a solution in which money has a unique positive value? I will discuss this question (Hahn's problem), and define such a mechanism in a very simple setting. The proposal involves some redistribution of wealth and some distortion of prices, but I will show that these effects can be made small.
Friday 15 May - Vissarion Fisikopoulos (ULB)
Polyhedral computations in computational algebraic geometry and optimization
We study geometric algorithms and polyhedral computations for problems that appear in computational algebraic geometry and optimization.
The first motivation comes from polynomial system solving.
From this perspective (Newton) polytopes characterize polynomials better than total degree thus offering the fundamental representation in sparse elimination theory. We propose output-sensitive algorithms that require the minimum number of polytope oracle calls, each reducing to the construction of a regular triangulation of the input set of points. Their implementation has been used first in the experimental analysis of algorithms and second as a computational tool in our study of the combinatorial characterization of these polytopes.
Another motivation comes from optimization, where polytopes are the solution space of a set of linear inequalities. We study 2-level (or compressed) polytopes, i.e. all of whose pulling triangulations are unimodular. These polytopes can be realized as 0/1 polytopes and contain the class of stable set polytopes of perfect graphs. We propose and implement an algorithm based on formal concept analysis to enumerate all combinatorial types of 2-level polytopes. Experimental results are valuable in the study of their extremal properties and towards proving characterization results with the ultimate goal to be the study of their extension complexity.
Friday 22 May - Joonkyung Lee (Oxford)
Some Advances on Sidorenko's Conjecture
A bipartite graph $H$ is said to have Sidorenko's property if the probability that the uniform random mapping from $V(H)$ to the vertex set of any graph $G$ is a homomorphism is at least the product of the probabilities that each edge of $H$ is mapped into an edge in $G$. In this talk, I will give an overview of the known results and new approaches to attack Sidorenko’s conjecture, especially an embedding algorithm to prove that bipartite graphs admitting a specific form of tree decomposition have Sidorenko's property. This is joint work with David Conlon, Jeong Han Kim, and Choongbum Lee.
Friday 13 March - Matthias Mnich (Bonn)
Steiner Multicut: A Computational Complexity Dichotomy
We consider the Steiner Multicut problem, which asks, given an undirected graph G, a collection T = {T_1 ,...,T_t } of terminal sets of size at most p, and an integer k, whether there is a set S of at most k edges or nodes such that of each set T i at least one pair of terminals is in different connected components of G \ S. This problem generalizes several well-studied graph cut problems, in particular the Multicut problem, which corresponds to the case p = 2. The Multicut problem was recently shown to be fixed-parameter tractable for parameter k [Marx and Razgon, Bousquet et al., STOC 2011]. The question whether this result generalizes to Steiner Multicut motivates the present work.
We answer the question that motivated this work, and in fact provide a full dichotomy of the computational complexity of Steiner Multicut on general graphs. That is, for any combination of k, t, p, and the treewidth tw(G) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable or that the problem is hard (W[1]-hard or even (para-)NP-complete). Among our many results, we highlight that:
-
The edge deletion version of Steiner Multicut is fixed-parameter tractable for parameter k + t on general graphs (but has no polynomial kernel, even on trees).
-
In contrast, both node deletion versions of Steiner Multicut are W[1]-hard for the parameter k + t on general graphs.
-
All versions of Steiner Multicut are W[1]-hard for the parameter k, even when p = 3 and the graph is a tree plus one node.
Since we allow k, t, p, and tw(G) to be any constants, our characterization includes a dichotomy for Steiner Multicut on trees (for tw(G) = 1) as well as a polynomial time versus NP-hardness dichotomy (by restricting k,t,p,tw(G) to constant or unbounded).
Joint work with Karl Bringmann, Danny Hermelin and Erik Jan van Leeuwen.
Friday 6 March - Francesco Nava (LSE)
Decentralized Bargaining: Efficiency and the Core
This paper studies market clearing in matching markets. The model is non-cooperative, fully decentralized, and in Markov strategies. Workers and firms bargain with each other to determine who will be matched to whom and on what terms of trade. Once a worker-firm pair reach agreement they exit the market. Inefficiencies, mismatch, and delay, arise from the strategic response to the potential evolution of the market. The main result identifies a necessary and su¢ cient condition for equilibrium efficiency and shows that inefficiencies are pervasive. Mismatch is a necessary by-product of the market context affecting any bargaining outcome.
Joint work with Matt Elliott
Friday 13 February - Ziv Hellman (Bar Ilan University)
Sex and Portfolio Investment
We propose an answer to `why sex?', a long-standing question stemming from the observation that asexual reproduction is ostensibly more efficient than sexual reproduction.
From the perspective of a genetic allele, each individual bearing that allele is akin to a stock share yielding dividends equal to that individual's number of offspring. The totality of individuals bearing the allele is its portfolio investment. Alleles compete over portfolio growth. Evolutionary reproduction strategies are then seen essentially to be on-line learning algorithms seeking improved portfolio growth, with sexual reproduction a goal-directed algorithmic exploration of genotype space by sampling in each generation. We show that the algorithm of sexual reproduction yields higher expected growth than that of asexual reproduction, thus explaining why a majority of species reproduce sexually.
Joint work with Omer Edhan and Dana Sherill-Rofe.
Friday 16 January - Barnaby Roberts (LSE)
Ramsey Numbers of Powers of Paths
For graphs G and H the Ramsey number, R(G,H), is the least integer n such that every colouring of the edges of the complete graph on n vertices contains either a red copy of G or a blue copy of H.
The k-th power of a path is the graph created from a path by joining all vertices which are at distance at most k from each other.
In joint work with Peter Allen and Jozef Skokan we look at determining the Ramsey number of the square of a path.
Friday 23 January - Nicola Wittur (LSE)
Introduction of "Optimal Use of Communication Resource" - a paper by Gossner, Hernandez and Neyman
Nicola Wittur will introduce a paper by Gossner, Hernandez and Neyman (Optimal Use of Communication Resources). The model can be summarized as follows:
A repeated game between a team of two players and nature is played. The team members have unequal knowledge about future states of nature in the following sense: while the second player (the agent) has no knowledge at all about the future, the first player (the forecaster) is fully informed and is able to signal some of his knowledge to the follower via his action choices. The team’s stage payoff not only depends on both team members actions, but also on the state of nature. Therefore, the forecaster would like to transmit as much of his knowledge about future states of nature as possible to the agent. At the same time, however, this information transmission may reduce the stage payoff.
Nicola will focus on the characterization of the set of distributions over the set of action triples that are implementable by the strategies of the forecaster and the agent.