论文标题
分开几乎线性大小的路径系统
Separating paths systems of almost linear size
论文作者
论文摘要
图$ g $的分离路径系统是$ g $中的$ \ mathcal {p} $的集合，使得每两个边缘$ e $ e $ e $ e $和$ f $ in $ g $中，$ \ mathcal {p} $中的路径包含$ e $，但不是$ f $。我们表明，每个$ n $ vertex图都有一个尺寸$ o（n \ log^* n）$的分离路径系统。这可以改善$ o（n \ log n）$的先前最佳上限，并在猜想的猜想中取得了进展，falgas-ravry-kittipassorn-korándi-letzter-letzter-narayanan和balogh-csaba--csaba-martin--martin--martin-pluhár，根据这一$ O（n）$绑定。
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ándi--Letzter--Narayanan and Balogh--Csaba--Martin--Pluhár, according to which an $O(n)$ bound should hold.
