Seminar and PhD Seminar on Combinatorics, Games and Optimisation

Friday 26 September 2025 - Willem van Hoeve (CMU)

**The seminar will take place from 15:30 to 16:30.**

Column Elimination for Arc Flow Formulations

We present column elimination, an iterative framework for solving integer programming problems expressed as arc-flow formulations. In these models, a feasible solution corresponds to a collection of paths through a directed acyclic graph, and the problem reduces to solving a constrained network flow. Because the graphs can quickly grow prohibitively large, column elimination begins with a smaller, relaxed representation of the graph, obtained from a relaxed dynamic program, that admits infeasible paths.

At each iteration, we solve the relaxed network flow problem, identify and remove infeasible paths in the solution, and repeat until an optimal feasible solution is found. The term 'column elimination' stems from the fact that each path corresponds to a column in a Dantzig-Wolfe interpretation of the model. Perhaps surprisingly, this method can prove optimality using a relaxed network that can be orders of magnitude smaller than the exact network flow formulation.

To accelerate the method, we utilize a dedicated subgradient algorithm to solve a Lagrangian relaxation of the problem, which offers additional opportunities for graph refinement. We experimentally demonstrate that column elimination can be competitive with or outperform state-of-the-art methods on several problem domains. Specifically, column elimination closes five open instances of the graph multicoloring problem, one open instance with 1,000 locations of the vehicle routing problem with time windows, and six open instances of the pickup-and-delivery problem with time windows. Since July, 2025, column elimination has been successfully integrated into the commercial optimization solver Hexaly as a generic dual bounding technique.

Friday 26 September 2025 - Yurong Chen (Inria, Ecole Normale Superieure, PSL Research University, France )

Learning a Stackelberg Leader's Incentives from Optimal Commitments

Stackelberg equilibria, as functions of the players' payoffs, can inversely reveal information about the players' incentives. In this paper, we study to what extent one can learn about the leader's incentives by actively querying the leader's optimal commitments against strategically designed followers. We show that, by using polynomially many queries and operations, one can learn a payoff function that is strategically equivalent to the leader's, in the sense that: 1) it preserves the leader's preference over almost all strategy profiles; and 2) it preserves the set of all possible (strong) Stackelberg equilibria the leader may engage in, considering all possible follower types. As an application, we show that the information acquired by our algorithm is sufficient for a follower to induce the best possible Stackelberg equilibrium by imitating a different follower type. To the best of our knowledge, we are the first to demonstrate that this is possible without knowing the leader's payoffs beforehand. Due caution is necessary when one intends to utilize the power of optimal commitment.

This is joint work with Xiaotie Deng (Peking University), Jiarui Gan (University of Oxford), and Yuhao Li (Columbia University).

Thursday 11 September 2025 - János Pach (Rényi Institute and EPFL)

Chromatic number and embeddings

What makes the chromatic number of a graph large? There have been many attempts to answer this question. The most natural approach is to look for unavoidable substructures in graphs of large chromatic number. Hadwiger made the conjecture that every graph of chromatic number r can be transformed into a complete graph of r vertices by a series of edge contractions and vertex and edge deletions. This is known to be true for r<6. There are several related problems on embeddability properties of graphs that I plan to explain.

The crossing number of a graph G is the smallest number of edge crossings in a proper drawing of G in the plane. According to Albertson's conjecture, the crossing number of every graph of chromatic number r is at least as large as the chromatic number of a complete graph with r vertices. We settle Albertson's conjecture for graphs whose number of vertices is not much larger than their chromatic number. Joint work with Jacob Fox and Andrew Suk.

Thursday 24 July 2025 - Akash Kumar (IIT Bombay)

Approximating Dasgupta Cost of Clusterable Graphs in Sublinear Time

In a 2002 work, Goldreich and Ron gave sublinear time algorithms for testing graph expansion. In 2015, Czumaj, Peng, and Sohler extended these ideas to test \(k\)-clusterability in roughly \(approx \sqrt{n}\) time.

However, no sublinear time algorithms are known that give any information about the cluster structure of a \(k\)-clusterable graph. That is, no such algorithms are known for understanding how clusters connect to each other. As a simple example, one may wonder whether it is possible to locally distinguish between the “cluster graph” forming a line from a cluster graph which forms a clique.

In this talk, I will present sublinear time algorithms for estimating the hierarchical cluster structure of \(k\)-clusterable graphs. The measure we use is Dasgupta cost, which is a standard way to evaluate hierarchical clustering. Our main result is a sublinear time algorithm that approximates the Dasgupta cost of a \(k\)-clusterable graph using a small number of randomly chosen seed vertices with known cluster labels.

In particular, I will describe an algorithm that gives an \(O(\sqrt{\log k})\) approximation to the Dasgupta cost of (G) in roughly \(approx \sqrt{n}\) time, using about \(approx n^{1/3}\) seeds. This can be viewed as a sublinear time simulation of the algorithm of Charikar and Chatziafratis (SODA 2017) on clusterable graphs.

This is joint work with Michael Kapralov, Silvio Lattanzi, Aida Mousavifar, and Weronika Kaminska.

Thursday 10 July 2025 - Bertrand Guenin (University of Waterloo) 

Bridging the gap between Linear and Integer Programming

 Informally, an Integer Program is obtained from a Linear Program by adding the condition that some variables be restricted to be integer. What kind of other restrictions lead to interesting classes of optimization problems? One such class of problems is obtained by restricting the variables in a Linear Program to be dyadic rationals, i.e. rationals where the denominator is a power of two. These problems borrow features from both Linear Programming and Integer Programming. Notably, they can be solved in polynomial time, but optimal solutions may have large support.

 There is a rich body of work investigating which Linear Programs are guaranteed to have integer solutions. We study which Linear Programs are guaranteed to have dyadic solutions. This is motivated by a 1975 conjecture by Paul Seymour on ideal clutters, that has implications for matchings in graphs, and for directed cuts in digraphs. We also show that this theory has some surprising implications for combinatorial optimization as it leads to a geometric characterization of Total Dual Integrality for non-degenerate instances.

Friday 4 July 2025 - Chien-Chung Huang (CNRS)

Robust Sparsification for Matroid Intersection with Applications

The matroid intersection problem is a fundamental problem in combinatorial optimization. In this problem we are given two matroids and the goal is to find the largest common independent set in both matroids. This problem was introduced and solved by Edmonds~\cite{edmonds1970submodular, Edmonds1971, Edmonds1979} in the 70s. The importance of matroid intersection stems from the large variety of combinatorial optimization problems it captures; well-known examples in computer science include bipartite matching and packing of spanning trees/arborescences. 

In this talk, we introduce a ``sparsifer'' for the matroid intersection problem and use it to design algorithms for two problems closely related to streaming: a one-way communication protocol and a streaming algorithm in the random-order streaming model. 

This is a joint-work with François Sellier.

Friday 27 June 2025 - Shagnik Das (NTU)

Odd-Ramsey numbers of complete bipartite graphs

