У математиці Гіпотеза Сеймура (Задача другої околиці) — це невирішена проблема про орієнтовані графи, поставлена Полом Сеймуром. Інтуїтивно з цього випливає, що в соціальній мережі, описаній таким графом, хтось матиме щонайменше стільки ж друзів друзів, скільки й друзів.
Твердження Направлений граф — це скінченний орієнтований граф, отриманий з простого неорієнтованого графа шляхом призначення орієнтації кожному ребру. Еквівалентно, це орієнтований граф, який не має петель, паралельних ребер і двореберних циклів. Перший окіл вершини (також називається її відкритим околом) складається з усіх вершин на відстані один від , і друга околиця складається з усіх вершин на відстані два від Ці дві околиці утворюють непересічні множини, жодна з яких не містить .
У 1990 році Пол Сеймур висунув гіпотезу, що в кожному орієнтованому графі завжди існує принаймні одна вершина друга околиця якої щонайменше така ж велика, як і перша околиця. Проблему вперше опублікували Натаніель Дін та Бренда Дж. Латка у 1995 році в статті, яка досліджувала проблему на обмеженому класі орієнтованих графів, турнірах (орієнтаціях повних графів). Дін раніше висунув гіпотезу, що кожен турнір підпорядковується гіпотезі про другу околицю, і цей окремий випадок став відомим як гіпотеза Діна.
Вершина в орієнтованому графі, друга околиця якої принаймні така ж велика, як і перша околиця, називається вершиною Сеймура.
У гіпотезі Сеймура про другу околицю умова, що граф не має двореберних циклів, є необхідною, оскільки в графах, які мають такі цикли (наприклад, повний орієнтований граф), усі другі околиці можуть бути порожніми або малими.
Часткові результати довів гіпотезу Діна для турнірів
Для деяких графів з вершинами з яких виходить небагато ребер гіпотеза Сеймура виконується. Наприклад, якщо направлений граф має стік, вершину ступеня виходу нуль, то стік автоматично є вершиною Сеймура, оскільки її перша та друга околиці порожні. У графі без стиків вершина ступеня виходу один завжди є вершиною Сеймура. В направлених графів без трикутників будь-яка вершина мінімального ступеня виходу знову є вершиною Сеймура, оскільки для будь-якого ребра з до іншої вершини , сусіди всі належать до другої околиці .
Доведено, що Гіпотеза Сеймура(Задача другої околиці) є істинною для будь-якого направленого графа, який містить принаймні одну вершину зовнішнього ступеня. ≤ 6. (Тобто, якщо граф містить вершину з якої виходить не більше 6 ребер, то гіпотеза Сеймура виконується). Виходячи з цього, гіпотеза є вірною для всіх графів в яких кількість вершин не перевищує 14,
Випадкові турніри та деякі випадкові направлені графи мають багато вершин Сеймура з високою ймовірністю. Кожен направлений граф має вершину, друга околиця якої є принаймні разів більший за першу околицю, де
є дійсним коренем полінома
Див. також
Парадокс дружби
Примітки
Посилання
, Open Problems in Graph Theory and Combinatorics, Douglas B. West.