Приближение евклидовой метрики остовными деревьями. Артур Бикеев
10.12.25 Приближение евклидовой метрики остовными деревьями. Докладчик: Артур Бикеев Аннотация: Для заданного метрического пространства $ (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 $ деревьев. Страница курса - https://mccme.ru/ru/nmu/courses-of-nmu/osen-20252026/nmu_autumn2025_grub/ Ссылка на группу курса - https://t.me/coarsegeometry Лектор - Андроник Арамович Арутюнов Эта и другие лекции смотрите на канале RuTube - https://rutube.ru/channel/42881756/
10.12.25 Приближение евклидовой метрики остовными деревьями. Докладчик: Артур Бикеев Аннотация: Для заданного метрического пространства $ (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 $ деревьев. Страница курса - https://mccme.ru/ru/nmu/courses-of-nmu/osen-20252026/nmu_autumn2025_grub/ Ссылка на группу курса - https://t.me/coarsegeometry Лектор - Андроник Арамович Арутюнов Эта и другие лекции смотрите на канале RuTube - https://rutube.ru/channel/42881756/