Introduced by Alon in his study of graph codes, the odd-Ramsey number of a family of graphs \(H\) in \(K_n\) is the minimum number of colours needed to colour the edges of \(K_n\) so that every copy of every graph in \(H\) intersects some colour class in an odd number of edges. In this talk, we focus on complete bipartite graphs, and shall present tight results when H is a family of spanning complete bipartite graphs. To prove our results, we demonstrate a close connection to a problem in coding theory regarding the maximum dimension of a linear code with forbidden weights. We shall also present bounds on the odd-Ramsey numbers of fixed (i.e. not spanning) complete bipartite graphs.

This is joint work with Simona Boyadzhiyska, Thomas Lesgourgues, Kalina Petrova, and Ying-Sian Wu.

Thursday 26 June 2025 - Thomas Lidbetter (Rutgers)

Booby trap games

We consider a family of zero-sum attacker-defender games in which a defender plants one or more booby traps in some search space and an attacker attacks a subset of the space. There is a reward function on subsets of the space, and the payoff to the attacker is equal to the reward of his chosen subset, as long as that subset contains no booby traps. If it contains a booby trap, the reward is zero. We discuss variants of the game where the search space is (i) a subset of Euclidean space, (ii) a set of boxes, or (iii) a network.

Friday 20 June 2025 - Panayotis Mertikopoulos (Grenoble, Inria)

Online learning in games: Limits, limit sets, and limitations

 Online learning deals with self-interested agents that are involved in an unknown, repeated game, and seek to improve their payoffs over time (much as you would when driving to work each day). I will begin with an overview of some widely used algorithms based on the idea of "regularized learning", paying special attention to the information available to the players— from full state observations, to payoff-based feedback (that is, when each player can only observe their own payoff and has no further information). I will then examine the interplay between the response graph of the game—a (weighted) directed graph capturing the players' profitable deviations—and the long-run behavior of regularized learning in games. A first important characterization is that the stable limit points of regularized learning are precisely the sink nodes of the graph, which correspond to the strict equilibria of the game—in particular, no mixed Nash equilibria can be stable or attracting. More generally, we show that a span of pure strategies is stable and attracting under regularized learning if and only if it is closed under better replies (i.e., it has no outgoing edges). At the other end of the spectrum, by looking at the Hodge decomposition of the game's response graph, we show that the absence of such "sink" components can lead to a phenomenon known as Poincaré recurrence, that is, players return infinitely often, infinitely close to their starting point.

Thursday 19 June 2025 - Benny Sudakov (ETH Zurich) 

Disjoint Pairs in Set Systems and the Combinatorics of Low-Rank Matrices

In this talk, I will discuss the solution to several problems in two closely related settings: set families in \(2^{[n]}\) with many disjoint pairs, and low-rank matrices with many zero entries.

Highlights include a resolution of an old question of Daykin and Erdős on the maximum number of disjoint set pairs, a proof of a conjecture by Singer and Sudan motivated by the log-rank conjecture in communication complexity, and tight bounds for a problem posed by Alon, Gilboa, and Gueron related to a long-standing question in coding theory about cover-free families.

Our proofs use probabilistic, entropy, and discrepancy methods, revealing connections to additive combinatorics and coding theory.

Joint with Hunter, Milojević and Tomon.

Wednesday 18 June 2025 - Raimundo Saona 

Computational complexity and strategy characterization for small memory policies in Partially Observable Sequential Decision Making

Partially Observable Markov Decision Processes (POMDPs) model a controller interacting with an uncertain environment.

A fundamental objective is to reach a target state. The general problem is algorithmically impossible:

(1) Approximating the maximum probability the controller can guarantee to reach the target is undecidable.

(2) even deciding if the maximum guarantee is probability 1 or not is undecidable.

Therefore, we study the problem for constant memory policies.

Under this restriction, the problem was known to be in between NP and a fundamental problem in geometry.

Beyond explaining the computational complexity achieved, I will explain fundamental tools in logic and parameterized Markov Chains. 

Thursday 12 June 2025 - Ian Kash (University of Illinois Chicago)

Binary-Report Peer Prediction for Real-Valued Signal Spaces

Theoretical guarantees about peer prediction mechanisms typically rely on the discreteness of the signal and report space. However, we posit that a discrete signal model is not realistic: in practice, agents observe richer information and map their signals to a discrete report. In this paper, we formalize a model with real-valued signals and binary reports. We study a natural class of symmetric strategies where agents map their information to a binary value according to a single real-valued treshold. We characterize equilibria for several well-known peer prediction mechanisms which are known to be truthful under the binary report model. In general, even when every threshold would correspond to a truthful equilibrium in the binary signal model, only certain tresholds remain equilibria in our model. Furthermore, by studying the dynamics of this treshold, we find that some of these equilibria are unstable. These results suggest important limitations for the deployment of existing peer prediction mechanisms in practice.

Joint work with Raf Frongillo and Mary Monroe.

Thursday 5 June 2025 - Xuan Vinh Doan (Warwick)

Robust Operations Research Games under Uncertainty and Distributional Ambiguity

Operations research games such as linear production games concern the cooperation among players who would face a joint optimization problem and share benefits/costs together if they agree to cooperate. In this talk, we apply the robust cooperative game framework to operations research games under uncertainty and distributional ambiguity and introduce a new solution concept of (robust) least chance decisions, which is the best "latent" robust core decision. We develop optimization formulations to find those decisions and compute their (robust) least chance dissatisfaction, and (in)stability measure which is the analogy of the least core value in deterministic games, for robust cooperative games under normally distributed uncertainty and moment-based distributional ambiguity. We demonstrate how the framework can be applied to operations research games such as linear production games with detailed analytical results.

Wednesday 4 June 2025 - Sharat Ibrahimpur (Bonn).

An O(log n)-Approximation Algorithm for (p,q)-Flexible Graph Connectivity via Independent Rounding 

In this talk I will present improved approximation algorithms for the Flexible Graph Connectivity (FGC) model of Adjiashvili, Hommelsheim and Mühlenthaler (IPCO 2020). Since its introduction the FGC model has received a lot of interest as it offers new means of capturing non-uniformity of edges that appear in survivable network design applications. In this setting, we are given a graph \( G = (V,E) \) whose edges have nonnegative costs and they are either safe and unsafe. The algorithmic goal in the \( (p,q) \)-FGC problem is to find a minimum cost set of edges \(F\) such that the subgraph \( (V,F) \) remains \(p\)-edge-connected after removing any \(q\) unsafe edges from \(F\), for some given connectivity and robustness parameters \(p\) and \(q\), respectively. 

I will present a new integer programming formulation for the \( (p,q) \)-FGC problem which is obtained by adding knapsack cover constraints to the capacitated \(p(p+q)\)-edge-connectivity formulation studied in previous work. I will then show that the associated linear relaxation can be solved in polynomial time by giving an efficient separation oracle. Complementing this, we will see that a simple independent randomized rounding of the LP solution yields an \(O(\log n)\)-approximation for general  values of \(p\) and \(q\), improving the state-of-the-art \(O(q \log n) \). For both separation and rounding, a key insight is to use Karger's bound on the number of near-minimum cuts. 

