Back to Search
Start Over
Separating path systems of almost linear size.
- Source :
-
Transactions of the American Mathematical Society . Aug2024, Vol. 377 Issue 8, p5583-5615. 33p. - Publication Year :
- 2024
-
Abstract
- 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]
- Subjects :
- *LINEAR systems
*LOGICAL prediction
Subjects
Details
- Language :
- English
- ISSN :
- 00029947
- Volume :
- 377
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Transactions of the American Mathematical Society
- Publication Type :
- Academic Journal
- Accession number :
- 178359023
- Full Text :
- https://doi.org/10.1090/tran/9187