Speaker: Georgios Kontogeorgiou
Center for Mathematical Modeling, U. de Chile
Date: Tuesday, March 12, 2024 at 2:30 p.m. Santiago time

Abstract: In a communication network of n nodes, each linked to every other, a single link fails. How can we discover which link is broken without going through the burdensome process of examining separately all \( \Theta(n^2)\) of them? A quick way to determine the faulty link would be to propagate messages through a designated set of paths S, such that for every two links there exists a path in S that contains exactly one of them. We say that such a set S (weakly) separates the network. It is known that a separating path system for a network of n nodes must contain at least n-1 paths. Recently, Fernandes, Oliveira Mota and Sanhueza-Matamala proved that \((1+o(1))n\) paths suffice.

I will talk about the history and motivation of this problem and give a short proof that n+2 paths are enough. This is joint work with Maya Stein.

Venue: Sala John Von Neumann, 7th floor, Beauchef 851