Based on joint work with László A. Végh: https://arxiv.org/abs/2501.12549.

Friday 30 May 2025 - Sahar Jahani (LSE)

Empirical Game-Theoretic Analysis of a Pricing Game

In recent years, many studies have examined the potential for collusion in pricing games between competing agents trained using machine learning. In this paper, we investigate a well-known asymmetric duopoly pricing game with demand inertia, played over multiple rounds. Given the infinite space of possible pricing strategies, we approximate the "hypergame" between all potential strategies using the Policy Space Response Oracle (PSRO) method. This approach constructs an evolving meta-game in which each agent’s pricing strategies corresponds to pure strategies in a bimatrix game.

We train these pricing strategies using two popular reinforcement learning algorithms: Proximal Policy Optimisation (PPO) and Soft Actor-Critic (SAC). We analyse the equilibria of the expanding meta-game as approximations of the hypergame equilibria. Our study highlights the strengths and limitations of each learning algorithm in training different types of strategies. Furthermore, we explore the modifications required to lead the training agents towards collusive behaviour and examine the resulting equilibrium strategies.

Thursday 29 May 2025 - Penny Haxell (University of Waterloo)

A topological approach in discrete optimisation

We describe how a topological method applies to a classical optimisation problem. In the max-min allocation problem, a set \( P \) of players are to be allocated disjoint subsets of a set \( R \) of indivisible resources, such that the minimum utility among all players is maximised.

In the restricted variant, also known as the Santa Claus problem, each resource (''toy'') has an intrinsic positive value, and each player (''child'') covets a subset of the resources. Thus, Santa wants to distribute the toys amongst the children, while wishing to maximise the minimum total value of toys received by each child. This problem turns out to have a natural reformulation in terms of hypergraph matching.

Bezáková and Dani showed that the Santa Claus problem is NP-hard to approximate within a factor less than \(2\), consequently, a great deal of work has focused on approximate solutions. To date, the principal approach for obtaining approximation algorithms has been via the Configuration LP (CLP) of Bansal and Sviridenko, and bounds on its integrality gap.

The existing algorithms and integrality gap estimations tend to be based on a combinatorial local search argument for finding perfect matchings in certain hypergraphs.

Here we introduce a different approach, which in particular replaces the local search technique with the use of topological methods for finding hypergraph matchings. This yields substantial improvements in the integrality gap of the CLP, both in the general case and in the \(1\), \( \varepsilon\)-restricted version, in which resources can take only two values.

 This is based on joint work with Tibor Szabó.

Wednesday 28 May 2025 - Julian Sahasrabudhe (Cambridge)

A new lower bound for the Ramsey numbers \(R(3,k)\)

 In this talk I will discuss a new lower bound for the off-diagonal Ramsey numbers \(R(3,k)\). For this, we develop a version of the triangle-free process that is significantly easier to analyse than the original process. We then 'seed' this process with a carefully chosen graph and show that it results in a graph with smaller independence number.

This is based on joint work with Marcelo Campos, Matthew Jenssen and Marcus Michelen.

Thursday 15 May 2025 - Zhening Li (University of Portsmouth)

Sphere covering and approximating tensor norms

The matrix spectral and nuclear norms appear in enormous applications. The generalization of these norms to high-order tensors is becoming increasingly important, but unfortunately they are both NP-hard to compute or even approximate. Although the two norms are dual to each other, the best-known approximation bound achieved by polynomial-time algorithms for the tensor nuclear norm is worse than that for the tensor spectral norm. We bridge this gap by proposing deterministic algorithms with the best bound for both tensor norms. The main idea is to construct a selection of unit vectors that can approximately represent the unit sphere, in other words, a collection of spherical caps to cover the sphere. For this purpose, we explicitly construct several collections of spherical caps for sphere covering with adjustable parameters for different levels of approximations and cardinalities. These readily available constructions are of independent interest, as they provide a powerful tool for various decision-making problems on spheres and related problems. Our results can be generalized to the ℓp-sphere covering and approximating spectral and nuclear p-norms.

Friday 9 May 2025 - Asaf Cohen (Tel Aviv University)

Weak saturation and collapsible complexes in a random graph

Let \(H\), \(G\) be two graphs. A spanning subgraph \(G'\) of \(G\) is called weakly    \(H\)-saturated if the following holds: one can add to \(G'\) the edges of \(G \setminus G'\) in some order so that whenever a new edge is added, a new copy of \(H\) is formed. Obtaining lower bounds for the size of such a \(G'\) (for various \(H\) and \(G)\) is a classical problem in extremal combinatorics. In particular, in the past 40 years, various algebraic tools have been used in order to prove such lower bounds. Our first contribution in this work unravels a new algebraic/topological connection which can be used in order to prove the following result. Let \(\text{w-sat}(t,G)\) be the size of a smallest weakly \(K_t\)-saturating subgraph of \(G\). Korandi and Sudakov asked to determine the threshold probability for the property that \(\text{w-sat}(t,G(n,p))=\text{w-sat}(t,K_n)\). Using our new observation, in the case \(t=3\), we show that the threshold probability is located at \(p=n^{-1/3 \pm o(1)}\). Moreover, using an argument inspired by Gromov's 'local to global' theorem, we determine, up to a multiplicative constant factor, the threshold probability for a bounded diameter version of the theorem.

Interestingly, our new connection between weak saturation and topological properties goes both ways since it also enables us to use combinatorial arguments in order to obtain new results concerning topological properties of random clique complexes.

In particular, we obtain a new upper bound on the threshold probability for simple connectivity of the 2-dimensional clique complex of G(n,p), improving a result of Khale.

Joint work with Yuval Peled, Asaf Shapira, Mykhaylo Tyomkyn, and Maksim Zhukovskii.

Friday 4 April 2025 - Francesco Di Braccio (LSE) 

The Zarankiewicz problem on tripartite graphs

In 1975, Bollobás,  Erdős, and Szemerédi asked for the smallest \(\tau\) such that a tripartite graph with \(n\) vertices in each part and minimum degree at least \(n + \tau\) must contain \(K_{t, t, t}\), conjecturing that \(\tau = O(n^{1/2})\) for \(t = 2\). In this talk, I will discuss our proof that \(\tau = O(n^{1 - 1/t})\), which confirms their conjecture and is best possible for all \(t \geq 2\) assuming the widely believed conjecture that \(\mathrm{ex}(n, K_{t, t}) = \Theta(n^{2 - 1/t})\). I will also present our construction of an infinite family of extremal graphs that are pairwise far apart (requiring the change of \(\Omega(n^2)\) edges to get between any two).

This is joint work with Freddie Illingworth. 

Thursday 3 April 2025 - John Sylvester (Liverpool) 

