Seminar and PhD Seminar on Combinatorics, Games and Optimisation

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\).

Thursday 18 July - Ádám Sagmeister (Renyi Institute / University of Szeged)

Some inequalities on reduced convex bodies in the hyperbolic space

The concept of reducedness was defined by Heil in 1978 in hope of tackling volume minimizing problems concerning the minimal width of the body. A convex body is called reduced, if for any different convex body that is contained within, the minimal width is strictly smaller. At first, the definition suggests that reduced bodies are some kind of dual of bodies of constant width, but in fact it is a broader family. A classical result of Pál from 1921 states that the regular triangle minimizes the area if the minimal width is fixed. Lassak conjectured that the area among reduced bodies of a fixed minimal width is maximized by the circle and the quarter of a disk, and he proved that all reduced polygons have a smaller area. Similar investigations have been made on the sphere, but the concept of reducedness in the hyperbolic space is very recent as the formerly known hyperbolic width functions did not make a good fit for this purpose. After introducing a new concept of hyperbolic width by Lassak, we will discuss some unexpected facts on hyperbolic reduced bodies including Pál's problem, we will see how hyperbolic reduced polytopes can differ from Euclidean or spherical ones, and we will answer three of Lassak's recent questions. This talk is partially based on joint works with Károly Jr. Böröczky, András Csépai and Ansgar Freye.

Friday 19 July - Joonkyung Lee (Yonsei University)

Around the positive graph conjecture

A graph $H$ is said to be positive if the homomorphism density $t_H(G)$ is non-negative for all weighted graphs $G$. The positive graph conjecture proposes a characterisation of such graphs, saying that a graph is positive if and only if it is symmetric, in the sense that it is formed by gluing two copies of some subgraph along an independent set. We prove several results relating to this conjecture. First, we make progress towards the conjecture itself by showing that any connected positive graph must have a vertex of even degree. We then make use of this result to identify some new counterexamples to the analogue of Sidorenko’s conjecture for hypergraphs. In particular, we show that, for $r$ odd, every $r$-uniform tight cycle is a counterexample, generalising a recent result of Conlon, Lee and Sidorenko that dealt with the case $r = 3$. Finally, we relate the positive graph conjecture to the emerging study of graph codes by showing that any positive graph has vanishing graph code density, thereby improving a result of Alon who proved the same result for symmetric graphs. Our proofs make use of a variety of tools and techniques, including the properties of independence polynomials, hypergraph quasirandomness and discrete Fourier analysis. Joint work with David Conlon and Leo Versteegen.

Tuesday 25 June - Naveen Garg (Indian Institute of Technology, Delhi) **2.00pm start**

Peer to Peer File Sharing

I will introduce a problem of file sharing among peers which are connected to a common core network through links of differing upload and download capacities/bandwidths. The objective is to share a file, initially residing on one of the peers, with all other peers in the least time possible. A peer can start sending the file to another peer only after it has received the entire file. Peers can simultaneously send/receive parts of a file to/from multiple peers. In the talk I will show a novel integer program for this problem and use the optimum solution to the LP-relaxation to give a schedule with makespan 2OPT+P where P is the time required by the slowest peer to download the file.  I will also discuss a “non-migratory” variant of the problem and show how to obtain a constant approximation algorithm. This is joint work with Thomas Erlebach (U. Durham), Sukriti Gupta (alphaGrep) and Amitabh Trehan (U. Durham).

Friday 21 June - Debmalya Bandyopadhyay (University of Birmingham)

Monochromatic Tight Cycle Partitions in Edge-Coloured Complete k-Graphs

Abstract

Thursday 20 June - Jacques Verstraete (University of California, San Diego)

Recent Progress in Ramsey Theory

Jacques Verstraete Abstract - Recent Progress in Ramsey Theory

Friday 14 June - Diogo Pires (City, University of London)

Evolutionary models of cooperative behaviour: from simple to complex interactions

Evolutionary models are often used to understand the emergence of cooperative behaviour when individuals face social dilemmas. We start from the simplest evolutionary game theory models and uncover the counter-intuitive impact of the size of a finite well-mixed population on the stability of emerging strategies. However, real social systems are characterized by more complex interactions between individuals, often involving structure and mobility. To incorporate these features into game theoretic modelling, we consider a framework under which interacting groups arise from the encounters of individuals moving on spatial networks. In populations restricted to independent and local movement, strong community ties emerge. In this case, multiplayer cooperation is sustained if the benefits of in-group interactions outperform the pitfalls of between-group spread, which can be translated into simple conditions. We further consider movement conditional on satisfaction with past interactions. This highlights a new mechanism involving the successful co-evolution of high mobility strategies with cooperative behaviour under broader contexts and for a larger set of evolutionary dynamics.

Wednesday 12 June - Benny Sudakov (ETH Zurich)

SDP, MaxCut, Discrepancy and Log-Rank-Conjecture

Semidefinite programming (SDP) is a powerful method used in many important approximation algorithms. In this talk, I discuss a different aspect of SDP and demonstrate how it can be employed to offer concise proofs for several well-known and new estimates related to MaxCut, as well as the discrepancy of graphs and matrices. I also explain how the discrepancy result leads to an improvement in Lovett’s best-known upper bound on the log-rank conjecture.

Friday 7 June - Luke Collins (UCL)

Chords in Longest Cycles

lc-abstract

Friday 31 May - Tom Lidbetter (Rutgers University)

New Results On a Classic Search Game

We consider a search game introduced in 1963, in which a target is hidden in one of n boxes. If a given box contains the target, each time that box is searched, the target is independently found with some fixed "success probability", which may depend on the box. A Hider chooses which box to hide the target in, and a Searcher simultaneously chooses an infinite sequence of boxes specifying the order in which to search them. The payoff of the game is number of boxes opened before the target is found. The Hider is the maximizer and the Searcher is the minimizer. Remarkably little is known about this game, even for the case n=2. We discuss new algorithms for finding a solution to the game in the more general setting where each box takes a given amount of time to search. We also give a closed form solution for the case of equal detection probabilities, and we ask the question: when is there an optimal pure strategy solution for the Searcher?

Thursday 30 May - Arsenii Sagdeev (MIPT, Renyi Insititute)

Canonical Theorems in Euclidean Ramsey Theory

