Talk information

Date: Sunday, December 11, 2022
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Shoham Letzter (University College London)
Title: Separating path systems of almost linear size

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.