Adjacency Labeling Schemes for Small Classes

 An adjacency labeling scheme for a class of graphs\(\mathcal{C}\) defines, for any \(n\text{-vertex } G \in \mathcal{C}\), an assignment of labels to each vertex in \(G\) so that adjacency in \(G\) is determined by a (fixed) function of the two labels of the endpoints. The _size_ of a labeling scheme is the bit length of the longest label, which we want as small as possible. If \(|\mathcal{C}_n|\) denotes the number of \(n\text{-vertex graphs in }\mathcal{C}\), then any adjacency labeling scheme has size at least  \(\log|C_n|)/n\). 

For many classes (e.g. planar, bounded twin-width, bounded degeneracy) this lower bound is tight up to a constant. In 1988 the Implicit Graph Conjecture (IGC) postulated that any _hereditary_ (closed under induced subgraphs)  class \(\mathcal{C}\) with \(\|\mathcal{C}_n|=2^{O(n\log n)}\) admits a labeling scheme of size \(\Theta(\log n)\), matching the lower bound. Hatami and Hatami recently disproved this, using the probabilistic method to construct a hereditary factorial class requiring almost \(\sqrt{n}\) size labels.

We begin with a more gentle introduction to labeling schemes, before outlining what we think to be the correct reformulation of the IGC: any hereditary class \(\mathcal{C}\) with \(|\mathcal{C}_n|=n!\,2^{O(n)}\) admits a labeling scheme of size \(\Theta(\log n)\). We prove this under the additional restriction that the class is _weakly sparse_ (excludes some fixed bipartite complete graph as a subgraph). We also prove that the conjecture holds if one relaxes the size bound to \(O(\log^3 n)\), improving on the previously best-known upper bound of \(n^{1-\Omega(1)}\). 

This is joint work with Édouard Bonnet, Julien Duron, Viktor Zamaraev and Maksim Zhukovskii.

Friday 28 March 2025 - Mihir Neve (LSE)

Robustness of the Sauer–Spencer Theorem

A robustness result typically examines how strongly an extremal theorem holds. More precisely, given a graph \(G\) and \(p \in [0, 1]\), we define \(G(p)\) to be the random subgraph of \(G\) generated by retaining each edge of \(G\) independently with probability \(p\). Suppose the graph \(G\) satisfies some property \(\Pi\). Then, this property \(\Pi\) is said to hold robustly for \(G\) if, for some \(p < 1\), the random subgraph \(G(p)\) also has the property \(\Pi\) with high probability. We prove such a robustness result for an old and well-known graph embedding theorem of Sauer and Spencer. The Sauer--Spencer theorem gives a minimum degree condition on the host graph \(G\) that enforces \(G\) to contain any spanning subgraph of a bounded constant maximum degree \(\Delta\). In this talk, I plan to sketch some key ideas that were used to prove our robustness result. One of our main tools is a vertex-spread version of the blow-up lemma of Allen, Böttcher, Hàn, Kohayakawa, and Person. 

This is a joint work with Peter Allen, Julia Böttcher, and Yoshiharu Kohayakawa.

Thursday 27 March 2025 - Dario Paccagnan (Imperial) 

Bridging Nash equilibria and Security Strategies via Optimal Transport

In many game-theoretic settings, agents are challenged with taking decisions against the uncertain behavior exhibited by others. Often, this uncertainty arises from multiple sources, e.g., incomplete information, limited computation, bounded rationality. While it may be possible to guide the agents’ decisions by modeling each source, their joint presence makes this task particularly daunting. Toward this goal, it is natural for agents to seek protection against deviations around the emergent behavior itself, which is ultimately impacted by all the above sources of uncertainty. To do so, we propose that each agent takes decisions in face of the worst-case behavior contained in an ambiguity set of tunable size, centered at the emergent behavior so implicitly defined. This gives rise to a novel equilibrium notion, which we call strategically robust equilibrium. Building on its definition we show that, when judiciously operationalized via optimal transport, strategically robust equilibria (i) interpolate between Nash and security strategies; (ii) come at no additional computational cost compared to Nash equilibria; (iii) often lead to better decisions and higher payoffs. Through a variety of experiments including bi-matrix games, congestion games, and Cournot competition, we show that strategic robustness protects against uncertainty in the opponents’ behavior and, surprisingly, results in higher equilibrium payoffs for all players – an effect we refer to as coordination via robustification.

Friday 21 March 2025 - Anand Rao Tadipatri (Cambridge)

Formal proofs and generalization

It has been known for over a century that it is possible to formally encode mathematical proofs in a logical foundation in principle. Softwares known as interactive theorem provers or proof assistants now make this possible in practice.

This talk will begin with an introduction to interactive theorem provers and their capabilities, with examples primarily drawn from the Lean theorem prover.

Later on in the talk, I will mention some possibilities that interactive theorem provers enable beyond proof verification, with a particular focus on proof generalization.  

Specifically, I will present an algorithm that takes in a mathematical theorem with its proof (like the proof of irrationality of √2), along with a constant to generalize (such as 2), and produces a more general theorem (that √p is irrational for any prime p) by determining the specific properties of the constant that were used in the proof and generalizing them.

I will conclude with some speculations about how such tools may be incorporated into the workflow of research mathematicians.

Thursday 20 March 2025 - Alex Black (ETH)

Shadows of Polytopes

Linear optimization corresponds to finding the highest point in a direction on a polytope. This is sufficient for when is only interested in optimizing a single objective. For multiple objectives as appears in parametric, multicriteria, and low rank convex optimization, the problem requires a new geometric interpretation. Namely, one looks at all candidate solutions in the linear span of a set of linear objectives, and these solutions correspond to the vertices of a projection of a polytope. Furthermore, the run-time of optimization algorithms for these problems is, up to small polynomial factors, at most the number of vertices of the projection. In this talk, I will survey results regarding estimating the number of vertices of two-dimensional projections of polytopes in various settings and discuss related open problems.

Thursday 13 March 2025 - Panos Giannopoulos (City, University of London)

Searching in \(\mathbb{R}^d\) with predictions

Searching for a target positioned at some unknown location in some region is a classic search game problem that has been well-studied in both fields of Computational Geometry and Operations Research. In this talk, we will consider the problem of searching for a target point in \(\mathbb{R}^d\) when additional information regarding the position of the target is available in the form of \(c\)-predictions -- approximate distances to the target \(t\): for each point \(p\) that the searcher visits, a value \(\lambda(p)\) is obtained such that \(|pt| \leq \lambda(p) \leq c |pt|\), according to some unknown function \(\lambda\) and where \(c\) is a fixed (possibly unknown) constant.

I will show some simple search strategies that achieve constant competitive ratio (i.e., length of the path produced over the Euclidean distance of the target from the origin) as a function of \(c\) and \(d\). The strategies use metric \(\epsilon\)-nets and simple exponential search and work even if \(c\) is unknown.  

We will also see a lower bound of the competitive ratio of any deterministic search strategy in \(\mathbb{R}^d\) with \(c\)-predictions. This bound uses again \(\epsilon\)-nets and some techniques for Euclidean TSP with Neighbourhoods.

Wednesday 12 March 2025 - Domagoj Bradač (ETH Zürich)

Unique subgraphs are rare