We prove the following two results in Euclidean Ramsey theory. First, every coloring of the space, regardless of the number of colors used, contains either a monochromatic or a rainbow congruent copy of each acute triangle. Second, every coloring of R^n contains either a monochromatic or a rainbow congruent copy of an m-dimensional unit hypercube, provided that n is sufficiently large in terms of m. Joint work with Panna Gehér and Géza Tóth.

Thursday 23 May - Merve Bodur (University of Edinburgh)

Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach

The multi-depot vehicle scheduling problem (MDVSP) is a principal planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. We propose an exact branch-and-cut (B&C) scheme to solve our CCP model. We present several cut-generation procedures that exploit the underlying problem structure and analyze the relationship between the obtained cut families. Additionally, we design a Lagrangian-based heuristic to handle large-scale instances reflective of real-world transit operations. Our approach partitions the set of trips, each subset leading to a subproblem that can be efficiently solved with our B&C algorithm, and then employs a procedure to combine the subproblem solutions to create a vehicle schedule that satisfies all the planning constraints of the MDVSP. Our empirical evaluation demonstrates the superiority of our stochastic variant in achieving cost-effective schedules with reliable service guarantees compared to alternatives commonly used by practitioners, as well as the computational benefits of our methodologies. 

Wednesday 22 May - David Steurer (ETH Zurich)

**Time changed to 1.30pm start**

Private Block Model and Graphon Estimation Via Sum-of-Squares

We develop differentially-private algorithms for parameter-learning stochastic block models and for graphon estimation.
They are the first to achieve pure node-differential privacy in polynomial running time for any constant number of blocks.
Their statistical utility guarantees match those of the previous best information-theoretic node-private mechanisms for these problems that have exponential running time.
The algorithm is based on a score function defined in terms of a sum-of-squares relaxation whose level depends on the number of blocks. The key ingredients of our results are
(1) a characterization of the distance between two block graphons in terms of a quadratic optimization over the polytope of doubly stochastic matrices,
(2) a general sum-of-squares convergence result for polynomial optimization over arbitrary polytopes, and
(3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.
This talk is based on a joint work with Hongjie Chen, Jingqiu Ding, Tommaso D'Orsi, Yiding Hua, Chih-Hung Liu, and David Steurer.

Thursday 16 May - Anderson Ang (University of Southampton)

Some topics about NNNNNNNN… optimization

This is a two-part talk on some topics in continuous optimization for machine learning, based on my recent joint works with many other people. Part 1 is on Nonnegative Matrix Factorization (NMF). We first give a short review of NMF based on conic and convex geometry, then we present our current work on sum-of-norms NMF that can empirically find the nonnegative rank of the data matrix. Being a Non-convex Non-smooth Non-separable Non-proximable problem, we present a solution strategy based on proximal averaging by the Moreau envelope for solving this NMF problem. Experiment results showcase this NMF model is able to solve rank-deficient NMF problems without knowing the nonnegative rank of the matrix. Part 2 is on Proximal Gradient Descent (PGD). We present our work on a multigrid accelerated PGD that is capable to solve Non-smooth strongly-convex optimization problem with convergence guarantee. In short, the whole idea of multigrid PGD is to collapse the Minkowski sum of subdifferentials into a singleton, based on a newly introduced adaptive restriction operator. On a PDE-induced minimization problem that is strongly-convex-but-unknown-modulus and Lipschitz-smooth-but-unknown-global-Lipschitz-constant, we showcase the proposed method is fast.

Keywords: Non-convex, Non-negative, Non-smooth, Non-separable, Non-proximable, Non-Lipschitz, Non-strongly-convex, Non-differentiable

Friday 10 May - Felix Mylius (University of Cambridge)

Why Personal Ties (Still) Matter: Referrals and Congestion

The internet has reduced search costs significantly, making it much easier to find and apply for a large number of jobs. Despite that, the share of jobs found through personal contacts has remained surprisingly stable over the past decades. To provide an explanation for this puzzle, my theoretical framework explores a new channel that makes referred candidates favourable for firms: a higher likelihood to accept a job offer. This trait becomes particularly advantageous whenever firms face uncertainty over whether their candidates would accept their job offer. To analyse the impact of lower search costs on the share of jobs found through referrals, I focus on how search costs impact the chances of securing a job through a referral. Overall, if search costs decrease and workers apply to more firms, a referred candidate expects to face more competitors, increasing the likelihood that someone else will show a stronger ability signal. On the other hand, with more applications being sent out, workers are, on average, less interested in each firm they apply to, which makes referred candidates stand out more. This means the chances of getting a job offer through a referral can increase if search frictions decrease.

Friday 3 May - Samuel Mansfield (University of Bristol)

A Structural Theorem for Sets with Few Triangles

In 1946, Erdős conjectured that the minimum number of distinct distances that can be determined by a set of N points in the plane is N(log N)^{-1/2}, the number achieved by an N^{1/2} by N^{1/2} square lattice. This was (almost) solved by Guth and Katz in 2015, but a harder variant -- that any point set with only this number of distinct distances must have a lattice structure -- is wide open, and there are remarkably few results about the structure of such a set at all. Instead of sets with few distances, we consider sets with few classes of congruent triangles, showing such sets either contain a polynomially-rich line or a positive proportion of the set lies on a circle. Our methods include classical tools from additive combinatorics combined with geometric structure within the affine group. This is based on joint work with Jonathan Passant.

Thursday 2 May - James Davies (University of Cambridge)

Distances in colourings of the plane

We prove that every finite colouring of the plane contains a monochromatic pair of points at an odd integral distance from each other. We will also discuss extensions to prime and polynomial distances.

Thursday 28 March - Olivier Gossner (LSE)

SCAMP

We study (interim correlated) rationalizability in games with incomplete information. For each given game with incomplete information, we show that all hierarchies of iterative deletion of dominated strategies can be captured through an automaton, the strategic automaton. We then prove that a finitely parameterized class of information structures, SCAMP, is sufficient to generate every outcome distribution induced by general common prior information structures. In this parameterized family, a profile of signals is identified to a path over the automaton, and the probability distribution of signal profiles defines a Markov chain.

Friday 22 March - Sahar Jahani (LSE)

Automated Equilibrium Analysis of 2x2x2 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. This paper presents an algorithm to compute this set for the simplest game with
more than two players with arbitrary (possibly non-generic) payoffs, which has not been done before. We define degeneracy in these games and we prove an upper bound on the number of possible equilibria in non-degenerate games. Furthermore, we introduce new elegant formulas for completely mixed equilibria as well as the visual representations of the best-response correspondences and their intersections in 3D, which defines 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 21 March - Tara Abrishami (University of Hamburg)

Width parameters and the maximum independent set problem 

Width parameters are graph invariants that measure the ''complexity'' of a graph. Treewidth, the most well-known graph width parameter, has important algorithmic implications: problems that are NP-hard in general, such as finding a maximum independent set in a graph, can be solved in polynomial time in graphs of bounded treewidth. However, treewidth does not capture the solvability of maximum independent set very well: there are many graph classes with unbounded treewidth which admit efficient algorithms for the maximum independent set problem. Recently, a number of new graph width parameters have been introduced with the intention of better representing the solvability of maximum independent set. In this talk, I will introduce some of these new width parameters, discuss recent results on a new parameter called induced matching treewidth, and describe several interesting open problems. This talk is based on joint work with Marcin Brianski, Jadwiga Czyżewska, Rose McCarty, Martin Milanic, Pawel Rzazewski, and Bartosz Walczak. 

Friday 15 March - Madison Van Dyk (University of Waterloo) **16.00-17.30 Joint CGO-Operations Research Reading Group Seminar**

Fast Combinatorial Algorithms for Efficient Sortation

Modern parcel logistic networks are designed to ship demand between given origin, destination pairs of nodes in an underlying directed network. Efficiency dictates that volume needs to be consolidated at intermediate nodes. In practice, such consolidation requires parcel-sortation. In this work, we propose a mathematical model for the physical requirements, and limitations of parcel sortation. We then show that, in the general model, it is NP-hard to determine whether a feasible sortation plan exists. We discuss several special settings, where (near-)feasibility of a given sortation instance can be determined efficiently. The algorithms we propose are fast, and construct solutions as well as combinatorial witness set type lower-bounds that are reminiscent and extend those used in early work on degree-bounded spanning trees and arborescences. This is joint work with Kim Klause, Jochen Koenemann, and Nicole Megow. To appear in IPCO 2024. 

Friday 15 March - Laurentiu Ploscaru (University of Birmingham)

A bipartite version of the Erdos-McKay conjecture

A set of vertices in a graph is said to be 'homogeneous' if it is a clique or an independent set. An old conjecture of Erdős and McKay states that if all homogeneous sets in an n-vertex graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,..., \Omega(n^2)}. We prove a bipartite analogue of this conjecture: if all balanced homogeneous sets in an n by n bipartite graph are of order at most O(log n), then the graph contains induced subgraphs of each size from {0,1,...,\Omega(n^2)}. Based on joint work with Eoin Long (Birmingham).

