In 1980, Akiyama, Exoo, and Harary conjectured that the edges of every graph with maximum degree $d$ can be decomposed into at most $\lceil d+1/2 \rceil$ linear forests, where a linear forest is a collection of vertex-disjoint paths. This conjecture was confirmed asymptotically by Alon in 1988 who showed that $(1+o(1))d/2$ linear forests suffice. The current best general bound is due to Lang and Postle who showed that there is a decomposition into at most $ d/2+ O(d^{1/2}\log(d)^4)$ linear forests. We show that any graph on $n$ vertices can be decomposed into at most $\Delta(G)/2+O(\log(n)$ linear forests. This improves the previous upper bounds for $\Delta(G)=\Omega(\log(n)^2)$. Along the way, we show that any $d$-regular graph on $n$ vertices has a spanning linear forest with at most $2 n/(d+1)$ paths. This resolves a conjecture of Feige and Fuchs and confirms a well-known conjecture of Magnant and Martin up to a factor of $2$. This talk is based on joint work with Micha Christoph, Nemanja Draganić, Eoin Hurley, and Alp Müyesser.

This talk will be a discussion on the following two recently proved theorems. (1) There exist functions f and g such that for all positive integers k and d, for every graph G, either G contains k cycles such that vertices of different cycles have distance at least d in G, or there exists a subset X of vertices of G with |X|≤f(k) such that G−B_G(X,g(d)) is a forest, where B_G(X,r) denotes the set of vertices of G having distance at most r from a vertex of X. (2) There exist functions f and g such that for all positive integers k and d, for every graph G and every subset A of the vertices of G, either G contains k A-paths such that vertices of different A-paths are at distance at least d in G, or there exists a set X of the vertices of G with |X|≤f(k) such that every A-path in G contains a vertex of B_G(X,g(k,d)).

Joint work with (1) Vida Dujmović, Gwenaël Joret, and Pat Morin; (2) Marc Distel, Ugo Giocanti, Jędrzej Hodor, and Clément Legrand-Duchesne.

A fundamental problem in arithmetic Ramsey theory is to describe which patterns are unavoidable in sets of integers with positive upper density. Until recently, work had focused on finite configurations, such as arithmetic progressions, but in the last decade new approaches emerged that allow us to study infinite configurations. I will survey some of the recent developments in this area involving infinite sumsets.

One of the main goals in spectral graph theory is to deduce the principal properties and structure of a graph from its graph spectrum. In this talk we will show how spectral graph theory provides powerful methods for obtaining results concerning substructures of graphs, and also how these results can be useful in other mathematical fields such as coding theory. In particular, we will derive sharp eigenvalue bounds for the k-independence number of a graph (or equivalently, the independence number of the k-th graph power), which is known to be very hard to compute. We will see how to use polynomials and mixed integer linear programming in order to optimize and compute such spectral bounds. Finally, we will illustrate some recent applications of the obtained eigenvalue bounds to coding theory. The obtained results are encouraging and strongly suggest that spectral graph theory can uncover structural properties of ambient spaces that are relevant to coding theory, but that are often not captured by classical coding theory techniques.

Hadwiger’s famous conjecture states that if a graph has chromatic number at least $t$, then it must contain a $K_{t}$ minor: that is, a collection of $t$ vertex-disjoint connected subgraphs, each two of which are connected by an edge. While this conjecture remains open, Illingworth and Wood introduced a more restrictive notion of a minor called a dominating model, which leads to a very improbable version of Hadwiger’s conjecture that has turned out to be nonetheless intriguing. In this talk, we’ll survey directions of work on Hadwiger’s conjecture, as well as look at several ways in which, rather surprisingly, graphs with no $K_t$-minor and graphs with no dominating $K_t$-model turn out to be similar. This is based on joint work with António Girão, Sergey Norin, and Youri Tamitegama.

Clustering is a central problem in combinatorial optimization, with a rich theory of approximation schemes in structured settings such as Euclidean spaces and planar graphs. However, existing approaches are typically tailored to specific structures. In this talk, we present a simple and unified clustering algorithm based on a new extremal parameter, called scatter dimension. This parameter captures the intrinsic tractability of metric spaces, unifying a wide range of settings, including both geometric structures (such as Euclidean spaces) and graph structures (such as bounded treewidth and planar graphs). Our algorithm is oblivious to these structures, yet achieves approximation schemes across all of them, therefore resolving several open problems and unifying many existing results.

We prove a new lower bound on the Ramsey number $r(\ell, C\ell)$ for any constant $C> 1$ and sufficiently large $\ell$, showing that there exists $\varepsilon(C) > 0$ such that $r(\ell, C\ell) \ge \left(p_C^{-1/2} + \varepsilon(C)\right)^\ell$, where $p_C$ denotes the unique solution in $(0, 1/2)$ satisfying $C = \log p_C / \log (1 - p_C)$. This provides the first exponential improvement over the classical lower bound by Erd\H{o}s since 1947. We will also aim to discuss some recent development related to this approach. Joint work with Wujie Shen and Shengjie Xie.

Hitomezashi is a Japanese stitching technique which produces beautiful and unexpected patterns and which has only recently been studied mathematically. In this talk, I will show how hitomezashi patterns can be linked to real algebraic curves via Viro’s patchworking construction. I will also propose a generalisation of hitomezashi patterns to higher dimensions and explain how, with a bit of work, we can maintain a connection to real algebraic geometry in the case of surfaces. In any dimension hitomezashi patterns are examples of positive parts of real tropical hypersurfaces. This is based on joint work with Jules Chenal.

The Itai-Zehavi conjecture states that every $k$ vertex-connected graph contains $k$ vertex-independent spanning trees, that is, $k$ spanning trees rooted at a common vertex $r$, such that for every vertex $v$ the paths between $r$ and $v$ in different trees are internally vertex-disjoint. We show that with high probability the Itai-Zehavi conjecture holds asymptotically for the binomial random graph $G(n,p)$ when $np=\omega(\log n)$ and for the random regular graph $G(n,d)$ when $d=\omega(\log n)$. This is joint work with Lawrence Hollom, Lyuben Lichev, Julien Portier and Yiting Wang.

The simplex method is an algorithm for linear programming, and this algorithm is much faster than theory is able to explain. In this talk I will describe a new theoretical framework we introduced to address this question. Under this framework, we prove new strong running time guarantees, using mathematical assumptions taken from software user manuals. I will discuss which features of real-world software and LP’s we have managed to theoretically capture for this purpose, and what will come next.

This talk requires no prior knowledge and will be suitable for a broad audience. We will meet the chromatic symmetric function, dating from 1995, which is a generalization of the chromatic polynomial that was intended to help solve the four-colour problem, dating from 1912. We will also hear about a famed problem regarding it, called the Stanley-Stembridge $(3+1)$-free problem. This has been the focus of much research lately including resolving another problem of Stanley of whether the $(3+1)$-free problem can be widened. The resulting paper on the latter problem was recently awarded the 2023 MAA David P. Robbins Prize, and we will hear this story too.

A well-known question in combinatorial group theory, going back to a conjecture of Graham from 1971, asks if given a subset $S$ of some group $(G,+)$, it is possible to order $S$ as $s_1, s_2,…, s_t$ so that the partial sums $s_1 + s_2 + … + s_j$ are all distinct for each $j < t$. We discuss recent progress on this question, driven by a synergy between ideas from additive combinatorics and graph theory. Based on a joint work with: Benjamin Bedert, Noah Kravitz, Richard Montgomery, and Alp Müyesser.