A folklore result attributed to Pólya states that there are \(1 + o(1))2^{\binom{n}{2}}/n!\) non-isomorphic graphs on \(n\) vertices. Given two graphs \(G\) and \(H\), we say that \(G\) is a unique subgraph of \(H\) if \(H\) contains exactly one subgraph isomorphic to \(G\). For an \(n-\)-vertex graph \(H\) , let \(f(H)\) be the number of non-isomorphic unique subgraphs of \(H\) divided by \(2^{\binom{n}{2}}/n!\) and let \(f(n)\) denote the maximum of \(f(H)\) over all graphs \(H\) on \(n\) vertices. In 1975, Erdős asked whether there exists \(\delta>0\) such that \(f(n)>\delta\) for all \(n\) and offered \(\$100\) for a proof and \(\$25\) for a disproof, indicating he does not believe this to be true. We verify Erd\H{o}s' intuition by showing that \(f(n)\rightarrow 0\) as \(n\) tends to infinity, i.e. no graph on \(n\) vertices contains a constant proportion of all graphs on \(n\) vertices as unique subgraphs.

Friday 7 March 2025 - Jasmin Katz (LSE)

A minimum degree condition for monochromatic trees in 2-edge coloured graphs

For any integer \(n\), it is easy to find a 2-edge colouring of the complete graph on \(2n-2\) vertices which doesn’t contain a monochromatic copy of every tree on \(n\) vertices. However, the ErdÅ‘s-Sós conjecture implies that for \(N = 2n-1\), any 2-edge colouring of \(K_N\) contains a monochromatic copy of every tree on \(n\) vertices. We show that any 2-edge coloured graph on \(N = 2n-1\) vertices with minimum degree at least \(3N/4\) contains a monochromatic copy of every bounded-degree tree on \(n\) vertices. 

This is a joint work with Matías Pavez-Signé and Jozef Skokan.

Thursday 6 March 2025 - Yehuda "John" Levy (University of Glasgow)

Small Player Robustness 

We introduce a concept of stability of a Nash equilibrium, or of a set of Nash equilibria, to the addition of small players, i.e., players who only have a small effect on the original players. We coin this concept `small player robustness' or `uniform small player robustness', depending on the specific condition required. We show that either of these conditions is equivalent to the essentiality condition of Govindan and Wilson (2005). Our techniques draw heavily on tools from semialgebraic geometry, as well as on previously developed game-theoretical tools.

Friday 28 February 2025 -Olha Silina (Carnegie Mellon University)

Strongly connected orientations and integer lattices

Let \(D=(V,A)\) be a digraph whose underlying graph is 2-edge-connected, and let P be the polytope whose vertices are the incidence vectors of arc sets whose reversal makes D strongly connected.

We study the lattice theoretic properties of the integer points contained in a proper face F of P not contained in \({x:x_a=i}\) for any \(a∈A, i∈{0,1}\). We prove under a mild necessary condition that \(F∩{0,1}^A\) contains an integral basis B, i.e., B is linearly independent, and any integral vector in the linear hull of F is an integral linear combination of B.

In proving the result, we develop a theory similar to Matching Theory for degree-constrained dijoins in bipartite digraphs. Our result has consequences for head-disjoint strong orientations in hypergraphs, and also to a famous conjecture by Woodall that the minimum size of a dicut of D, say τ, is equal to the maximum number of disjoint dijoins.

This is a joint work with Ahmad Abdi, Gerard Cornuejols, and Siyue Liu.

Thursday 27 February 2025 - Yelena Yuditsky (Université libre de Bruxelles)

Integer programs with nearly totally unimodular matrices: the cographic case

It is a notorious open question whether integer programs (IPs), with an integer coefficient matrix M whose subdeterminants are all bounded by a constant in absolute value, can be solved in polynomial time. We answer this question in the affirmative if we further require that, by removing a constant number of rows and columns from M, one obtains the transpose of a network matrix. We achieve our result in two main steps, the first related to the theory of IPs and the second related to graph minor theory. In this talk, I will present the ideas behind some of the results we obtain in either of those steps.

This is a joint work with M. Aprile, S. Fiorini, G. Joret,  S. Kober, M.T. Seweryn and S. Weltge. 

 Friday 21 February 2025 -Zahra Parsaeian (Freiburg)

Laminar Matroid Secretary: Greedy Strikes Back

We show that a simple greedy algorithm is 4.75-competitive for the Laminar Matroid Secretary Problem, improving the \( 33 \approx 5.1963\sqrt{3} \approx 5.19633 \approx 5.196-\) competitive algorithm based on the forbidden sets technique (Soto, Turkieltaub, and Verdugo, 2018).

Thursday 20 February 2025 - Linda Cook (University of Amsterdam)

200,000 colors suffice (for t-perfect graphs)

Perfect graphs can be described as the graphs whose stable set polytopes are defined by their non-negativity and clique inequalities. In 1975, V. Chvátal defined an analogous class called t-perfect graphs, which are the graphs whose stable set polytopes are defined by their non-negativity, edge inequalities, and odd circuit inequalities. We show that t-perfect graphs are 200,000-colourable. This is the first finite bound on the chromatic number of t-perfect graphs, and answers a question of B. Shepherd from 1995.

This bound is probably not tight;  M. Laurent and P. Seymour gave an example of a t-perfect graph requiring four colors in the 1990's and it is open whether all t-perfect graphs are 4-colorable. Our proof is mainly graph theoretic.

Joint work with: Maria Chudnovsky (Princeton), James Davies (Cambridge), Sang-il Oum (IBS DIMAG), Jane Tan (Oxford). Available at: https://arxiv.org/abs/2412.17735

Friday 14 February 2025 - Kyriakos Katsamaktsis (UCL)

Ascending subgraph decomposition

We prove for large graphs the following conjecture of Alavi, Boals Chartrand, Erdős and Oellermann from 1987: any graph with \((m+1)m/2\) edges can be decomposed into graphs \(G_1,...,G_m\) such that \(G_i\) has exactly i edges and is isomorphic to a subgraph of \(G_{i+1}\). This is joint work with Shoham Letzter, Alexey Pokrovskiy and Benny Sudakov.

Thursday 13 February 2025 - Leo Versteegen (LSE)

An exploration of the balance game

The balance game is played on a graph G by two players, Admirable (A) and Impish (I), who take turns claiming vertices of G. The game ends once all vertices have been claimed, at which point the ‘score’ is computed as the number of edges whose incident vertices have been claimed by different players minus the number of edges whose incident vertices have been claimed by the same player. The goal of (A) is to minimize this quantity while (I) attempts to maximize it. Let \(b^A(G)\) be the score of a game in which (A) made the first move, and both players played optimally. We will establish general bounds on \(b^A(G)\) as well as discuss the behaviour of \(b^A(G)\) for specific classes for graphs such as paths and random graphs.

Based on joint work with Paul Dorbec, Michael Henning, and Zsolt Tuza.

Friday 7 February 2025 - Lawrence Hollom (Cambridge)

