Приближение евклидовой метрики остовными деревьями.

Докладчик: Артур Бикеев

Аннотация:
Для заданного метрического пространства $ (P,\phi) $ древесное покрытие с протяженностью $ t $ - это такой набор деревьев на $ P $, такой что ребра $ (x,y) $ этих деревьев имеют длину $ \phi(x,y) $, и такой, что для любой пары точек $ u, v\in P $ существует дерево $ T $, такое, что индуцированное графовое расстояние в $ T $ между вершинами $ u $ и $ v $ не превышает $ t\cdot \phi(u,v) $.
Известно, что для решетки $ [n]^d $ в $\mathbb R ^d$ существует древесное покрытие размера $ d+1 $ с протяженностью $ O(1) $, однако минимальное возможное количество таких деревьев остается неизвестным. Мы доказали, что для любого набора $ P $ точек на евклидовой плоскости существует древесное покрытие из двух деревьев с протяженностью $ O(1) $. Несмотря на то, что в более высоких размерностях задача все еще не решена, мы также доказали, что для некоторого более сильного варианта задачи о древесном покрытии с протяженностью $ O(1) $ требуется не менее $ (d+1)/2 $ деревьев.

Доклад: 10 декабря (среда), НМУ, аудитория 310, начало в 19.20.
Ссылка на трансляцию: https://www.youtube.com/live/aFBMpajMnLo