Separating the edges of a graph by a linear number of paths

The separation of mathematical objects is one of the most classical themes in mathematics. For example, in the geometric setting, the Hyperplane Separation Theorem due to Minkowski asserts that any two disjoint convex sets in the d-dimensional Eucledian space can be separated by a hyperplane. Another example is Lusin’s Separation Theorem in descriptive set theory, which says that for any two disjoint analytic subsets of a Polish space, there is a Borel set containing the first set but disjoint from the second set.

The paper concerns the setting of separating edges by a small family of paths in a graph. Resolving the conjecture of Balogh, Csaba, Martin and Pluhár, and the conjecture of Falgas-Ravry, Kittipassorn, Korándi, Letzter and Narayanan, the authors show that every $n$-vertex graph contains a set of $O(n)$, namely $19n$, paths such that for any two edges the family contains a path containg the first but not the second edge and a path containing the second edge but not the first. It is known that the size of such a family should be linear in $n$, namely at least $(2-o(1))n$.