Double-jump phase transitions for the reverse Littlewood-Offord problem

An old conjecture of Erdős asks, given n unit vectors in dimension d, for a lower bound on the probability that a random signed sum of these unit vectors (taken uniformly at random from the \(2^n\) possibilities) lies close to the origin. This conjecture has been corrected, solved, rediscovered and generalised over the years, and so it might appear that there is little more to say about it. However, in this talk we discuss adding a parity condition to n, a condition which both adds significant depth to the setting and gives new life to Erdős's original conjecture, giving rise to a wealth of interesting results and wide-open problems. We will also say a few words about optimal constructions in the original setting of Erdős, about which much also remains mysterious

Thursday 6 February 2025 - Matthias Englert (Warwick)

Exploiting gradient flow convergence properties to reconstruct training data from neural networks

There can be many different weights, all of which result in a network that correctly classifies the training data. An important question is to understand the implicit bias of gradient flow (that is, gradient descent with an infinitesimally small step size), i.e. which of these solutions the gradient flow will converge to. Work by Lyu and Li [ICLR 2020] and Ji and Telgarsky [NeurIPS 2020] shows that, under certain conditions, when optimising the binary cross-entropy loss of a homogeneous neural network using gradient flow, the direction of the network weights converges to a Karush-Kuhn-Tucker (KKT) point of the maximum margin problem.

Haim et al. [NeurIPS 2022] exploit this implicit bias of gradient flow to reconstruct part of the training data from the network weights of the final trained network.

 We will briefly discuss this theoretical background of the implicit bias of gradient flow and how it was used by Haim et al. to experimentally reconstruct part of the training data. Finally, we will show how diffusion models can be used to improve the quality of the reconstructions obtained by Haim et al.

 (joint work with Ranko Lazic and Avi Semler)

Friday 31 January 2025 - Tamás Schwarcz (LSE)

Problems on group-labeled matroid bases

Several combinatorial optimization problems involve additional constraints, such as parity, congruency, and exact-weight constraints. These constraints are subsumed by group-label constraints defined as follows: given a labeling of a ground set to an abelian group and a prescribed set F of forbidden labels, we define a subset of the ground set F-avoiding if the sum of the labels of its elements is not in F.

 We study the problems of finding F-avoiding bases and common bases of two matroids. For the single matroid case, finding an F-avoiding basis is hard if F is part of the input, while for a fixed |F|, we show the polynomial solvability of the problem in several cases, including matroids representable over fixed, finite fields. For two matroids, we show that the complexity of finding an F-avoiding common basis depends on the group if F consists of a single forbidden label, while the problem is hard for any nontrivial fixed group if we allow at most two forbidden labels.

Based on joint work with F. Hörsch, A. Imolay, R. Mizutani, and T. Oki.

Thursday 30 January 2025 - Daniel Kadnikov (Alan Turing Institute)

Informational Aspects of Strategic Forms

In the first part of the talk, we revisit two traditional game-theoretic models: the extensive tree form (ETF) and strategic form. The latter (explicitly) provides information only about atemporal strategies and the outcomes these strategies induce. The former specifies information sets -- what players know -- and local choices at the information sets -- what players do. The strategic assignments approach -- the classical method to generate the strategic form of a given ETF -- specifies local decisions at every information set and finds continuous paths from the root to the leaves. As we show, the lesser-known powers approach at once yields the same strategic forms while offering a computational improvement.

 In the second part of the talk, we go in the opposite direction and explore which aspects of the original decision structure are recoverable from strategic forms. In doing this, we do not start from scratch as the same question was addressed by Mailath, Samuelson, and Swinkels [Econometrica 1993; JET 1994]. The authors introduced and studied the concept of the so-called normal form information sets. We then show how leveraging the powers approach sheds light on the intrinsic geometry of strategic forms and offers an exponential improvement in detecting normal form information sets.

This is joint work with Rahul Savani and Philipp Wichardt.

Friday 24 January 2025 - Jun Yan (Warwick)

Ramsey numbers of trees

Given a graph \(G\), the Ramsey number \(R(G)\) is defined to be the smallest \(N\) such that any red/blue colouring of the complete graph \(K_N\) contains a monochromatic copy of \(G\). For a tree \(T\) whose bipartition classes have sizes \(t_1\geq t_2\), two simple constructions shows that \(R(T)\geq R_B(T):=\max\{t_1+2t_2,2t_1\}-1\), and Burr conjectured in 1974 that \(R(T)=R_B(T)\). 

It has been shown that Burr’s conjecture is false for certain trees called the double stars, though all of these known counterexamples have large maximum degrees. In 2002, Haxell, Łuczak and Tingley showed that an approximate version of Burr’s conjecture is true if one imposes a maximum degree condition. In an upcoming joint work with Richard Montgomery and Matías Pavez-Signé, we prove that Burr’s conjecture is true for all trees with up to small linear maximum degrees. That is, there exists \(c>0\) such that for all trees \(T\) on \(n\) vertices with \(\Delta(T)\leq cn\), \(R(T)=R_B(T)\).

Thursday 23 January 2025 - Adva Mond (KCL)

Maker-Breaker percolation games on a random board

The (m,b) Maker-Breaker percolation game on an infinite graph G is played in the following way. Maker starts by choosing a vertex and naming it the origin. Maker and Breaker then alternately claim m and b unclaimed edges of G, respectively. Breaker wins if the component containing the origin becomes finite when his edges are deleted from G. Maker wins if she can indefinitely avoid a win of Breaker.

 We will discuss the state of the art for this game, with special attention to the case where G is the result of bond percolation on the square lattice. In particular, we will show how this game can be analysed using tools from bootstrap percolation.

This is joint work with Vojtěch Dvořák and Victor Souza.

Friday 13 December - Brian Hearn (LSE) 

Reconstructing graphs from their colouring graphs

Given a graph \(G\) and a natural number \(k\), the \(k\)-colouring graph of \(G\) (or the reconfiguration graph of the \(k\)-colourings of \(G\)) is the (unlabelled) graph whose vertex set is the set of proper \(k\)-colourings of \(G\), and whose edge set is the set of pairs of proper k-colourings of \(G\) which differ at exactly one vertex of \(G\).
In January 2024, Asgarli, Krehbiel, Levinson, and Russell conjectured that for every graph \(G\), there exists some finite collection of colouring graphs of \(G\) which uniquely determines \(G\) (up to isomorphism). In March 2024, Hogan, Scott, Tamitegama, and Tan confirmed this conjecture by proving that any graph G is uniquely determined (up to isomorphism) by its \(k\)-colouring graph whenever \(k > 5|G|^2\). We adapt this proof to show that the same is true for any \(k\) larger than the chromatic number of \(G\). This bound is optimal, in the sense that for any natural number \(χ\), there exist infinite families of graphs with chromatic number χ which all have the same χ-colouring graph.

Wednesday 4 December - Ruth Heller (Tel-Aviv University)**n.b. this will take place at 3:30pm**

Selecting informative conformal prediction sets with false coverage rate control

