-

A new spin on Pósa rotation: Progress on Linear arboricity

组织者

马杰 , 本杰明·苏达科夫

演讲者

Nemanja Draganic

时间

2026年04月21日 17:05 至 18:15

地点

Online

线上

Zoom 787 662 9899 (BIMSA)

摘要

A linear forest is a collection of vertex-disjoint paths. The Linear Arboricity Conjecture (Akiyama, Exoo, and Harary, 1980) posits that the edges of every graph of maximum degree $\Delta$ can be decomposed into at most $\lceil(\Delta+1)/2\rceil$ linear forests. In this talk, I will present our recent work showing that $\Delta/2 + \mathcal{O}(\log n)$ linear forests suffice for an n-vertex graph. For $\Delta = \Omega(n^\varepsilon)$, this yields an exponential improvement over previously known error terms. The core of the proof relies on a novel technique that generalizes Pósa rotations, extending the operation from a single path endpoint to the simultaneous rotation of multiple endpoints in a linear forest. We will also discuss the application of this method to resolve a conjecture of Feige and Fuchs, which states that every d-regular graph on n vertices admits a spanning linear forest consisting of at most $\mathcal{O}(n/d)$ paths. Finally, we will use this method to establish the existence of optimally short tours in connected regular graphs. This is joint work with Micha Christoph, António Girão, Eoin Hurley, Lukas Michel, and Alp Müyesser.