**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.

Venue: Sala de Seminario John Von Neumann, CMM, Beauchef 851, Torre Norte, Piso 7.

Speaker: Ana Laura Trujillo

Affiliation: Centro de Modalamiento Matemático

Coordinator: Matías Pavez

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