Gazin, U., Heller, R., Marandon, A. and Roquain, E.

In supervised learning, including regression and classification, conformal methods provide  prediction sets for the outcome/label with finite sample coverage for any machine learning predictors. We consider here the case where such prediction sets come after a selection process. The selection process requires that the selected prediction sets be `informative' in a well defined sense. We consider both the classification and regression settings where the analyst may consider as informative only the sample with prediction sets small enough, excluding null values, or obeying other appropriate `monotone' constraints. We develop a unified framework for building such informative conformal prediction sets while controlling the false coverage rate (FCR) on the selected sample. While conformal prediction sets after selection have been the focus of much recent literature in the field, the new introduced procedures, called InfoSP and InfoSCOP, are to our knowledge the first ones providing FCR control for informative prediction sets. We show the usefulness of our resulting procedures on real and simulated data. 

Thursday 5 December - Thu Dang (Lancaster University) 

On matchings, T-joins, and arc routing in road networks

Matchings and T-joins are fundamental and much-studied concepts in graph theory and combinatorial optimization. One important application of matchings and T-joins is in the computation of strong lower bounds for arc routing problems (ARPs). An ARP is a special kind of vehicle routing problem, in which the demands are located along edges or arcs, rather than at nodes. We point out that the literature on applying matchings and T-joins to ARPs does not fully exploit the structure of real-life road networks. We propose some ways to exploit this structure. Computational results show significant running time improvements, without deteriorating the quality of the lower bounds.

Friday 29 November - Matteo Bettini (Cambridge)

Controlling Behavioral Diversity in Multi-Agent Reinforcement Learning

Diversity has been shown to be key to collective intelligence in natural systems. Despite this, current Multi-Agent Reinforcement Learning (MARL) approaches enforce behavioral homogeneity (to boost efficiency) or blindly promote behavioral diversity via intrinsic rewards or additional loss functions, effectively changing the learning objective and lacking a principled measure for it.

In this context, I will present some work carried out during my PhD that deals with the question of how to control the strategy diversity of a learning multi-agent system. 

I will introduce Diversity Control (DiCo), a method able to control diversity to an exact value of a given metric by representing policies as the sum of a parameter-shared component and dynamically scaled per-agent components. By applying constraints directly to the policy architecture, DiCo leaves the learning objective unchanged, enabling its applicability to any actor-critic MARL algorithm. We theoretically prove that DiCo achieves the desired diversity, and we provide several experiments, both in cooperative and competitive tasks, that show how DiCo can be employed as a novel paradigm to increase performance and sample efficiency in MARL, as well as lead to the emergence of novel diverse policies. Multimedia results are available on the project’s website.

Thursday 28 November - Matías Pavez-Signé (U Chile) 

Ramsey problems for trees and related questions

The Ramsey number of a pair of graphs \(G,H\), denoted by \(R(G,H)\), is the minimum number n so that every red/blue edge-colouring of the n-vertex complete graph either contains a red copy of \(G\0 or a blue copy of \(H\). In this talk, I will survey what is known about \(R(G,H)\) when at least one of the graphs is a tree, and discuss generalisations of this problem such as hypergraphs variants, or when a sparser graph replaces the edge-coloured complete graph.

Friday 22 November - Freddie Illingworth (UCL) 

Colouring hypergraphs and their intersection spectrum

The chromatic number of a graph is the smallest number of colours needed to colour its vertices such that adjacent vertices receive different colours. There are various ways one might generalise this notion to hypergraphs (graphs where we allow edges to contain any number of vertices). The chromatic number, ꭓ(), of a hypergraph is usually defined as the smallest number of colours needed to colour the vertices of so that every edge receives at least two colours. The intersection spectrum, (), is the set of all intersection sizes \(|e \cap f|\) of distinct edges \(|e \cap f|\). It is not obvious that the notions of chromatic number and intersection spectrum should be related but, in 1975, Erdős and Lovász observed that if \(ꭓ() > 2\), then \(1 ∈ ()\), and if \(ꭓ() > 3, then 0 ∈ ()\).

I will survey some open problems and discuss recent work with Kevin Hendrey, Nina Kamčev, and Jane Tan where we generalise the second observation to colourings where all edges receive at least c colours, resolving a problem of Blais, Weinstein, and Yoshida.

Wednesday 20 November - Imre Leader (Cambridge)**n.b. this will take place at 3:30pm**

Partial Shuffles by Transpositions

Suppose we generate a random permutation by making a sequence of transpositions: we have a fixed sequence of transpositions and we apply each with a certain probability. How many transpositions do we need if we are to obtain a uniform random permutation? And what happens if we ask only that each element has the same probability of being in each position? We will discuss these and several related questions.

(Joint work with Barnabas Janzer and Robert Johnson.)

Friday 15 November - Cameron Strachan (LSE)

Isoperimetry of the two smallest distances on the triangular lattice

Consider an \(n-vertex\) graph whose vertex set is a subset of the triangular lattice. We connect two vertices by an edge if their distance is \(1\) or \(\sqrt{3}\). In this talk, I present a proof of the maximum number of edges such a graph can have for each value of \(n\).

Thursday 14 November - Mehdi Makhul (LSE) 

On the Orchard type problems in higher dimensions

Let P be a set of n points in the plane not all on a line. The orchard planting problem asks for the maximum number of lines through exactly three points of P. Green and Tao showed that the maximum possible number for an n element set is \(⌊n(n − 3)/6⌋ + 1\). Lin and Swanepoel also investigated a generalization of the orchard problem in higher dimensions. Namely, if P is a set of n points in the d dimension, they found an upper bound for the maximum number of hyperplanes through exactly d+1 points of P. In this talk, we will see that if P is a set that is contained in an algebraic curve C of degree r and determines \(cn^{d}\) hyperplanes through exactly d+1 points of P, then r=d+1, and C is the intersection of \([(d+1)(d-2)]/2\) quadric hypersurfaces.

Friday 8 November - Camila Zarate-Gueren (University of Birmingham) 

Colour-bias perfect matchings in hypergraphs

Given a \(k-uniform\) hypergraph H on n vertices with an r-colouring of its edges, we look for a minimum l-degree condition that guarantees the existence of a perfect matching in H that has more than \(n/rk\) edges in one colour. We call this a colour-bias perfect matching.

For 2-coloured graphs, a result of Balogh, Csaba, Jing and Pluhár yields the minimum degree threshold that ensures a perfect matching of significant colour-bias. In this talk, I will present an analogous of this result for k-uniform hypergraphs. More precisely, for each \(1 \leq l < k\) and \(r \geq 2\) we determined the minimum l-degree threshold that forces a perfect matching of significant colour-bias in an r-edge-coloured k-uniform hypergraph.

Wednesday 6 November - Sujoy Bhore (IIT Bombay)**n.b. this will take place at 3:30pm**

Sketching and Uncertainty: Through the Geometric Lens

In various applications, such as machine learning, robotics, and social choice theory, the input data, often represented geometrically as points in a finite metric space, can be massive in size. Efficient processing and representation of such large datasets is crucial. Sketching is a fundamental technique used to compress a large dataset into a smaller dataset while approximately preserving key properties. Among the various sketching mechanisms, two of the most important and well-studied structures are spanners and tree covers. In the first part of this talk, I will discuss recent advances in geometric sketching methods.

Traditional algorithmic models assume complete knowledge of the input in advance; however, this assumption often fails in dynamic settings, where inputs evolve over time. In such cases, algorithms must not only compute efficiently at each stage but also maintain high-quality solutions as the input undergoes updates. In the second part of the talk, I will explore the dynamic aspects of geometric sketching and discuss strategies for adapting algorithms to handle these challenges effectively.

Friday 1 November - Marcelo Campos (University of Cambridge)

Upper bounds for multicolour Ramsey numbers

The r-colour Ramsey number \(R_r(k)\) is the minimum \(n\in \mathbb{N}\) such that every r-colouring of the edges of the complete graph \(K_n\) on n vertices contains a monochromatic copy of \(K_k\). In this talk I will show that for each fixed \(r\geq 2\), that\(R_r(k)\leq \exp(-\delta k)r^{rk}\) for some constant \(\delta=\delta(r)>0\) and all sufficiently large \(k\in \mathbb{N}\). For each \(r\geq 3\), this is the first exponential improvement over the upper bound of Erdős and Szekeres from 1935. The proof uses a new geometric lemma and a new algorithm to find almost optimal monochromatic 'books'.

This is joint work with Paul Balister, Béla Bollobás, Simon Griffiths, Eoin Hurley, Robert Morris, Julian Sahasrabudhe and Marius Tiba.

Thursday 31 October - Eilon Solan (Tel Aviv University) 

Bayesian games with incomplete information

In Bayesian games with general type spaces, a Bayesian equilibrium need not exist. We study Bayesian games with nested information, that is, each player i knows her own type, as well as the type of players \(i+1, i+2, ..., n\). We show that in this case, a Bayesian equilibrium exists under weak conditions.

This is based on joint work with Royi Jacobovic and John Levy.

Friday 25 October - Ella Williams (University College London) 

Covering vertices with monochromatic paths

In 1995, Erdős and Gyárfás proved that in every 2-edge-coloured complete graph on \(n\) vertices, there exists a collection of \(2\sqrt{n}\) monochromatic paths, all of the same colour, which cover the entire vertex set. They conjectured that it is possible to replace \(2\sqrt{n}\) by \(\sqrt{n}\). We prove this to be true for all sufficiently large \(n\). This is based on joint work with Alexey Pokrovskiy and Leo Versteegen.

Thursday 24 October - Paul Bastide (TU Delft)

Reconstruction with a distance oracle

Given a connected graph \(G = (V, E)\) where \(V\) is known and \(E\) is hidden, we are provided access to an oracle that can answer the following queries: given \(u\), \(v\) in \(V\), the oracle returns the distance of the shortest path between \(u\) and \(v\) in \(G\). This setup naturally arises in network recovery and phylogenetic reconstruction problems. This talk explores what is known about the query complexity for various classes of graphs and recent developments toward the main open conjecture in the area: is it possible to reconstruct graphs of bounded degree using n*polylog(n) queries, where n denotes the size of \(V\)?

Friday 18 October - Desmond Chan (King's College London)

Asymptotic Extinction in Large Coordination Games

We study the exploration-exploitation tradeoff in multiplayer, normal form games under Q-Learning, a common learning framework for multi-agent reinforcement learning. Q-Learning is known to have two potential shortcomings: 1) non-convergence and 2) equilibrium selection problem, where there are multiple equilibria and which equilibria learning agents end up in are dependent on initial conditions.   In this talk, we will study the typical behaviours that arises from Q-Learning over normal form games in the large actions and many player limit. Payoff matrices randomly generated, players are initialised random strategise and the emerging learning dynamical behaviour is studied. In the large action and many player limit, we show the critical exploration rate required for convergence to a unique fixed point in a zero-sum game tends to half that of an identical payoff potential game. Alongside this, we provide a structural result that the unique fixed point of Q-Learning tends to the boundary of the simplex of the action space in coordination games as the numbers of action increases, a phenomenon we term asymptotic extinction, where a constant fraction of the actions are played with zero probability at a rate \(o(1/N)\) for an \(N\)-action game.

