Семинар МЛ ТИ "Реконструкции случайных графов"

Дата: 20 ноября 2025 г., 18:10 - 19:30

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

Место проведения: Zoom 

Идентификатор конференции: 819 6829 9453
Код доступа: 031290