Friday 8 March - Michal Feldman (Tel-Aviv University)

Ambiguous contracts

In this work we explore the deliberate infusion of ambiguity into the design of contracts. We show that when the agent is ambiguity-averse and chooses an action that maximizes their max-min utility, then the principal can strictly gain from using an ambiguous contract. We provide insights into the structure of optimal contracts, and establish that optimal ambiguous contracts are composed of simple contracts. We also provide a geometric characterization of ambiguity-proof classes of contracts. Finally, we show that when the agent considers mixed strategies, then there is no advantage in using an ambiguous contract.

Friday 8 March - Estelle Varloot (University of Liverpool) **11.00-12.00**

Level-strategyproof Belief Aggregation Mechanisms

In the problem of aggregating experts' probabilistic predictions or opinions over an ordered set of outcomes, we introduce the axiom of level-strategyproofness (level-SP) and argue that it is natural in several real-life applications and robust as a notion. It implies truthfulness in a rich domain of single-peaked preferences over the space of cumulative distributions. This contrasts with the existing literature, where we usually assume single-peaked preferences over the space of probability distributions instead. Our main results are (1) explicit characterizations of all level-SP methods with and without the addition of other axioms (certainty preservation, plausibility preservation, proportionality); (2) comparisons and axiomatic characterizations of two new and practical level-SP methods: the proportional-cumulative and the middlemost-cumulative; (3) an application of the proportional-cumulative to construct a new voting method that extends majority judgment and where voters can express their uncertainties/doubts about the merits/qualities of the candidates/alternatives to be ranked.

Thursday 7 March - Nemanja Draganic (University of Oxford)

Hamiltonicity of expanders: optimal bounds and applications

An n-vertex graph G is a C-expander if |N(X)|≥C|X| for every X ⊆ V(G) with |X|<n/2C and there is an edge between every two disjoint sets of at least n/2C vertices. We show that there is
some constant C > 0 for which every C-expander is Hamiltonian. In particular, this implies the well known conjecture of Krivelevich and Sudakov from 2003 on Hamilton cycles in (n,d,λ)-graphs. This completes a long line of research on the Hamiltonicity of sparse graphs, and has many applications. Joint work with R. Montgomery, D. Munhá Correia, A. Pokrovskiy and B. Sudakov.

Wednesday 6 March - Meike Neuwohner (LSE)

Improved Approximation Algorithms for Weighted k-Set Packing

Abstract

Friday 1 March - R Ravi (Carnegie Mellon University) **16.00-17.30 Joint CGO-Operations Research Reading Group Seminar**

Models and Algorithms for Information Freshness in Graphs

I will describe two related formulations of information dissemination under a telephone model in graphs. After drawing out the relations between them, I plan to present an algorithm for a new variant (called Average Broadcast Time) described in this SODA 23 paper “Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models” by Chen, An, Niaparast, Ravi, and Rudenko. The talk will describe joint work with several graduate students over the years.

Friday 1 March - Miriam Fischer (Imperial College London)

Fair interventions in weighted congestion games

