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.
the PhD seminar takes place on Fridays from 12.00 - 13:00.

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

Upcoming speakers

Thursday 30 March - Karoly Bezdek (University of Calgary)
Hybrid - 14:00 on Zoom, and SAL.LG.04

A new look at r-ball bodies and r-ball polyhedra
An r-ball body (rep., r-ball polyhedron) is an intersection of balls of radius r (resp., of finitely many balls of radius r) in Euclidean d-space. The talk is centered around the following topics via selected results: the Kneser-Poulsen conjecture; Blaschke-Santalo-type inequalities for r-ball bodies; reverse isoperimetric and reverse inradius inequalities for r-ball bodies; Pal’s theorem for r-disk domains; spindle convexity; Caratheodory’s theorem for spindle convex hull; Euler-Poincare formula and Steinitz’s theorem for standard ball-polyhedra.

Friday 31 March - Theophile François Thiery (QMUL)
Hybrid - 12:00 on Zoom, and KSW.G.01

An improved approximation for Maximum Weighted k-Set Packing
The 3-Dimensional Matching problem, which figures in Karp's list of 21 NP-complete problems, is the generalization of bipartite matchings to 3-partite hypergraphs. The best approximation factor for this problem is attained by studying a slightly more general problem: k-Set Packing. In the weighted k-Set Packing problem, we are given weighted sets, each with at most k elements, and must return a maximum weight collection of pairwise disjoint sets. It encodes weighted 3D-matching for k = 3.
By expanding the work of Berman, I will give a simple improved approximation algorithm for the weighted 3-Set Packing problem whose approximation ratio is 1.786. This result improves over the state-of-the-art approximation factor equal to 2 - 10^{-7}. Using more elaborate techniques, I will further explain how to improve over this factor and obtain a tight approximation factor equal to sqrt(3). Our algorithm yields improved guarantees for other values of k as well. Joint work with Justin Ward.

Previous seminars in the series:

Friday 24 March - Cristina Gava (KCL)

Distributed Averaging in Population Protocols
We consider a simple one-way averaging protocol on graphs.
Initially, every node of the graph has a value. A node %%u%% is chosen uniformly at random and %%u%% samples %%k%% neighbours %%v_1,v_2,\cdots,v_k \in N(u)%% uniformly at random. Then, %%u%% averages its value with %%v%% as follows: %%\xi_u(t+1) = \alpha \xi_u(t) + \frac{(1-\alpha)}{k} \sum_{i=1}^k \xi_{v_i}(t)%% for some %%\alpha \in (0,1)%%, where %%\xi_u(t)%% is the value of node %%u%% at time %%t%%. Note that, in contrast to neighbourhood value balancing, only %%u%% changes its value. Hence, the sum (and the average) of the values of all nodes changes over time.
Our results are two-fold. First, we show a bound on the convergence time (the time it takes until all values are roughly the same) that is asymptotically tight for some initial assignments of values to the nodes.
Our second set of results concerns the ability of this protocol to approximate well the initial average of all values: we bound the probability that the final outcome is significantly away from the initial average.
Interestingly, the variance of the outcome does not depend on the graph structure. The proof introduces an interesting generalisation of the duality between coalescing random walks and the voter model.

Thursday 23 March - Simona Boyadzhiyska (University of Birmingham)

Covering real grids with multiplicity
Given a field %%\mathbb{F}%%, finite subsets %%S_1,\dots,S_d\subseteq \mathbb{F}%%, and a point %%\vec{p}\in S_1\times \dots\times S_d%%, what is the smallest number of hyperplanes needed to cover all points of %%S_1\times\dots\times S_d\setminus\{\vec{p}\}\subseteq \mathbb{F}^d%% while omitting %%\vec{p}%% entirely? This question was answered precisely in a celebrated paper of Alon and F\"uredi.
We will discuss a variant of this problem in which every point in %%S_1\times\dots\times S_d\setminus\{\vec{p}\}%% must be covered \emph{at least %%k\geq 1%% times}, while the remaining point %%\vec{p}%% is again left uncovered. In contrast to the case %%k=1%%, this problem is generally not well understood for larger %%k%%.
Recently Clifton and Huang and Sauermann and Wigderson investigated the special case where %%\mathbb{F} = \mathbb{R}%% and the grid is %%\{0,1\}^d%%. A natural next step is to consider larger grids over the reals. In this talk, we will focus on the two-dimensional setting and determine the answer for several different types of grids.

