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

Описание: Семинар международной лаборатории теоретической информатики ФКН

На семинаре рассматривается мультимножество классов изоморфизмов всех подграфов 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