In this talk I present joint work with Martin Gairing and Dario Paccagnan. We study the power and limitations of fair interventions in weighted congestion games.  Specifically, we focus on interventions that aim at improving the equilibrium quality (price of anarchy) and are fair. Within this setting, we provide three key contributions:1) We show that no fair intervention can reduce the price of anarchy below a given factor depending solely on the class of latencies considered. This lower bound is unconditional, i.e., it applies regardless of how much computation interventions are allowed to use. 2) We propose a taxation mechanism that is fair and show that the resulting price of anarchy matches this lower bound, while the mechanism can be efficiently computed in polynomial time. 3) We complement these results by showing that no intervention (fair or not) can achieve a better approximation if polynomial computability is required. We do so by proving that the minimum social cost is NP-hard to approximate below a factor identical to the one previously introduced. Our results also show that the randomized algorithm proposed by Makarychev and Sviridenko [JACM’2018] for the class of optimization problems with a “diseconomy of scale” is optimal, and provide a novel way to derandomize its solution via equilibrium computation.

Thursday 29 February - Andreas Feldmann (University of Sheffield)

Parameterized Algorithms for Steiner Forest in Bounded Width Graphs

We study the parameterized complexity of the well-studied Steiner Forest problem in several graph classes of bounded width. The problem takes an edge-weighted graph and pairs of vertices as input, and the aim is to find a minimum cost subgraph in which each given vertex pair lies in the same connected component. It is known that this problem is APX-hard in general, and NP-hard on graphs of treewidth 3, treedepth 4, and feedback vertex set size 2. However, Bateni et al. [JACM, 2011] gave an approximation scheme with a runtime of n^O((k^2)/ε) on graphs of treewidth k. Our main result is a much faster efficient parameterized approximation scheme (EPAS) with a runtime of 2^O((k^2)/ε log(k/ε)) n^O(1). If k instead is the vertex cover number of the input graph, we show how to compute the optimum solution in 2^O(k log k) n^O(1) time, and we also prove that this runtime dependence on k is asymptotically best possible, under ETH. Furthermore, if k is the size of a feedback edge set, then we obtain a faster 2^O(k) n^O(1) time algorithm, which again cannot be improved under ETH.

