Реконструкции случайных графов (Никита Звонков)

Семинар международной лаборатории теоретической информатики ФКН На семинаре рассматривается мультимножество классов изоморфизмов всех подграфов G, полученных удалением одной вершины и инцидентных ей рёбер — мультимножество D(G). Гипотеза Улама утверждает, что любые два графа с D(G)~D(G') изоморфны, если |V(G)| больше двух. Более сильная гипотеза утверждает, что для каждого G на хотя бы трёх вершинах существуют три вершины u,v,w такие, что любой G' с таким же количеством вершин, обладающий разными индуцированными подграфами, изоморфными G\{v}, G\{u} и G\{w}, обязан быть изоморфен G. Назовём граф G, обладающий таким свойством, 3-восстановимым. Мы рассматриваем случайный граф G(n,p) и для разных асимптотик p покажем, что граф G(n,p) 3-восстановим с вероятностью, стремящейся к единице. Для некоторых p мы показываем, что граф G(n,p) 3-восстановим по любым трём подграфам с вероятностью, стремящейся к единице. Также затрагиваются вопросы 3-восстанавливаемости гигантской компоненты и 2-ядра случайного графа G(n,p). Выступает Никита Звонков, стажер-исследователь международной лаборатории теоретической информатики ФКН ВШЭ. 20 ноября 2025 Международная лаборатория теоретической информатики: https://cs.hse.ru/big-data/tcs-lab/ ФКН: https://cs.hse.ru Подписывайтесь на нас: 📍 https://vk.com/cshse 📍 https://t.me/fcs_hse 📍 https://t.me/sci_fcs