Title: Separating the edges of a graph by a linear number of paths
Data: 12/4 (sexta-feira) – 14h – Auditório Jacy Monteiro (Bloco B)
Speaker: Fábio Botler

Abstract: Recently, Letzter proved that any graph of order 𝑛 contains a collection of 𝑂(𝑛log⋆𝑛) paths with the following property: for all distinct edges 𝑒 and 𝑓 there exists a path in which contains 𝑒 but not 𝑓. We improve this upper bound to 19𝑛, thus answering a question of G.O.H. Katona and confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. Our proof is elementary a nd self-contained.