14:00
15:00

[gt.go] - "Separating the edges of a graph by a linear number of paths" by Fábio Botler

/Exposé en anglais/Talk in english/

A path separates an edge e from an edge f if it contains the former and not the latter. How many paths do we need to separate any edge from any other? This question was first asked by Katona in 2013, in line with the general study of separating systems initiated by Rényi in 1961. In this talk, we show that the answer is linear in the number of vertices, thus confirming a conjecture independently posed by Balogh, Csaba, Martin, and Pluhár and by Falgas-Ravry, Kittipassorn, Korándi, Letzter, and Narayanan. We focus on the proof method and possible extensions.

This is based on joint work with Bonamy, Dross, Naia and Skokan.

[Fábio Botler] (Université fédérale de Rio de Janeiro )

https://www.cos.ufrj.br/~fbotler/

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

https://webconf.u-bordeaux.fr/b/mar-ef4-zed and LaBRI/178