Separating path systems of almost linear size.

A separating path system for a graph G is a collection \mathcal {P} of paths in G such that for every two edges e and f, there is a path in \mathcal {P} that contains e but not f. We show that every n-vertex graph has a separating path system of size O(n \log ^* n). This improves upon the previous best upper bound of O(n \log n), and makes progress towards a conjecture of Falgas-Ravry–Kittipassorn–Korándi–Letzter–Narayanan and Balogh–Csaba–Martin–Pluhár, according to which an O(n) bound should hold. [ABSTRACT FROM AUTHOR]