This is joint work with Anurag Bishnoi, Shagnik Das, and Yvonne den Bakker.

Friday 17 March - Andrea Freschi (University of Birmingham)

The induced saturation problem for posets
For a fixed poset %%P%%, a family %%\mathcal{F}%% of subsets of %%[n]%% is induced %%P%%-saturated if %%\mathcal F%% does not contain an induced copy of %%P%%, but for every subset %%S%% of %%[n]%% such that %% S\not \in \mathcal F%%, then %%P%% is an induced subposet of %%\mathcal F \cup \{S\}%%. The size of the smallest such family %%\mathcal{F}%% is denoted by %%\text{sat}^* (n,P)%%.
In recent years, there has been a growing interest in tackling the problem of determining %%\text{sat}^*(n,P)%%. Keszegh, Lemons, Martin, P\'alv\"olgyi and Patk\'os [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset %%P%%, either %%\text{sat}^* (n,P)=O(1)%% or %%\text{sat}^* (n,P)\geq \log _2 n%%. Furthermore, they conjectured that either %%\text{sat}^* (n,P)=O(1)%% or %%\text{sat}^* (n,P)\geq n+1%%.
In this talk we present some progress on this conjecture, namely that either %%\text{sat}^* (n,P)=O(1)%% or %%\text{sat}^* (n,P) \geq 2 \sqrt{n-2}%%. This is joint work with Sim\'on Piga, Maryam Sharifzadeh and Andrew Treglown.

Thursday 16 March - Juan P.Aguilera (Vienna University of Technology)

Generalizations of Borel Determinacy
Martin's Borel Determinacy theorem asserts that all (infinite two-player, perfect-information, zero-sum) Gale-Stewart games are determined, provided that the payoff set is Borel, i.e., simple enough. In this talk, we will cover some of the historical and mathematical context for these games and the theorem and survey various directions in which it can be generalized. The precise contents of the talk will depend on the background and interests of the audience, and it will be self-contained.

Friday 10 March - Eilon Solan (Tel-Aviv University)

Identifying the deviator
A group of players are supposed to follow a prescribed profile of behavior strategies in a repeated game. If they follow this profile, they will reach a given target (namely, a given set of plays) with probability 1. Suppose that the target has not been reached. Can an outside observer, who observes the play, identify the deviator? We show that the answer is positive, and illustrate this result by a couple of nontrivial examples.

Joint work with Noga Alon, Benjamin Gunby, Xiaoyu He, and Eran Shmaya.

Thursday 9 March - Gal Kronenburg (University of Oxford)

Partitioning graphs into isomorphic linear forests
The linear arboricity of a graph G, denoted by la(G), is the minimum number of edge-disjoint linear forests (i.e. collections of disjoint paths) in G whose union is all the edges of G. It is known that the linear arboricity of every cubic graph is 2. In 1987 Wormald conjectured that every cubic graph with even number of edges, can be partitioned such that the two parts are isomorphic linear forests. This is known to hold for Jeager graphs and for some further classes of cubic graphs (see, Bermond-Fouquet-Habib-Peroche, Wormald, Jackson-Wormald, Fouquet-Thuillier-Vanherpe-Wojda). In this talk we will present a proof of Wormald's conjecture for all large connected cubic graphs.

This is joint work with Shoham Letzter, Alexey Pokrovskiy, and Liana Yepremyan.

Friday 3 March - Kamilla Rekvényi (Imperial College)

The Orbital Diameter of Primitive Permutation Groups
In this talk I will be introducing a very versatile concept in algebraic graph theory and nice connections between combinatorics and group theory.
Let G be a group acting transitively on a finite set Ω. Then G acts on ΩxΩ componentwise. Define the orbitals to be the orbits of G on ΩxΩ. The diagonal orbital is the orbital of the form ∆ = {(α, α)|α ∈ Ω}. The others are called non-diagonal orbitals. Let Γ be a non-diagonal orbital. Define an orbital graph to be the non-directed graph with vertex set Ω and edge set (α,β)∈ Γ with α,β∈ Ω. If the action of G on Ω is primitive, then all non-diagonal orbital graphs are connected. The orbital diameter of a primitive permutation group is the supremum of the diameters of its non-diagonal orbital graphs.
There has been a lot of interest in finding bounds on the orbital diameter of primitive permutation groups. In my talk I will outline some important background information and the progress made towards finding explicit bounds on the orbital diameter. In particular, I will discuss some results on the orbital diameter of the groups of simple diagonal type and their connection to the covering number of finite simple groups.

