Dear all,
There will be a noon seminar this Thursday 27 November, given by Alexander Clifton. Please find the talk details below.
Best regards, Misha Tyomkyn.
---------------------------------------------------
Rainbow Separating Path Systems Alexander Clifton The Czech Technical University in Prague
November 27, 2025, 12:20 in S6 Abstract
We define a rainbow separating path system of a graph G as a collection of paths, where for each pair of edges e, f in E(G), there exists a path that contains e but not f, and a path of a different color that contains f but not e. Let c_k(G) denote the minimum size of a rainbow separating path system with k colors. While c_k(G) can be bounded in terms of the existing notions of weak and strong separation numbers, we show that it is not a straightforward function of these quantities. We compute c_2(G) exactly when G is a path or cycle, and up to an additive constant when G is a spider. For trees T on n vertices, we apply these results to show that c_2(T) is at most (4n+2)/3, which is asymptotically best possible. For more colors, we establish bounds for several graph classes including trees and random graphs.
Joint work with George Kontogeorgiou, S Taruni, and Ana Trujillo-Negrete
---------------------------------------------------