Welcome to Combinatorics and Optimization

Abstract: We prove that no single-pass semi-streaming algorithm (deterministic or randomized) can achieve a better-than-half approximation to the maximum matching problem. This implies the optimality of the naive greedy algorithm, answering a longstanding open question in graph streaming literature since the introduction of the model. Our proof consists of two main parts:

 1. Blueprint framework: reducing the problem of proving lower bounds for semi-streaming matching to constructing certain combinatorial objects which we call blueprints; and,

 2. Blueprint construction: an optimal construction of such blueprints usable within this framework.

 Putting these two parts together implies our semi-streaming matching lower bound.

Based on joint work with Max Jiang and Mars Xiang in https://arxiv.org/abs/2607.14644 (STOC 2026) and https://arxiv.org/abs/2607.14656 (arXiv; July 2026)

Abstract: A $k$-sunflower is a family of $k$ distinct sets whose pairwise intersections all coincide. The Erd\H{o}s--Szemer\'edi conjecture asserts that for every $k \ge 3$ there is a constant $c_k < 2$ such that any $k$-sunflower-free family $\mathcal{F} \subseteq 2^{[n]}$ satisfies $|\mathcal{F}| \le c_k^{\,n}$. Bucic, He, and Lee recently proved this with an explicit bound.

In this talk we survey the problem and its place among sunflower questions, then work through the proof, centered on a vector-sunflower argument. We also discuss how the result relates to a related problem, the uniform Erd\H{o}s--Rado conjecture, which it does not settle. No prior background is assumed. 

Abstract: Determining whether a graph is k-colourable is a famously hard computational problem. Even when placing significant restrictions on the graph, the resulting problem is often NP-hard. In this talk, we focus on the case of restricting the diameter. Under the Exponential Time Hypothesis, there does not exist a sub-exponential algorithm for 3-colouring diameter-4 graphs or for 4-colouring diameter-2 graphs. Hence, the interesting remaining cases are 3-colouring graphs of diameter 2 or 3. We show that 3-colouring diameter-3 graphs can be solved in 2^O(n^{2/3−ε}) for any ε < 1/33 by providing an algorithm based on a structural result. This improves on the previous best known algorithm due to Dębski, Piecyk and Rzążewski.

This talk is based on joint work with Carla Groenland and Sophie Spirkl.