Thursday 2 March - Edita Macajova (Comenius University)

Geometric approach to Berge's conjecture
A fascinating conjecture of Berge suggests that every bridgeless cubic graph can be expressed as a union of at most five perfect matchings. Since three perfect matchings suffice only when the graph is 3-edge-colourable, the remaining cubic graphs fall into two classes: those that can be covered with four perfect matchings, and those that need at least five.
Understanding the cubic graphs that require more than four perfect matchings to cover their edges is therefore fundamental for any potential approach that might lead to proving or disproving Berge's conjecture. A significant obstacle for this has been the fact that examples of cubic graphs that cannot be covered with four perfect matchings are extremely rare and difficult to find.
In the talk we outline a theory that describes coverings with four perfect matchings as flows whose flow values represent points and outflow patterns represent lines of a configuration six lines spanned by four points of the 3-dimensional projective space over the 2-element field in general position. This theory provides a powerful tool for investigating the graphs that do not admit such a cover and leads to a number of new results.
Among them are, for instance, unification all known examples and constructions into a single family, offering a great variety of new constructions, or disproving conjectures that attribute certain properties to cubic graphs that cannot be covered with four perfect matchings.

Friday 24 February - Stavros Ioannidis (KCL)

Strong Approximations and Irrationality in Financial Networks with Derivatives
Financial networks model a set of financial institutions (firms) interconnected by obligations. Recent work has introduced to this model a class of obligations called credit default swaps, a certain kind of financial derivatives. The main computational challenge for such systems is known as the clearing problem, which is to determine which firms are in default and to compute their exposure to systemic risk, technically known as their recovery rates. It is known that the recovery rates form the set of fixed points of a simple function, and that these fixed points can be irrational. Furthermore, Schuldenzucker et al. (2016) have shown that finding a weakly (or ``almost") approximate (rational) fixed point is PPAD-complete.
We study the clearing problem from the point of view of irrationality and approximation strength. Firstly, we observe that weakly approximate solutions may misrepresent the actual financial state of an institution. On this basis, we study the complexity of finding a strongly (or ``near") approximate solution, and show FIXP-completeness. We then study the structural properties required for irrationality, and we give necessary conditions for irrational solutions to emerge: The presence of certain types of cycles in a financial network forces the recovery rates to take the form of roots of non-linear polynomials. In the absence of a large subclass of such cycles, we study the complexity of finding an exact fixed point, which we show to be a problem close to, albeit outside of, PPAD.

Thursday 23 February - Frederik Mallmann-Trenn (KCL)

Finding the best papers with noisy reviews
Say you are tasked to find the best 150 papers among more than 550 papers. You can ask people to review a given paper by either asking
1. Is paper A better than paper B, or
2. What’s the score of paper A?

The problem is that each review returns an incorrect response with a small probability, say 2/3.
How can you assign reviews so that the total number of queries is small and the number of review rounds is small? In other words: How should we review papers? Paper.

Friday 17 February - Alper Yildirim (University of Edinburgh)

On Exact and Inexact RLT and RLT-SDP Relaxations of Nonconvex Box-Constrained Quadratic Programs
In this talk, we study the problem of minimizing a nonconvex quadratic function over a polytope defined by box constraints. This fundamental problem arises in various applications and also as a subproblem in some general nonlinear programming algorithms. Despite its very special structure, this is an NP-hard problem. In fact, it is NP-hard to even approximate a local minimizer. On the other hand, the problem admits various tractable convex relaxations that yield lower bounds on the optimal value. A convex relaxation is said to be exact if the lower bound is equal to the optimal value. We focus on the well-known RLT and RLT-SDP relaxations of box-constrained quadratic programs (BoxQPs). We present complete descriptions of the set of instances that admit exact RLT and RLT-SDP relaxations. We show that our descriptions can be converted into algorithms for efficiently constructing instances of BoxQPs with exact and/or inexact relaxations.

Wednesday 15 February - Akshay Gupte (University of Edinburgh)

Submodular functions — Maximization and Polyhedra
A submodular function over the 0-1 lattice is regarded as a discrete analog of a convex function, and appears commonly in many combinatorial optimization problems. It can be minimised in polynomial-time, but maximisation is NP-hard although it is 1/2-approximable. Many approximation algorithms are known for maximising over different classes of independence families, such as constant number of matroids and %%\le%%-knapsacks. We consider the question over the intersection of an independence family with a collection of %%\le%%- and %%\ge%%-knapsacks that satisfy a certain property that is related to integrality of their covering polytope and their clutters. We show that when %%k%% (number of knapsacks) is bounded by a constant then the maximum can be approximated to the same factor as that for submodular maximisation over the independence family. We also give a lower bound on approximability by establishing that there does not exist a randomised algorithm with factor roughly \Omega(\sqrt{k}/2^\log{n}).
The second part of this talk discusses the submodular polyhedron whose facial structure is widely known when the set corresponds to the epigraph. We extend this facial study to arbitrary domains and under some (mild) structural assumptions, characterise the polyhedron through polarity and with disjunctive inequalities.

Friday 10 February - Emil Powierski (University of Oxford)

Balancing connected colourings of graphs
It is folklore that the edges of any graph %%G%% can be coloured blue and red such that the blue degree and red degree of each vertex differ by at most two. For graphs %%G%% containing two edge-disjoint spanning trees, what if we demand the blue and red graphs to be connected? The focus of this talk will be on showing that any such %%G%% admits a connected blue/red colouring where the colour degrees of each vertex differ by at most four. This improves on a result of Hörsch. We might also briefly discuss variations of the question for digraphs, infinite graphs and a computational question.

Joint work with Freddie Illingworth, Alex Scott and Youri Tamitegama.

Friday 3 February - Kyriakos Katsamaktsis (UCL)

Hamilton cycles in randomly perturbed graphs
Let %%G%% be a graph of order %%n%% with linear minimum degree, and suppose we `perturbe’ %%G%% by adding the edges of the binomial random graph on the same vertex set. It is well known that if the random graph has edge probability at least %%C/n%% for some constant C, then with high probability the perturbed graph is Hamiltonian. We show that if each edge of the perturbed graph gets a colour independently and uniformly at random from a set of size %%n%%, then with high probability the perturbed graph has a rainbow Hamilton cycle, i.e. one with each edge having a different colour. This is joint work with Shoham Letzter.

Thursday 2 February - Afrouz Jabal Ameli (TU/e)

Improved Approximation for Two-Edge-Connectivity
The basic goal of survivable network design is to construct low-cost networks which preserve a sufficient level of connectivity despite the failure or removal of a few nodes or edges. One of the most basic problems in this area is the 2-Edge-Connected Spanning Subgraph problem (2-ECSS): given an undirected graph G, find a 2-edge-connected spanning subgraph H of G with the minimum number of edges (in particular, H remains connected after the removal of one arbitrary edge).
2-ECSS is NP-hard and the best-known (polynomial-time) approximation factor for this problem is 4/3. Interestingly, this factor was achieved with drastically different techniques by [Hunkenschr{ö}der, Vempala and Vetta '00,'19] and [Seb{ö} and Vygen, '14]. In this paper we present an improved 118/89+ϵ<1.326 approximation for 2-ECSS.
The key ingredient in our approach (which might also be helpful in future work) is a reduction to a special type of structured graphs: our reduction preserves approximation factors up to 6/5.
While reducing to 2-vertex-connected graphs is trivial (and heavily used in prior work), our structured graphs are "almost" 3-vertex-connected: more precisely, given any 2-vertex-cut {u,v} of a structured graph G=(V,E), G[V∖{u,v}] has exactly 2 connected components, one of which contains exactly one node of degree 2 in G.

Friday 27 January - Adva Mond (University of Cambridge)

Minimum degree edge-disjoint Hamilton cycles in random directed graphs
At most how many edge-disjoint Hamilton cycles does a given directed graph contain? A trivial upper bound is the minimum between the minimum out- and in-degrees. We show that a typical random directed graph D(n,p) contains precisely this many edge-disjoint Hamilton cycles, given that p >= (log^C n)/n where C is some fixed integer, which is optimal up to a factor of polylog n.
Our proof provides a randomised algorithm to generate the cycles and uses a (relatively) recent "online sprinkling" idea, as was introduced by Ferber and Vu, to generate D(n,p), allowing us to control some key properties of the graph.
This is a joint work with Asaf Ferber and Kaarel Haenni.

Thursday 26 January- Aled Williams (LSE)

Distances to and the sparsity of lattice points in rational polyhedra
During this talk we show a relation holds between two well-established areas of research, namely proximity and sparsity of solutions to integer programs. The proximity-type results provide estimates for the distance between optimal vertex solutions to linear programs and feasible integer points. The sparsity-type results, in their turn, provide bounds on the size of support (i.e. the number of nonzero components) for feasible integer points and solutions to integer programs.
Our initial focus will be on the knapsack scenario. In this context, the results can be viewed as a transference result which allows strengthening the best known distance bound if integer points in the knapsack polytope are not sparse and, vice versa, strengthening the best known sparsity bound if feasible integer points are sufficiently far from a vertex of the knapsack polytope. Upon considering general integer linear programs, we show that a resembling transference inequality holds for vertices of Gomory’s corner polyhedra. This is joint work with Iskander Aliev, Marcel Celaya and Martin Henk.

Thursday 19 January - Robert Simon (LSE)

A Measure theoretic paradox from group action and continuity
This is an example of optimisation that can be solved only in a way not measurable with respect to any finitely additive measure. Special is that the structure is locally finite.

Thursday 15 December - Katherine Staden (Open University)

Counting subgraphs
Given a small graph F, how many copies of F can a large host graph G contain? What is the extremal behaviour -- the maximum and minimum number of copies -- among all host graphs G satisfying a particular property? I will survey various aspects of this classical question, including the Erd\H{o}s-Rademacher problem and the inducibility problem.

Tuesday 13 December - Denizalp Goktas (Brown University)

Stackelberg Games and Their Applications to General Equilibrium Theory
Over the last two centuries, mathematical economists and game theorists alike, have dedicated a great deal of effort to constructing models of rational behavior that are arguably representative of human behavior. These models can be roughly categorized as general equilibrium models, i.e., market models, and game models. Although both concern rational agents, the algorithmic literature on general equilibrium and games has evolved mostly independently. In this talk, I will introduce novel algorithms to solve important classes of two-player sequential, i.e., Stackelberg, zero-sum games, and show how these games can model well known classes of general equilibrium models allowing us to obtain efficient algorithms to solve these models.

Friday 9 December - Bento Natura (Georgia Tech)

Breaking the quadratic gap for strongly polynomial solvers to combinatorial linear programs
Recent years have seen tremendous progress in high-accuracy solvers for Maximum Flow, Minimum-Cost Flow and general Linear Programs (LP). Progress on strongly polynomial solvers for combinatorial LP on the other hand has stalled. The computational gap between high-accuracy solvers and strongly polynomial solvers is linear in the number of variables only for combinatorial LP on directed graphs. For combinatorial LP beyond directed graphs this gap is currently quadratic and is known since the 1980s due to a seminal result by Tardos.
We finally break the quadratic gap and design a strongly polynomial interior-point-method for combinatorial LP, which reduces the gap to only a linear factor. Thus, we match the known linear gap for LP on directed graphs. Furthermore, we close the linear gap between feasibility and optimization of combinatorial LP.

Thursday 8 December - Tom Gur (University of Warwick)

Worst-Case to Average-Case Reductions via Additive Combinatorics
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time T that are only correct on a small (subconstant) fraction of their inputs into algorithms running in time O(T \log T) that are correct *on all* inputs.
Using our framework, we obtain such efficient worst-case to average-case reductions for fundamental problems in a variety of computational models; namely, algorithms for matrix multiplication, streaming algorithms for the online matrix-vector multiplication problem, and static data structures for all linear problems as well as for the multivariate polynomial evaluation problem.
Our techniques crucially rely on additive combinatorics. In particular, we show a local correction lemma that relies on a new probabilistic version of the quasi-polynomial Bogolyubov-Ruzsa lemma.

Joint work with Vahid Asadi, Alexander Golovnev, and Igor Shinkar (STOC ’22).

Friday 2 December - Alp Muyesser (UCL)

Matchings in hypergraphs defined by groups
When can we find perfect matchings in hypergraphs whose vertices represent group elements and edges represent solutions to systems of (linear) equations? Problems expressible in this language include the Hall-Paige conjecture, the n-queens problem, Graham-Sloane harmonious tree-labelling conjecture, Ringel's sequencability conjecture, Snevily's subsquare conjecture, Friedlander-Gordon-Tannenbaum conjecture, and many others. In this talk we discuss a novel approach to attack these problems.

Thursday 1 December - Sharat Ibrahimpur (LSE)

Stochastic Minimum Norm Combinatorial Optimization
In this work, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions; each feasible solution induces a random multidimensional cost vector. The goal is to find a solution that minimizes the expected norm of the induced cost vector, for a given monotone, symmetric norm. We give a framework for designing approximation algorithms for stochastic minimum-norm optimization and use it to obtain approximation algorithms for stochastic min-norm versions of load balancing and spanning tree problems.

Joint work with Chaitanya Swamy. A full version of our results can be found in the speaker's PhD thesis with the same title.

Friday 18 November - Michael Savery (University of Oxford)

Invertibility of digraphs and tournaments: computational complexity and other aspects
For an oriented graph %%D%% and a set %%X\subseteq V(D)%%, the inversion of X in %%D%% is the digraph obtained by reversing the orientations of the edges of %%D%% with both endpoints in %%X%%. The inversion number of %%D%%, %%\operatorname{inv}(D)%%, is the minimum number of inversions which can be applied in turn to %%D%% to produce an acyclic digraph. Bang-Jensen, da Silva, and Havet recently posed a series of interesting conjectures and questions concerning inversions and inversion number; in this talk we will discuss the resolution of several of them. A particular focus will be the computational complexity of deciding for fixed %%k\in \mathbb{N}%% whether an input digraph %%D%% satisfies %%\operatorname{inv}(D)\leq k%%. We will see that in general this problem is NP-complete, but that when the input is restricted to tournaments %%T%% it can be solved in time %%O(|V(T)|^2)%%. These two results respectively confirm a conjecture and answer a question of the above group of authors.

This is joint work with Emil Powierski, Alex Scott, and Elizabeth Wilmer.

Thursday 17 November - Yani Pehova (LSE)

Transversal factors and spanning trees
In this talk we consider a recent transversal, or rainbow, variant of the classical question: for which d do n-vertex graphs with minimum degree d always contain a fixed subgraph H? We consider a collection of graphs %%G_1,G_2,...,G_m%% on the same set of n vertices whose minimum degree is at least d, and ask which d guarantee the existence of a fixed (m-edge) subgraph H using exactly one edge from each %%G_i%%. The obtained copy of H is called a transversal, or a rainbow copy if we view each %%G_i%% as a different colour. We give the correct minimum degree threshold for the existence of rainbow spanning trees with maximum degree %%o(n/\log n)%% and perfect F-tilings in this setting. This is joint work with Alp Müyesser and Richard Montgomery.

Friday 11 November - Mark Voorneveld (Stockholm School of Economics)

No bullying! A playful proof of Brouwer's fixed-point theorem
Consider a finite number of children, each with a single indivisible good (a toy) and preferences over those toys. Let's say that a group of children, possibly after exchanging toys, can bully some poor kid if all group members find their own current toy better than the toy of this victim. We provide an algorithmic proof of a "no-bullying lemma", which asserts that some group S of children can redistribute their toys among themselves in such a way that all members of S get their favorite toy from S, but they cannot bully anyone. This combinatorial lemma is a key ingredient in an elementary proof of Brouwer's fixed-point theorem. The only mathematical prerequisite is a version of the Bolzano-Weierstrass theorem: a sequence in a compact subset of n-dimensional Euclidean space has a convergent subsequence with a limit in that set.

Thursday 10 November - Andrea Celli (Bocconi University)

Online bidding in repeated auctions under long-term constraints
Budget-management systems are one of the key components of modern auction markets. Internet advertising platforms typically offer advertisers the possibility to pace the rate at which their budget is depleted, through budget-pacing mechanisms. In this setting, the (proxy) bidder is confronted with a series of advertising opportunities, and wants to maximize their expected reward without violating a finite set of resource constraints. The case of repeated second-price auctions is well-understood. In this talk, I will present a general framework for online learning problems with long-term constraints which can be applied, for example, to online bidding problems in repeated first-price auctions. The results are based on the adversarial bandits with knapsack framework. Our framework yields the first best-of-both-worlds type algorithm for this setting, with no-regret guarantees both under stochastic and adversarial inputs. When budgets grow at least linearly in the time horizon, it allows us to provide the first constant-factor competitive ratio for this setting in the adversarial case.

Friday 4 November - Tamio-Vesa Nakajima (University of Oxford)

Linearly Ordered Hypergraph Colouring
Consider a set of products, and subsets of r products that are, in some sense, comparable. Suppose we want to assign these products k ratings such that each set of comparable products has a clear best product i.e. a unique product with maximum rating. Such a collection of products can be seen as an r-uniform hypergraph, and such an assignment is called a linearly ordered colouring of that hypergraph. In this talk we will explore various promise problems dealing with linearly ordered Hypergraph colourings. In particular, we will explain a state-of-the-art algorithm for finding a linearly ordered colouring when we are promised that a linearly ordered colouring with 2 colours exists; and we will also discuss some intractable problems of this kind.

Friday 28 October - Sahar Jahani (LSE)

Automated Equilibrium Analysis of 2 × 2 × 2 Games
The set of all Nash equilibria of a non-cooperative game with more than two players is defined by equations and inequalities between nonlinear polynomials, which makes it challenging to compute. In this talk, we present an algorithm that computes this set for the simplest game with more than two players with arbitrary (possibly non-generic) payoffs, which has not been done before. We give new elegant formulas for completely mixed equilibria, and compute visual representations of the best-response correspondences and their intersections, which define the Nash equilibrium set. These have been implemented in Python and will be part of a public web-based software for automated equilibrium analysis.

Thursday 27 October - Matías Pavez-Signé (University of Warwick)

Counting spanning subgraphs in dense hypergraphs
In the 1990s, Bollobás and Bondy posed the question of estimating the number of distinct Hamilton cycles in graphs with large minimum degree. This question was solved by Cuckler and Kahn in 2009, who found precise estimates on both the number of Hamilton cycles and perfect matchings in graphs with large minimum degree. In recent years, there have been some efforts to extend this question in uniform hypergraphs. In this talk, we will introduce a technique that allows us to estimate the number of distinct copies of some families of spanning hypergraphs in k-graphs with large minimum degrees. In particular, we can estimate the number of distinct Hamilton l-cycles in hypergraphs with minimum codegree above the threshold for Hamiltonicity. This is joint work with Richard Montgomery.

Thursday 20 October - Daniel Kráľ (Masaryk University)

Common graphs with arbitrary large chromatic number
A graph is common if the number of its monochromatic copies in a 2-edge-coloring of a large complete graph is minimized by the random 2-edge-coloring. This notion goes back to the work of Erdős in the 1960s, who conjectured that every complete graph is common. The conjecture was disproved by Thomason in the 1980s, however, a classification of common graphs remains one of the most intriguing problems in extremal combinatorics.
Sidorenko's Conjecture (if true) would imply that every bipartite graph is common, and in fact, no bipartite common graph unsettled for Sidorenko's Conjecture is known. Until Hatami et al. showed that a 5-wheel is common about a decade ago, common graphs with chromatic number two or three only were known. We establish the existence of (connected) common graphs with arbitrarily large chromatic number.

The talk is based on joint work with Jan Volec and Fan Wei.

Friday 14 October - Research Catch-up
Hybrid - 12:00 on Zoom, and PAR.2.03

Speakers Robert Simon, Aled Williams, Yani Pehova, Mahsa Dalirrooyfard, Domenico Mergoni, and Sharat Ibrahimpur will speak about their research for 5-7 minutes each.

Wednesday 12 October - Nathan Klein (University of Washington)

A Deterministic Better-Than-3/2 Approximation Algorithm for Metric TSP
I will describe a deterministic algorithm with an approximation ratio below 3/2 for the metric traveling salesperson problem (TSP). The algorithm builds on recent work which showed the same ratio was achievable by a randomized algorithm; here, we show that the analysis in the prior work can be implemented in polynomial time. In this talk, I will assume no familiarity with prior work and give a relatively self-contained proof for a simple case. Our arguments rely on properties of strong Rayleigh distributions, the structure of near minimum cuts, and the fact that the generating polynomial of lambda-uniform spanning trees can be efficiently evaluated. Based on joint work with Anna Karlin and Shayan Oveis Gharan.

Friday 7 October - Abraham Neyman (The Hebrew University of Jerusalem)
Hybrid - 12:00 on Zoom, and PAR.2.03

Stochastic games with limited memory space
Uniform e-optimal strategies in two-person zero-sum stochastic games that use little public memory space (explicitly, O(log n) memory states are used in the first n stages of the game) are introduced, and it is shown that any strategy in the Big Match that uses a finite public memory is worthless.

Joint work with Kristoffer Arnsfelt Hansen and Rasmus Ibsen-Jensen.

Thursday 6 October - Kalina Petrova (ETH Zurich)

Size-Ramsey numbers of graphs with maximum degree three
The size-Ramsey number %%\hat{r}(H)%% of a graph %%H%% is the smallest number of edges a (host) graph %%G%% can have, such that for any red/blue colouring of %%G%%, there is a monochromatic copy of %%H%% in %%G%%. Recently, Conlon, Nenadov and Truji\'c showed that if %%H%% is a graph on %%n%% vertices and maximum degree three, then %%\hat{r}(H) = O(n^{8/5})%%, improving upon the upper bound of %%n^{5/3 + o(1)}%% by Kohayakawa, R\"odl, Schacht and Szemer\'edi. In joint work with Nemanja Dragani\'c (ETH Z\"urich), we show that %%\hat{r}(H)\leq n^{3/2+o(1)}%%. While the previously used host graphs were vanilla binomial random graphs, we prove our result using a novel host graph construction. Our bound hits a natural barrier of the existing methods.

Friday 30 September - Simon Jantschgi (University of Zurich & Grenoble-Alpes)

Markets and Transaction Costs
Transaction costs are omnipresent in markets but are often omitted in economic models. In markets in which the price is set to equate revealed supply and demand, we show that the presence of transaction costs can fundamentally alter incentive and welfare properties.
We categorize transaction costs into two types. Asymptotically uninfluenceable transaction costs— such as fixed and price fees—preserve the key properties of markets without transaction costs, namely asymptotic strategyproofness, efficiency, and robustness to misspecified beliefs and to aggregate uncertainty.
In contrast, influenceable transaction costs—such as spread fees—lead to complex strategic behavior (price guessing) that may result in severe market failure.
Considering a social planner with a given objective function, we show that the same categorization determines their behavior.
Any asymptotically uninfluenceable transaction cost can maximize the objective function if optimally scaled, while purely influenceable transaction costs lead to zero revenue. Furthermore, all asymptotically uninfluenceable optimally-scaled transaction costs lead to the same welfare. Our insights extend beyond markets equalizing demand and supply.

Thursday 29 September - Zoltan Szabo (LSE)

Support Vector Machines with Hard Shape Constraints
Shape constraints enable one to incorporate prior knowledge into predictive models in a principled way with numerous successful applications. Including this side information in a hard fashion (for instance, at each point of an interval) for rich function classes however is a quite challenging task. I am going to present a convex optimization framework to encode hard affine constraints on function values and derivatives in the flexible family of kernel machines. The efficiency of the approach will be demonstrated in joint quantile regression (analysis of aircraft departures), convoy localization and safety-critical control (piloting a submarine vehicle while avoiding obstacles). [This is joint work with Pierre-Cyril Aubin-Frankowski. Preprint.

Thursday 22 September - Lucas Pahl (University of Bonn)

Robustness of Equilibria in Generic Extensive-Form Games
We prove the 2-player, generic extensive-form case of the conjecture of Govindan and Wilson (1996, 1997) and Hauk and Hurkens (2002) stating that an equilibrium component is essential in every equivalent game if and only if the index of the component is nonzero. This provides an index-theoretic characterization of the concept of hyperstable components of equilibria in generic extensive-form games, first formulated by Kohlberg-Mertens (1986). We explore consequences of the result for the literature on refinements.
Joint work with Carlos Pimienta (University of New South Wales, Sydney)

Friday 16 September - Dana Pizarro (Université Toulouse 1 Capitole)

Competition and Recall in Selection Problems
In this talk, I will present an extension of the prophet inequality problem to a competitive setting. At every period, a new sample from a known distribution arrives, which is publicly observed. Then, two players simultaneously decide whether to pick an available value or to pass and wait until the next period (ties are broken uniformly at random). As soon as a player gets one sample, he leaves the market, and his payoff is the value of the sample. In a first variant, namely no recall case, the agents can only bid in each period for the current value. In a second variant, the full recall case, the agents can also bid at each period for any of the previous samples that have not been already selected. For each variant, we study the two-player game induced by the optimal stopping problem, focusing on subgame-perfect Nash equilibria. In particular, I will describe the set of subgame-perfect Nash equilibria payoffs, I will compare the two model variants in terms of the payoffs of the players and I will provide tight bounds for the Price of Anarchy and Price of Stability of the former setting when the number of arrivals is two.

Joint work with Fabien Gensbittel and Jérôme Renault (TSE).

Seminar and PhD Seminar on Combinatorics, Games and Optimisation:

2021/22, 2020/21, 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