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

Abstract: A collection $\mathcal{P}$ of paths in a graph $G$ is called a \textit{strongly-separating path system} if, for any two edges $e$ and $f$ in $G$, there exist paths $P_e,P_f\in \mathcal{P}$ such that $e$ belongs to $P_e$ but not to $P_f$, and $f$ belongs to $P_f$ but not to $P_e$. If $\mathcal{P}$ contains a path that includes one edge but not the other, it is called a \textit{weakly-separating path system}. In 2014, Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan conjectured that every graph on $n$ vertices admits a weakly-separating path system of size $O(n)$. Independently, in 2016, Balogh, Csaba, Martin, and Pluhár posed a similar conjecture for strongly-separating path systems. In 2022, Letzter made significant progress by proving the existence of a strongly-separating path system of size $n\log^\star n$.
More recently, in 2023, Bonamy, Botler, Dross, Naia, and Skokan confirmed the conjecture of Balogh et al., showing that every graph on $n$ vertices admits a strongly-separating path system of size $19n$. In this talk, we will present the construction and key ideas behind the
proof by Bonamy et al., which establishes this improved bound.

Posted on Sep 25, 2024 in Seminario de Grafos, Seminars