- This event has passed.
Jozef Skokan, Separating the edges of a graph by a linear number of paths
May 9 Tuesday @ 4:30 PM - 5:30 PM KST
Room B332, IBS (기초과학연구원)
Recently, Letzter proved that any graph of order n contains a collection P of $O(n \log^*n)$ paths with the following property: for all distinct edges e and f there exists a path in P which contains e but not f. We improve this upper bound to 19n, thus answering a question of Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhar and by Falgas-Ravry, Kittipassorn, Korandi, Letzter, and Narayanan.
Our proof is elementary and self-contained.