Analysis seminar – Ofer Neiman – Covering Metric Spaces by Few Trees
Oct 19, 2023
9:30AM to 10:30AM
Date(s) - 19/10/2023
9:30 am - 10:30 am
Location: Online/Zoom meeting (details to be shared via email)
Speaker: Ofer Neiman (David Ben-Gurion University, Israel)
Title: Covering Metric Spaces by Few Trees.
Abstract: A tree cover of a metric space (X,d) is a collection of trees, so that every pair x,y ? X has a low distortion path in one of the trees. If it has the stronger property that every point x ? X has a single tree with low distortion paths to all other points, we call this a Ramsey tree cover.
We devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.
This is joint work with Yair Bartal and Nova Fandina,