Thursday 17 October - Liana Yepremyan (Emory University)

Counterexample to Babai's lonely colour conjecture

Motivated by colouring minimal Cayley graphs, in 1978, Babai conjectured that no-lonely-colour graphs have bounded chromatic number. We disprove this in a strong sense by constructing graphs of arbitrarily large girth and chromatic number that have a proper edge-colouring in which each cycle contains no colour exactly once. Joint work with James Davies and Meike Hatzel.

Thursday 10 October - Nora Frankl (Open University)

On forbidden configurations in point-line incidence graphs

The celebrated Szemeredi-Trotter theorem states that the maximum number of incidences between n points and n lines in the plane is \(O(n^{4/3})\), which is asymptotically tight. Solymosi conjectured that this bound drops to \(o(n^{4/3})\) if we exclude subconfigurations isomorphic to any fixed point-line configuration. We describe a construction disproving this conjecture. On the other hand, we prove new upper bounds on the number of incidences for configurations that avoid certain subconfigurations. Joint work with Martin Balko.

Thursday 3 October - Bassel Tarbush (University of Oxford)

Game Connectivity and Adaptive Dynamics

We analyse the typical structure of games in terms of the connectivity properties of their best-response graphs. Our central result shows that almost every game that is ‘generic’ (without indifferences) and has a pure Nash equilibrium and a ‘large’ number of players is connected, meaning that every action profile that is not a pure Nash equilibrium can reach every pure Nash equilibrium via best-response paths. This has important implications for dynamics in games. In particular, we show that there are simple, uncoupled, adaptive dynamics for which period-by-period play converges almost surely to a pure Nash equilibrium in almost every large generic game that has one (which contrasts with the known fact that there is no such dynamic that leads almost surely to a pure Nash equilibrium in every generic game that has one). We build on recent results in probabilistic combinatorics for our characterisation of game connectivity. This is joint work with Tom Johnston, Michael Savery, and Alex Scott.

Friday 20 September - Vipul Arora (School of Computing, National University of Singapore)

Low Degree Testing Over the Reals

We study the problem of testing whether a function \(f\):

\(reals^n \to \reals\) is a polynomial of degree at most $d$ in the distribution-free testing model. Here, the distance between functions is measured with respect to an unknown distribution \(D\) over \(\reals^n\) from which we can draw samples. In contrast to previous work, we do not assume that \(D\) has finite support.

We design a tester that given query access to \(f\), and sample access to \(D\), makes \(\poly(d/\eps)\) many queries to \(f\), accepts with probability \(1\) if \(f\) is a polynomial of degree \(d\), and rejects with probability at least \(2/3\) if every degree-\(d\) polynomial \(P\) disagrees with \(f\) on a set of mass at least \(\eps\) with respect to \(D\).