This One-Day Meeting in Combinatorics, which will be held in the School of Mathematics at the University of Bristol on the afternoon of Wednesday 10th June 2026, features four internationally-known speakers in Combinatorics.
Venue: Fry Building, LG02.
1pm: António Girão (UCL): Linear arboricity and related problems.
2pm: Candida Bowtell (Birmingham): Andersen’s rainbow path conjecture.
3pm-3:30pm: Coffee break.
3:30pm: Jessica Enright (Glasgow): Solving problems on (parameterised) temporal graphs.
4:30pm: Shoham Letzter (UCL): An exact minimum codegree threshold for tight Hamilton cycles.
____
Abstracts.
António Girão (UCL). Linear arboricity and related problems.
Abstract: In 1980, Akiyama, Exoo, and Harary conjectured that the edges of every graph with maximum degree d can be decomposed into at most ceiling(d+1/2) 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, Lukas Michel and Alp Müyesser.
Candida Bowtell (Birmingham). Andersen’s rainbow path conjecture.
Abstract: In 1989, Andersen conjectured that every properly edge-coloured complete graph on n vertices contains a rainbow path covering at least n-1 vertices. That is, a path which uses any colour at most once. We confirm this conjecture for sufficiently large n, moreover, showing that when at least n colours are used, one can find a rainbow Hamilton path. Our proof combines results of Montgomery on rainbow matchings in bipartite graphs with a novel relaxation of a sorting network. This is joint work with Richard Montgomery, Alp Müyesser and Alexey Pokrovskiy.
Jessica Enright (Glasgow). Solving problems on (parameterised) temporal graphs.
Abstract: Temporal graphs are graphs with edges that are only active at some specified timesteps and are useful for modelling systems where contact between agents changes over time. As for classic graphs, many of the combinatorial optimisation problems we might want to solve are intractable in general, and parameterised algorithms are one approach that will let us attack these problems when there is some useful restriction on the temporal graph. I will discuss several of the parameters we have found to be algorithmically useful and outline some general approaches to using them for e.g. firefighting, dominating set, temporal Hamiltonian path.
Shoham Letzter (UCL). An exact minimum codegree threshold for tight Hamiltonian cycles.
Abstract: A tight Hamilton cycle in a k-uniform hypergraph is a cyclic ordering of the vertices such that every k consecutive vertices form an edge. We solve the following problem (for large n): what is the minimum m such that if G is a k-uniform hypergraph on n vertices whose every k-1 vertices are in at least m edges (i.e. G has minimum codegree at least m) then G has a tight Hamilton cycle? We show that this minimum m is (n–k+2)/2, confirming a conjecture of Katona and Kierstead from 1999. This is joint work with Richard Lang, Arjun Ranganathan, and Nicolás Sanhueza-Matamala.