Friday 23 February - Fei Wu (King's College London)

Strategic Bidding Wars in On-chain Auctions

The Ethereum block construction market has changed significantly since the emergence of Proposer-Builder Separation. Validators access blocks through a marketplace, where block builders bid for the right to construct the block and earn MEV (Maximal Extractable Value) rewards in a competition, known as the MEV-boost auction. While more than 90% of blocks are currently built through the auction process, trade-offs between builders’ strategic behaviors and auction design remain poorly understood.

We introduce a game-theoretic model for MEV-Boost auctions and use simulations to study different builders’ bidding strategies observed in practice. We study various strategic interactions and auction setups and evaluate how the interplay between critical elements such as access to MEV opportunities and improved network connectivity impact bidding performance and strategy effectiveness.

Thursday 22 February - Olaf Parczyk (FU Berlin)

Maximal diameter of simplicial d-complexes

The diameter of a simplicial d-complex is the diameter of its dual graph. We improve the best known lower bounds for the maximum diameter of a strongly connected simplicial d-complex. For d=2 we even obtain optimal constructions matching the trivial upper bound. This is joint work with Tibor Szabó and Silas Rathke.

Wednesday 21 February - Thomas Sauerwald (University of Cambridge)

Balanced Allocations: The Power of Choice versus Noise

In the balanced allocation problem we wish to allocate m balls (jobs) into n bins (servers) by allowing each ball to choose from some bins sampled uniformly at random. The goal is to maintain a small gap between the maximum load and average load. For the one-choice protocol, where each ball is allocated to a random bin, the gap diverges for large m. However, for the two-choice protocol, where each ball samples two bins and is placed in the least loaded of the two, it was shown that gap is only O(log log n) for all m. This dramatic improvement is widely known as ``power of two choices’’, and similar effects have been observed in hashing and routing.

In this talk, we will first give some intuition why two-choice maintains such a good balance in theory and practice. Then we will present new results in settings where the load information is incomplete or subject to some noise. Roughly speaking, our results demonstrate that if the noise is not too strong, then the performance of two-choice is not affected too much. However, we will also explore a setting with strong noise where having more choices leads to a worse performance. This is based on joint works with Dimitrios Los and John Sylvester.

Friday 16 February - Luming Zhang (LSE)

Stretching demi-bits and more on non-deterministic secure pseudorandomness

Super-bits and demi-bits are variants of pseudorandom generators which are secure against nondeterministic statistical tests. They were introduced to rule out certain approaches to proving strong complexity lower bounds beyond the limitations set out by the Natural Proofs barrier of Rudich and Razborov. Whether demi-bits are stretchable at all had been an open problem since its introduction. We answer this question affirmatively by showing that: every demi-bit can be stretched into sublinear many demi-bits. I may talk more about our contribution to non-deterministic secure pseudorandomness if time permits. [2304.14700] Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness (arxiv.org)

Thursday 15 February - Ehud Shapiro (Weizmann Institute of Science and LSE)

Grassroots Digital Democracy: Transferring power and wealth from global platforms to the people

The digital realm today is dominated by two architectures: Centralized autocratic global platforms that have adopted surveillance-capitalism as their business model; and up-and-coming blockchain-based global platforms that are decentralized but fundamentally plutocratic.  Global platforms exacerbate inequality and undermine the fabric of human society by depleting the social, economic, civic, and political capital of local communities, worldwide. The talk will review the work of my group at Weizmann with colleagues around the world on a third, alternative architecture for the digital realm, termed grassroots digital democracy.  The architecture and its engendered grassroots applications (including social networking; cryptocurrencies; social contracts) aim to provide scalable foundations for grassroots digital economies that can emerge without initial capital or external credit, and for sovereign democratic digital communities, both operating solely on the networked smartphones of their members, independently of any global resources and platforms. The publications that form the basis of the talk are collectively available here. 

Friday 9 February - Namrata (University of Warwick)

Kneser graphs are Hamiltonian

For integers k ≥ 1 and n ≥ 2k + 1, the Kneser graph K(n, k) has as vertices all k-element subsets of an n-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph K(5, 2). This problem received considerable attention in the literature, including a recent solution for the sparsest case n = 2k + 1. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph J(n, k, s) has as vertices all k-element subsets of an n-element ground set, and an edge between any two sets whose intersection has size exactly s. Clearly, we have K(n, k) = J(n, k, 0), i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász’ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway’s Game of Life, and to analyze this system combinatorially and via linear algebra.

Thursday 8 February - Andrea Freschi (University of Birmingham)

Hamilton cycles with large oriented discrepancy

Given graphs G and H, what is the largest t such that in any 2-colouring of the edgesof G, there is a copy of H in G with at least t edges in the same colour? This topic was firstraised by Erd˝os in the 1960s and has attracted renewed attention in recent years. Gishboliner,Krivelevich and Michaeli considered an analogous question for Hamilton cycles in oriented graphs.They conjectured that if G is an oriented graph on n vertices and δ(G) ≥ n/2 then G contains aHamilton cycle with at least δ(G) edges pointing in the same direction. In this talk we present aproof of this conjecture, as well as an overview of the recent developments in the area.This is based on joint works with Allan Lo and Joseph Hyde, Joanna Lada and Andrew Treglown.

Wednesday 7 February - Martin Bullinger (University of Oxford)

Online Coalition Formation under Random Arrival or Coalition Dissolution

Coalition formation considers the question of how to partition a set of n agents into disjoint coalitions according to their preferences. We consider a cardinal utility model with additively separable aggregation of preferences and study the online variant of coalition formation, where the agents arrive in sequence. The goal is to achieve competitive social welfare. In a purely deterministic model, the natural greedy algorithm is known to achieve an optimal competitive ratio, which heavily relies on the range of utilities.

We complement this result by considering two related models. First, we study a model where agents arrive in a random order. We find that the competitive ratio of the greedy algorithm is of order 1/n^2, whereas an alternative algorithm, which is based on alternating between waiting and greedy phases, can achieve a competitive ratio of of order 1/n. Second, we relax the irrevocability of decisions by allowing to dissolve coalitions into singleton coalitions. We achieve the asymptotically optimal competitive ratio of of order 1/n by drawing a close connection to a general model of online matching. Hence, in both models, we obtain a competitive ratio that does not only get rid of the utility dependencies in the base model but even essentially matches the best possible approximation ratio by polynomial-time algorithms.

This is joint work with René Romen. The paper is available on arXiv: https://arxiv.org/abs/2306.16965. A preliminary version of this paper has appeared in the Proceedings of the 31st Annual European Symposium on Algorithms (ESA 2023). 

Friday 2 February 2024 - Alexandra Lassota (Eindhoven University of Technology), 4.00-5.30pm

Small Lecture on Block-Structured Integer Programs

Integer Programs (IPs) are an ubiquitous and potent modeling tool, but in general also NP-hard to solve. Thus, special cases are studied that are solvable in polynomial time. One important case is that of block-structured IPs. The simplest class of such IPs have a constraint matrix consisting of independent sub-matrices that are linked by either few variables (2-stage stochastic IPs) or few constraints (n-fold IPs)  This talk gives an overview on the results of these IPs (including our brand-new SODA results) and outlines the most important techniques to achieve them.

Friday 2 February 2024 - Alex Malekshaian (KCL)

Counting antichains in the Boolean lattice

An old question of Dedekind asks for the number of antichains in the Boolean lattice on $n$ elements. After a long series of partial results, this was answered asymptotically by Korshunov in the 1980s. Using methods from probability and statistical physics, we refine his asymptotics, giving a formula to arbitrary exponential precision. We also give asymptotics for the number of antichains of a given, large size. As a corollary, we derive a 'sparse' version of the classical theorem of Sperner which states that the largest antichain is precisely the middle layer: we determine the threshold for the size at which an antichain is almost surely contained in the middle layer.

Joint work with Matthew Jenssen and Jinyoung Park.

Thursday 1 February - Robert Hancock (University of Oxford)

A resolution of the Kohayakawa Kreuter conjecture for almost all pairs of graphs

We study asymmetric Ramsey properties of the random graph G(n,p). For r ≥ 2 and a graph H, Rödl and Rucinski (1993-5) provided the asymptotic threshold for G(n,p) to have the following property: whenever we r-colour the edges of G(n,p) there exists a monochromatic copy of H as a subgraph. In 1997, Kohayakawa and Kreuter conjectured an asymmetric version of this result, where one replaces H with a set of graphs H_1,...,H_r and we seek the threshold for when every r-colouring contains a monochromatic copy of H_i in colour i for some i ∈ {1,...,r}.

The 1-statement of this conjecture was confirmed by Mousset, Nenadov and Samotij in 2020. We extend upon the many partial results for the 0-statement, by resolving it for almost all cases. We reduce the remaining cases to a deterministic colouring problem. Our methods also extend to the hypergraph setting. Joint work with Candida Bowtell (University of Warwick) and Joseph Hyde (University of Victoria).

Friday 26 January - George Chionas (University of Liverpool)

Who gets the MEV? A Dynamical Sharing Blockchain Mechanism

Maximal Extractable Value (MEV) has emerged as a new frontier in the design of blockchain systems. The marriage between decentralization and finance gives the power to block producers not only to select and add transactions to the blockchain but, crucially, also to order them so as to extract additional value. However, the additional value comes from the economic activity of users. In this work, we propose to make the MEV extraction rate part of the protocol design space. Our aim is to leverage this parameter to maintain a healthy balance between block producers (who need to be compensated) and users (who need to feel encouraged to transact). Inspired by the principles introduced by EIP-1559 for transaction fees, we design a dynamic mechanism which updates the MEV extraction rate with the goal of stabilizing it at a target value. We analyze the evolution of this dynamic mechanism under various market conditions and provide formal guarantees about its long-term performance.

Friday 19 January 2024 - Joachim Spoerhase (University of Sheffield)

Parameterized Approximation Schemes for Clustering with General Norm Objectives

This paper considers the well-studied algorithmic regime of designing a (1+epsilon)-approximation algorithm for a k-clustering problem that runs in time f(k,epsilon)poly(n) (sometimes called an efficient parameterized approximation scheme or EPAS for short). Notable previous results of this kind include EPASes in the high-dimensional Euclidean setting for k-center as well as k-median, and k-means. However, existing EPASes handle only basic objectives (such as k-center, k-median, and k-means) and are tailored to the specific objective and metric space. Our main contribution is a clean, simple, and unified algorithm that yields an EPAS for a large variety of clustering objectives (for example, k-means, k-center, k-median, priority k-center, l-centrum, ordered k-median, socially fair k-median aka robust k-median, or more generally monotone norm k-clustering) and metric spaces (for example, continuous high-dimensional Euclidean spaces, metrics of bounded doubling dimension, bounded treewidth metrics, and planar metrics), and which is (almost) entirely oblivious to the underlying objective and metric space. Key to our approach is a new concept that we call bounded epsilon-scatter dimension -- an intrinsic complexity measure of a metric space that is a relaxation of the standard notion of bounded doubling dimension.

This is joint work with Fateme Abbasi, Sandip Banerjee, Jarosław Byrka, Parinya Chalermsook, Ameet Gadekar, Kamyar Khodamoradi, Dániel Marx, and Roohani Sharma.

Thursday 18 January 2024 - Olivier Gossner, Matoula Kotsialou, Bernhard von Stengel, Adam Ostaszewski, Bob Simon (LSE)

Research Catch-Up Session

Wednesday 13 December - Ryan Martin (Iowa State University)

Counting Cycles in Planar Graphs

Basic Tur\'an theory asks how many edges a graph can have, given certain restrictions such as not having a large clique. A more generalized Tur\'an question asks how many copies of a fixed subgraph $H$ the graph can have, given certain restrictions. There has been a great deal of recent interest in the case where the restriction is planarity. In this talk, we will discuss some of the general results in the field, primarily the asymptotic value of ${\bf N}_{\mathcal P}(n,H)$, which denotes the maximum number of copies of $H$ in an $n$-vertex planar graph. In particular, we will focus on the case where $H$ is a cycle. It was determined that ${\bf N}_{\mathcal P}(n,C_{2m})=(n/m)^m+o(n^m)$ for small values of $m$ by Cox and Martin and resolved for all $m$ by Lv, Gy\H{o}ri, He, Salia, Tompkins, and Zhu. The case of $H=C_{2m+1}$ is more difficult and it is conjectured that ${\bf N}_{\mathcal P}(n,C_{2m+1})=2m(n/m)^m+o(n^m)$. We will discuss recent progress on this problem, including verification of the conjecture in the case where $m=3$ and $m=4$ and a lemma which reduces the solution of this problem for any $m$ to a so-called ``maximum likelihood'' problem. The maximum likelihood problem is, in and of itself, an interesting question in random graph theory.

This is joint work with Emily Heath and Chris (Cox) Wells.

Thursday 7 December - Maria Chudnovsky (Princeton University)

Induced Subgraphs and Tree Decompositions

Tree decompositions are a powerful tool in both structural graph theory and graph algorithms. Many hard problems become tractable if the input graph is known to have a tree decomposition of bounded “width”. Exhibiting a particular kind of a tree decomposition is also a useful way to describe the structure of a graph. Tree decompositions have traditionally been used in the context of forbidden graph minors; bringing them into the realm of forbidden induced subgraphs has until recently remained out of reach. Over the last several of years we have made significant progress in this direction, exploring both the classical notion of bounded tree-width, and concepts of more structural flavor. This talk will survey some of these ideas and results.

Friday 1 December 16.00 – 17.30 - Kristóf Bérczi (ELTE, Budapest)

Reconfiguration of basis pairs in regular matroids

Determining the exchange distance of two matroid basis sequences appears in several areas of computer science and mathematics. In 1980, White proposed a conjecture for the characterization of two basis sequences being reachable from each other by symmetric exchanges, which received a significant interest also in algebra due to its connection to toric ideals and Gröbner bases. In this talk, we present a proof of White's conjecture for basis sequences of length two in regular matroids, a problem that was formulated as a separate question by Farber, Richter, and Shan and Andres, Hochstättler, and Merkel. We study the problem from an optimization point of view and give a polynomial algorithm for constructing a sequence of symmetric exchanges that transforms a basis pair into another. As a byproduct, we verify a conjecture of Gabow from 1976 on the serial symmetric exchange property of matroids for the regular case. Joint work with Bence Mátravölgyi and Tamás Schwarcz.

Friday 1 December - Jun Yan (University of Warwick)

An Interesting Forbidden Matrix Problem

An r-matrix is a matrix whose entries belong to the set {0,1,…,r-1}. The forbidden matrix problem studies the quantity forb(m,r,F), which is defined to be the maximum number of distinct columns in an m-rowed r-matrix that does not contain a submatrix that is a row and/or column permutation of F. The r=2 case has been extensively studied, while relatively little is known about the r>=3 cases. In this joint work with Wallace Peaslee and Attila Sali, we study forb(m,r,M), where M is the smallest (0,1)-matrix for which the exact value of this forbidden number is not known. We significantly improve known bounds on forb(m,r,M) and, in the process, link this problem to another curious optimisation problem involving edge multiplicities of certain multigraphs.

Thursday 30 November - Marcelo Campos (University of Oxford)

Independence number of sparser Cayley graphs

Given a $p$-random $A \subseteq \mathbb{Z}_n$, the random Cayley graph $\Gamma_p$ is defined to have vertex set $\mathbb{Z}_n$ and an edge between two distinct vertices $x, y \in \mathbb{Z}_n$ if $x + y \in A$. For $p=1/2$ Green and Morris showed that the independence number of $\Gamma_{1/2}$ is asymptotically equal to $\alpha(G(n, 1/2))$. In this talk I'll show that the independence number of $\Gamma_p$ matches that of $G(n,p)$ for $p \geq (\log n)^{-1/80}$.

This is joint work with Lucas Aragão, Gabriel Dahia and João Pedro Marciano.

Friday 24 November – Eoin Hurley (University of Amsterdam)

Induced Trees in Sparse Expanders

Inspired by the network routing literature we utilise what we call the "Pre-Emptive Greedy Algorithm" to embed bounded degree induced trees in sparse expanders.  This simple proof generalises (with some extra conditions) a powerful theorem of Friedman and Pippenger to the induced setting.  It immediately implies that the sparse random graph contains all bounded degree trees (up to some linear order) as induced subgraphs. It further implies that the multicolour induced and size induced ramsey numbers of bounded trees are linear. No such linear bounds were previously known and we hope the theorem will find many more applications.

Thursday 23 November - Alastair Litterick (University of Essex)

Condorcet Domains: Their Enumeration and Structure

In 1785, on the cusp of the French Revolution, the philosopher, mathematician and politician Le Marquis de Condorcet published a seminal essay in which he considered various issues related to ranked-choice voting systems. One such issue is the Condorcet paradox: if election candidates are compared pair-wise, an overall winner may not exist. For instance if three votes are A > B > C, B > C > A and C > A > B, then each candidate loses to another by a two-thirds majority. One way to resolve this paradox is to restrict which votes are allowed: A collection of allowable votes is called a Condorcet domain if each election using these votes will have an overall winner. The question then is: What are the Condorcet domains, among all possible collections of votes? This basic question remains open despite significant advances by many researchers. Even the largest size of a Condorcet Domain is unknown for more than eight candidates. This talk will present recent progress made on questions related to Condorcet domains, through a combination of computational algebra and significant computing power.

This is joint work with Dolica Akello-Egwell, Charles Leedham-Green, Klas Markström and Søren Riis.

Friday 17 November - Yani Pehova (LSE)

The Erdős-Rothschild problem for dichromatic triangles

In 1974 Erdős and Rothschild asked the following question: given integers k, s and a large n, what is the maximum number of s-edge-colourings of an n-vertex graph free of a monochromatic k-vertex clique? A follow up question is to determine which graph(s) attain this maximum. Recent work of Pikhurko, Staden and Yilma shows that in most cases this problem reduces to considering complete multipartite graphs and only counting a natural family of Kk-free "template" colourings of their edge set. Despite this reduction, the Erdős-Rothschild problem has only been solved for some small s and k. Various generalisations of this problem have been considered in the literature, where instead of forbidding monochromatic cliques, we forbid other, non-monochromatic, patterns on a clique. We consider the problem of maximising the number of s-edge-colourings without triangles which see exactly two colours, and show that for every s, the extremal graph is an r-partite Turán graphs where r is easy to compute for any given s.

This is joint work with Pranshu Gupta, Emil Powierski and Katherine Staden.

Thursday 16 November - Thomas Karam (University of Oxford)

On the expressive power of mod-p linear forms on the Boolean cube

Let A_1,..,A_s be a sequence of dense subsets of the Boolean cube {0,1}^n and let p be a prime. We show that if s is assumed to be superpolynomial in n then we can find distinct i,j such that the two distributions of every mod-p linear form on A_i and A_j are almost positively correlated. We also prove that if s is merely assumed to be sufficiently large independently of n then we may require the two distributions to have overlap bounded below by a positive quantity depending on p only. 

Friday 10 November - Edward Plumb (LSE)

Learning in Games

We study the dynamics caused by agents who learn while playing games. We show that, even under uncertainty, dynamics locally converge to strict Nash equilibria in repeated games. However, we show that the uniqueness of a strict Nash equilibrium is not sufficient to ensure global convergence in general, but then introduce a class of games where global convergence may be obtained. 

Thursday 9 November - Irene Muzi (Birkbeck, University of London)

Improved bound for the directed grid theorem yielding an elementary Erd\H os-P\'osa bound

In 2015, Kawarabayashi and Kreutzer proved the directed grid theorem --- the generalization of the well-known excluded grid theorem to directed graphs --- confirming a conjecture by Reed, Johnson, Robertson, Seymour, and Thomas from the mid-nineties. The theorem states the existence of a function $f$ such that every digraph of directed tree-width $f(k)$ contains a cylindrical grid of order $k$ as a butterfly minor, but their function grows non-elementarily with the size of the grid minor. More precisely, it contains a tower whose height depends on the size of the grid.

In this paper we present an alternative proof of the directed grid theorem which is conceptually much simpler, more modular in its composition and also proves an elementary bound for the function $f$. Our proof is inspired by the breakthrough result of Chekuri and Chuzhoy who proved a polynomial bound for the excluded grid theorem for undirected graphs. We translate a key concept of their proof to directed graphs by introducing \emph{cycles-of-well-linked sets (CWS)} and show that any digraph of high directed tree-width contains a large CWS. As it is easily seen that a CWS contains a cylindrical grid, this allows us to improve the proof by Kawarabayashi and Kreutzer from non-elementary to an elementary function.

Since its publication in STOC 2015, the Directed Grid Theorem has found numerous applications of which our result is a direct improvement. As an example, an elementary bound for the Directed Grid Theorem implies a new bound for the Erd\H os-P\'osa property of directed cycles, the first ever elementary bound.

Friday 3 November - Tim Planken (University of Birmingham)

Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets

A range family R is a family of subsets of \mathbb{R}^d, like all halfplanes, or all unit disks. Given a range family R, we consider the m-uniform range capturing hypergraphs H(V,R,m) whose vertex-sets V are finite sets of points in \mathbb{R}^d with any m vertices forming a hyperedge e whenever e = V \cap r for some r in R. Given additionally an integer k, we seek to find the minimum m = m_R(k) such that every H(V,R,m) admits a polychromatic k-coloring of its vertices, that is, where every hyperedge contains at least one point of each color. Clearly, m_R(k) \geq k and the gold standard is an upper bound m_R(k) = O(k) that is linear in k.

A t-shallow hitting set in H(V,R,m) is a subset S of V such that every hyperedge is hit at least once but at most t times by S. In this talk, we show for several range families R the existence of t-shallow hitting sets in every H(V,R,m) with t being a constant only depending on R, which in particular proves that m_R(k) = O(k) in such cases, improving previous polynomial bounds in k. Joint work with Torsten Ueckerdt.

Thursday 2 November - Bart De Keijzer (King's College London) 

Multi-Unit Bilateral Trade

We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number k of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular.

Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised e/(1 − e) approximation mechanism, matching the best known bounds for the single-item setting. Joint work with Matthias Gerstgrasser, Paul Goldberg, Philip Lazos, and Alexander Skopalik, 2020.

Friday 27 October - Domenico Mergoni (LSE)

Many questions and some answers about product-free sets of integers 

The topic of sum-free sets of integers has been extensively studied in the past few years. However, no attention has been spent in the study of product-free sets of integers. We aim to start closing this gap with an initial analysis of properties of product-free sets of integers in the deterministic, probabilistic, and perturbed settings.

Thursday 26 October - Marius Tiba (University of Oxford)

Sharp stability for the Brunn-Minkowski inequality for arbitrary sets 

The Brunn-Minkowski inequality states that for (open) sets A and B in R^d, we have |A+B|^{1/d} \geq |A|^{1/d}+|B|^{1/d}. Equality holds if and only if A and B are convex and homothetic sets in R^d. In this talk, we present a sharp stability result for the Brunn-Minkowski inequality, concluding a long line of research on this problem. We show that if we are close to equality in the Brunn-Minkowski inequality, then A and B are close to being homothetic and convex, establishing the exact dependency between the three notions of closeness. This is based on joint work with Alessio Figalli and Peter van Hintum.

Wednesday 25 October - Marc Schröder (Maastricht University)

Hotelling's model with network effects

We study a variant of Hotelling's location game (1929). In this game firms have to decide on a location on an interval. Hotelling's famous result says that firms have an incentive to minimize differentiation. We assume a different behavior of the consumers: consumers care about their travel distance as well as the number of other consumers visiting each firm. We see how this change in assumption affects the locations of the firms and observe that the results are very different for congestion than for popularity effects.

Friday 13 October 2023 - Ilay Hoshen (Tel Aviv University)

Simonovits's Theorem in Random Graphs

(Abstract in LaTex) Let $H$ be a graph with chromatic number $\chi(H) = r+1$. Simonovits's theorem states that the unique largest $H$-free subgraph of $K_n$ is its largest $r$-partite subgraph if and only if $H$ is edge-critical. We show that the same holds with $K_n$ replaced by $G_{n,p}$ whenever $H$ is also strictly 2-balanced and
      \begin{align*}
      p \geq C n^{-1/m_2(H)} \log(n)^{1/(e(H)-1)},
      \end{align*}
for some constant $C > 0$. This is best possible up to the choice of the constant $C$. This (partially) resolves a conjecture of DeMarco and Kahn, who proved the result in the case where $H$ is a complete graph. Moreover, we prove the result with explicit constant $C = C(H)$ that we believe to be optimal. Joint work with Wojciech Samotij.

Thursday 12 October 2023 - Dima Shaiderman (Technion Israel Institute of Technology) [Online via Zoom]

Markovian Persuasion

In the classical Bayesian persuasion model, an informed player and an uninformed one engage in a static interaction. This work extends this classical model to a dynamic setting where the state of nature evolves according to a Markovian law, allowing for a more realistic representation of real-world situations where  the state of nature evolves over time. In this repeated persuasion model, an optimal disclosure strategy of the sender must balance between obtaining a high-stage payoff and disclosing information that may have negative implications on future payoffs. We discuss optimal strategies under different discount factors and characterize when the asymptotic value achieves the maximal possible value. Joint work with Ehud Lehrer.

Friday 6 October 2023 - Siyue Liu (Carnegie Mellon University/ LSE)

Approximately Packing Dijoins via Nowhere-Zero Flows

(Abstract in LaTex) In a digraph, a dicut is a cut where all the arcs are in one direction. A dijoin is a subset of arcs that intersect each dicut. Woodall conjectured in 1976 that in every digraph, the size of a minimum dicut equals to the maximum number of disjoint dijoins. Even the following weaker statement is still open. Let $f$ be the largest function such that every digraph with minimum dicut size $\tau$ contains $f(\tau)$ disjoint dijoins. It is open if when $\tau$ goes to infinity $f(\tau)$ also goes to infinity. It is not even known whether such $f(\tau)$ can be at least $3$ when $\tau$ goes to infinity.

By building connections with nowhere-zero $k$-flows, we prove that every digraph with minimum dicut size $\tau$ contains $\frac{\tau}{k}$ disjoint dijoins if the underlying undirected graph admits a nowhere-zero $k$-flow. The existence of nowhere-zero $6$-flows in $2$-edge-connected graphs proved by Seymour directly leads to the existence of $\frac{\tau}{6}$ disjoint dijoins in any digraph with minimum dicut size $\tau$ which can also be found in polynomial time. The existence of nowhere-zero circular $(2+\frac{1}{p})$-flows in $6p$-edge-connected graphs proved by Lov\'asz et al. directly leads to the existence of $\frac{\tau p}{2p+1}$ disjoint dijoins in any digraph with minimum dicut size $\tau$ whose underlying undirected graph is $6p$-edge-connected. This is joint work with G\'erard Cornu\'ejols and R. Ravi.

Thursday 5 October 2023 - Coralia Cartis (University of Oxford)

Dimensionality reduction techniques for nonconvex optimization 

Modern applications such as machine learning involve the solution of huge scale nonconvex optimization problems, sometimes with special structure. Motivated by these challenges, we investigate more generally, dimensionality reduction techniques in the variable/parameter domain for local and global optimization that rely crucially on random projections.
We describe and use sketching results that allow efficient projections to low dimensions while preserving useful properties, as well as other tools from random matrix theory and conic integral geometry.  We focus on functions with low effective dimensionality, a common occurrence in applications involving overparameterized models and that can serve as an insightful proxy for the training landscape in neural networks. We obtain algorithms that scale well with problem dimension, allow inaccurate information and biased noise, have adaptive parameters and benefit from high-probability complexity guarantees and almost sure convergence.

Friday 29 September 2023 - David Hannon (Queen Mary University of London)

Optimal Impartial Selection

We consider directed graphs without loops, and rules that select a subset of the vertices in any graph. A selection rule is impartial if the selection of a vertex is independent of its outgoing edges and we also aim to make our selection rule competitive, that is, select vertices with high indegree. This models peer selection where vertices are candidates and directed edges represent votes. We wish to select highly voted candidates such that a candidate cannot influence their own selection. We will introduce mechanisms that achieve this goal and show some impossibility results.

Thursday 28 September 2023 - Christian Coester (University of Oxford)

The Randomized k-Server Conjecture is False!

The randomized k-server conjecture, which had been open for over three decades, states that there exists an O(log k)-competitive randomized algorithm for the k-server problem. In this talk, I will present our recent joint work with Sébastien Bubeck and Yuval Rabani, where we refute this conjecture by giving a lower bound of Omega((log k)^2). Our work also settles the competitive ratio of metrical task systems to be Theta((log n)^2) on the hardest metric spaces and Theta(log n) on the easiest metric spaces of n points. In particular, this yields the first improvement over the previous “coupon collector” lower bound since the introduction of the model in 1987.