Гипотеза Сеймура о второй окрестности

Гипотеза Сеймура о второй окрестности — это нерешенная математическая проблема об ориентированных графах, сформулированная Полом Сеймуром. Интуитивно понятно, что в социальной сети, описываемой таким графом, у кого-то будет хотя бы столько же друзей друзей, сколько и друзей. Эта проблема также известна как гипотеза Сеймура о расстоянии два.

Постановка задачи

В контексте гипотезы Сеймура под ориентированным графом понимается конечный ориентированный граф, полученный из простого неориентированного графа путем присвоения ориентации каждому ребру. Эквивалентно, это конечный ориентированный граф, который не имеет петель, кратных ребер и циклов длины два. Первая окрестность вершины $v$ (также называемая его открытой окрестностью) состоит из всех вершин на расстоянии один от $v$, и вторая окрестность $v$ состоит из всех вершин на расстоянии два от $v$. Иными словами, первая окрестность $v$ состоит из вершин, длина минимального не нарушающего ориентацию пути до которых из $v$ равна 1, и вторая окрестность $v$ состоит из вершин, длина минимального не нарушающего ориентацию пути до которых из $v$ равна 2. Эти две окрестности образуют непересекающиеся множества, ни одно из которых не содержит саму вершину $v$.

В 1990 году Пол Сеймур предположил, что в каждом ориентированном графе всегда существует хотя бы одна вершина $v$, размер второй окрестности которой по крайней мере равен размеру ее первой окрестности. Эквивалентно, в квадрате графа степень $v$ как минимум удваивается. Впервые эта проблема была опубликована Натаниэлем Дином и Брендой Дж. Латкой в 1995 году в работе, посвященной частному случаю для особого класса ориентированных графов — турниров (полных графов с введенной ориентацией). Ранее Дин предполагал, что каждый турнир удовлетворяет гипотезе о второй окрестности, и этот особый случай стал известен как гипотеза Дина.

Гипотеза Сеймура: Любой ориентированный граф содержит точку Сеймура.

Вершина в ориентированном графе, чья вторая окрестность не меньше его первой окрестности, называется точкой Сеймура или вершиной Сеймура. В гипотезе о второй окрестности является необходимым условие, что у графа нет циклов длины два, поскольку в графах с такими циклами (например, в полном орграфе) все вторые окрестности могут быть пустыми или маленькими.

Частичные результаты

Фишер (1996) доказал гипотезу Дина, частный случай гипотезы Сеймура для турниров.

Для некоторых графов вершина минимальной исходящей степени будет вершиной Сеймура. Например, если у ориентированного графа есть сток, вершина с исходящей степенью ноль, то сток автоматически является вершиной Сеймура, поскольку его первая и вторая окрестности имеют нулевой размер. В графе без стоков вершина с исходящей степенью, равной единице, всегда является вершиной Сеймура. В ориентациях графов без треугольников любая вершина $v$ с минимальной исходящей степенью является вершиной Сеймура, поскольку для любого ребра из $v$ в другую вершину $w$, открытая окрестность $w$ вся принадлежат второй окрестности $v$. Для произвольных графов с большими степенями вершин, вершины минимальной степени могут не быть точками Сеймура, но существование вершины маленькой степени все еще может привести к существованию близлежащей точки Сеймура. С помощью такого рода рассуждений было доказано, что гипотеза о второй окрестности верна для любого ориентированного графа, который содержит хотя бы одну вершину исходящей степени ≤ 6.

Случайные турниры и случайно ориентированные графы с высокой вероятностью имеют много точек Сеймура. Чень, Шень и Юстер показали, что каждый ориентированный граф содержит вершину, вторая окрестность которой как минимум $\gamma$ на ее первую окрестность, где

$\gamma ={\frac {1}{6}}\left(-1+{\sqrt[{3}]{53-6{\sqrt {78}}}}+{\sqrt[{3}]{53+6{\sqrt {78}}}}\right)\approx 0.657$

является единственным вещественным корнем полинома $2x^{3}+x^{2}-1$.

См. также

• Парадокс дружбы

Внешние ссылки

• Seymour's 2nd Neighborhood Conjecture Архивная копия от 11 января 2019 на Wayback Machine, Open Problems in Graph Theory and Combinatorics, Douglas B. West.
• Seymour's Second Neighbourhood Conjecture Архивная копия от 17 июля 2020 на Wayback Machine, Open Problem Garden.