Back to Search
Start Over
Separating paths systems of almost linear size
- Publication Year :
- 2022
-
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$ in $G$, 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\'andi--Letzter--Narayanan and Balogh--Csaba--Martin--Pluh\'ar, according to which an $O(n)$ bound should hold.<br />Comment: 36 pages, 2 figures, fixed small errors in section 5
- Subjects :
- Mathematics - Combinatorics
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2211.07732
- Document Type :
- Working Paper