Прошел семинар лаборатории: "Реконструкции случайных графов"
Прошел семинар лаборатории теоретической информатики 20 ноября 2025 года.
На семинаре рассмотрели мультимножество классов изоморфизмов всех подграфов G, полученных удалением одной вершины и инцидентных ей рёбер - мультимножество D(G).
Гипотеза Улама утверждает, что любые два графа с D(G)~D(G') изоморфны, если |V(G)|>2. Более сильная гипотеза утверждает, что для каждого 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).
Звонков Никита Сергеевич
Международная лаборатория теоретической информатики: стажер-исследователь