Вторая проблема соседства

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

Проблема также известна как вторая гипотеза соседства или гипотеза Сеймура о расстоянии два . ^[1]^[3]

Заявление

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

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

Нерешенная задача по математике :

Каждый ли ориентированный граф содержит вершину Сеймура?

(еще нерешенные задачи по математике)

Вершина ориентированного графа, вторая окрестность которой не меньше первой окрестности, называется вершиной Сеймура . ^[5]

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

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

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

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

Для произвольных графов с более высокими степенями вершин вершины минимальной степени могут не быть вершинами Сеймура, но существование вершины низкой степени все равно может привести к существованию близлежащей вершины Сеймура. С помощью такого рода рассуждений было доказано, что вторая гипотеза о окрестности верна для любого ориентированного графа, который содержит хотя бы одну вершину исходящей степени ≤ 6. ^[8]

Случайные турниры и некоторые графы случайных ориентированных графов с высокой вероятностью имеют множество вершин Сеймура. ^[5]В каждом ориентированном графе есть вершина, вторая окрестность которой не меньше $\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$ . ^[9]

См. также

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

Ссылки

^ Jump up to: ^а ^б Газаль, Салман (2015). «Замечание о второй проблеме соседства». Электронный журнал теории графов и приложений . 3 (2): 182–190. arXiv : 1509.03282 . дои : 10.5614/ejgta.2015.3.2.6 . S2CID 12891714 .
^ « Гипотеза Сеймура о втором соседстве » . факультет.математика.illinois.edu . Проверено 28 апреля 2023 г.
^ «Доказательство гипотезы Сеймура о втором соседстве» (PDF) .
^ Дин, Натаниэль; Латка, Бренда Дж. (1995), «Квадратирование турнира — открытая проблема», Труды двадцать шестой Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1995), Congressus Numerantium , 109 : 73 –80, МР 1369296
^ Jump up to: ^а ^б Кон, Закари; Годболе, Анант; Райт Харкнесс, Элизабет; Чжан, Игуан (2016), «Количество вершин Сеймура в случайных турнирах и орграфах», Graphs and Combinatorics , 32 (5): 1805–1816, arXiv : 1502.04061 , doi : 10.1007/s00373-015-1672-9 , MR 3543199 , S2CID 253889516
^ Фишер, Дэвид К. (1996), «Приведение турнира в квадрат: доказательство гипотезы Дина», Journal of Graph Theory , 23 (1): 43–48, doi : 10.1002/(SICI)1097-0118(199609)23: 1<43::AID-JGT4>3.0.CO;2-K , MR 1402137
^ Брантнер, Джеймс; Брокман, Грег; Кей, Билл; Снивли, Эмма (2009), «Вклад в гипотезу о втором соседстве Сеймура», Involve , 2 (4): 385–393, arXiv : 0808.0946 , doi : 10.2140/involve.2009.2.387 , MR 2579558 , S2CID 6206110
^ Канеко, Ёсихиро; Локк, Стивен К. (2001), «Подход минимальной степени для гипотезы Пола Сеймура о расстоянии 2», Труды тридцать второй Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 2001), Congressus Numerantium , 148 : 201–206, МР 1887387
^ Чен, Гуантао; Шен, Цзянь; Юстер, Рафаэль (2003), «Второе соседство через первое соседство в орграфах», Annals of Combinatorics , 7 (1): 15–20, doi : 10.1007/s000260300001 , MR 1984642 , S2CID 11503071

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

Гипотеза о 2-й окрестности Сеймура , Открытые проблемы теории графов и комбинаторики, Дуглас Б. Уэст .

[:0-1] Jump up to: ^а ^б Газаль, Салман (2015). «Замечание о второй проблеме соседства». Электронный журнал теории графов и приложений . 3 (2): 182–190. arXiv : 1509.03282 . дои : 10.5614/ejgta.2015.3.2.6 . S2CID 12891714 .

[2] « Гипотеза Сеймура о втором соседстве » . факультет.математика.illinois.edu . Проверено 28 апреля 2023 г.

[3] «Доказательство гипотезы Сеймура о втором соседстве» (PDF) .

[dl95-4] Дин, Натаниэль; Латка, Бренда Дж. (1995), «Квадратирование турнира — открытая проблема», Труды двадцать шестой Юго-восточной международной конференции по комбинаторике, теории графов и вычислениям (Бока-Ратон, Флорида, 1995), Congressus Numerantium , 109 : 73 –80, МР 1369296

[cgwz16-5] Jump up to: ^а ^б Кон, Закари; Годболе, Анант; Райт Харкнесс, Элизабет; Чжан, Игуан (2016), «Количество вершин Сеймура в случайных турнирах и орграфах», Graphs and Combinatorics , 32 (5): 1805–1816, arXiv : 1502.04061 , doi : 10.1007/s00373-015-1672-9 , MR 3543199 , S2CID 253889516

[f96-6] Фишер, Дэвид К. (1996), «Приведение турнира в квадрат: доказательство гипотезы Дина», Journal of Graph Theory , 23 (1): 43–48, doi : 10.1002/(SICI)1097-0118(199609)23: 1<43::AID-JGT4>3.0.CO;2-K , MR 1402137

[bbks09-7] Брантнер, Джеймс; Брокман, Грег; Кей, Билл; Снивли, Эмма (2009), «Вклад в гипотезу о втором соседстве Сеймура», Involve , 2 (4): 385–393, arXiv : 0808.0946 , doi : 10.2140/involve.2009.2.387 , MR 2579558 , S2CID 6206110

[kl01-8] Канеко, Ёсихиро; Локк, Стивен К. (2001), «Подход минимальной степени для гипотезы Пола Сеймура о расстоянии 2», Труды тридцать второй Юго-Восточной международной конференции по комбинаторике, теории графов и вычислениям (Батон-Руж, Луизиана, 2001), Congressus Numerantium , 148 : 201–206, МР 1887387

[csy03-9] Чен, Гуантао; Шен, Цзянь; Юстер, Рафаэль (2003), «Второе соседство через первое соседство в орграфах», Annals of Combinatorics , 7 (1): 15–20, doi : 10.1007/s000260300001 , MR 1984642 , S2CID 11503071

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]