Вторая проблема соседства - Second neighborhood problem

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

утверждение

Ориентированный граф - это конечный ориентированный граф получается из простого неориентированный граф путем присвоения ориентация к каждому краю. Эквивалентно, это ориентированный граф, который не имеет петель, параллельных ребер и двухреберных циклов. Первая окрестность вершины ${\displaystyle v}$ (также называемый открытый район ) состоит из всех вершин в расстояние один из ${\displaystyle v}$, а вторая окрестность ${\displaystyle v}$ состоит из всех вершин на расстоянии два от ${\displaystyle v}$. Эти два района образуют непересекающиеся множества, ни один из которых не содержит ${\displaystyle v}$ сам.

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

Нерешенная проблема в математике: Каждый ориентированный граф содержит вершину Сеймура? (больше нерешенных задач по математике)

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

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

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

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

Случайные турниры и случайные ориентированные графы имеют много вершин Сеймура с высокой вероятностью.^[2]Каждый ориентированный граф имеет вершину, вторая окрестность которой не меньше ${\displaystyle \gamma }$ раз больше, чем первый район, где

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

- действительный корень многочлена ${\displaystyle 2x^{3}+x^{2}-1}$.^[6]

Смотрите также

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

использованная литература

1. Дин, Натаниэль; Латка, Бренда Дж. (1995), «Квадрат турнира - открытая проблема», Труды Двадцать шестой Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1995), Congressus Numerantium, 109: 73–80, Г-Н  1369296
2. Кон, Захари; Годболе, Анант; Райт Харкнесс, Элизабет; Чжан, Игуан (2016), "Число вершин Сеймура в случайных турнирах и орграфах", Графы и комбинаторика, 32 (5): 1805–1816, arXiv:1502.04061, Дои:10.1007 / s00373-015-1672-9, Г-Н  3543199
3. Фишер, Дэвид С. (1996), «Квадрат турнира: доказательство гипотезы Дина», Журнал теории графов, 23 (1): 43–48, Дои:10.1002 / (SICI) 1097-0118 (199609) 23: 1 <43 :: AID-JGT4> 3.0.CO; 2-K, Г-Н  1402137
4. Брантнер, Джеймс; Брокман, Грег; Кей, Билл; Снайвли, Эмма (2009), «Вклад в гипотезу Сеймура о втором соседстве», Вовлекать, 2 (4): 385–393, arXiv:0808.0946, Дои:10.2140 / вовлекать 2009.2.387, Г-Н  2579558
5. Канеко, Йошихиро; Локк, Стивен К. (2001), "Подход минимальной степени для гипотезы Пола Сеймура о расстоянии 2", Труды Тридцать второй Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Лос-Анджелес, 2001), Congressus Numerantium, 148: 201–206, Г-Н  1887387
6. Чен, Гуантао; Шен, Цзянь; Юстер, Рафаэль (2003), "Второе соседство через первое соседство в орграфах", Анналы комбинаторики, 7 (1): 15–20, Дои:10.1007 / с000260300001, Г-Н  1984642

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

• Гипотеза Сеймура о втором соседстве, Открытые задачи теории графов и комбинаторики, Дуглас Б. Вест.