Letzter, Shoham;
(2024)
Separating path systems of almost linear size.
Transactions of the American Mathematical Society
, 377
(8)
pp. 5583-5615.
10.1090/tran/9187.
Preview |
Text
sep-paths.pdf - Accepted Version Download (459kB) | Preview |
Abstract
A separating path system for a graph G is a collection P of paths in G such that for every two edges e and f, there is a path in 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´andi–Letzter–Narayanan and Balogh–Csaba–Martin–Pluh´ar, according to which an O(n) bound should hold.
| Type: | Article |
|---|---|
| Title: | Separating path systems of almost linear size |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1090/tran/9187 |
| Publisher version: | http://dx.doi.org/10.1090/tran/9187 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher's terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10194646 |
Archive Staff Only
 |
View Item |
