Drugi problem sąsiedztwa

W matematyce drugi problem sąsiedztwa jest nierozwiązanym problemem dotyczącym grafów zorientowanych, postawionym przez Paula Seymoura . Intuicyjnie sugeruje to, że w sieci społecznościowej opisanej takim wykresem ktoś będzie miał co najmniej tyle samo znajomych znajomych, co znajomych. Problem jest również znany jako hipoteza drugiego sąsiedztwa lub hipoteza odległości dwa Seymoura .

Oświadczenie

Graf zorientowany to skończony graf skierowany otrzymany z prostego grafu nieskierowanego poprzez przypisanie orientacji każdej krawędzi. Równoważnie, jest to graf skierowany, który nie ma pętli własnych, krawędzi równoległych ani cykli dwukrawędziowych. Pierwsze sąsiedztwo wierzchołka $)$ zwane także jego otwartym sąsiedztwem składa się ze wszystkich wierzchołków w odległości $displaystyle$ od i drugiego sąsiedztwa $v}$ składa się ze wszystkich wierzchołków w odległości dwóch od ${\ displaystyle v}$ . Te dwa $siebie$ tworzą rozłączne zbiory , z których żaden nie zawiera .

W 1990 roku $Paul$ Seymour wysunął przypuszczenie, że w każdym grafie zorientowanym zawsze istnieje co najmniej jeden wierzchołek, drugie sąsiedztwo jest co najmniej tak duże jak jego pierwsze sąsiedztwo. Równoważnie w kwadracie wykresu stopień jest co $.$ podwojony Problem został po raz pierwszy opublikowany przez Nathaniela Deana i Brendę J. Latkę w 1995 roku w artykule, w którym badano problem na ograniczonej klasie zorientowanych grafów, turniejach (orientacje pełnych wykresów). Dean wcześniej przypuszczał, że każdy turniej jest zgodny z hipotezą drugiego sąsiedztwa, a ten szczególny przypadek stał się znany jako hipoteza Deana.

Nierozwiązany problem z matematyki :

Czy każdy graf zorientowany zawiera wierzchołek Seymoura?

(więcej nierozwiązanych problemów z matematyki)

Wierzchołek w grafie skierowanym, którego drugie sąsiedztwo jest co najmniej tak duże jak jego pierwsze sąsiedztwo, nazywany jest wierzchołkiem Seymoura . W drugim przypuszczeniu sąsiedztwa konieczny jest warunek, że graf nie ma cykli dwukrawędziowych, ponieważ w grafach, które mają takie cykle (na przykład graf kompletny zorientowany), wszystkie drugie sąsiedztwa mogą być puste lub małe.

Wyniki częściowe

Fisher (1996) udowodnił hipotezę Deana, szczególny przypadek drugiego problemu sąsiedztwa dla turniejów.

W przypadku niektórych grafów wierzchołek o minimalnym stopniu zewnętrznym będzie wierzchołkiem Seymoura. Na przykład, jeśli graf skierowany ma ujście, wierzchołek poza stopniem zero, to ujście jest automatycznie wierzchołkiem Seymoura, ponieważ jego pierwsze i drugie sąsiedztwo mają rozmiar zero. W grafie bez zlewów wierzchołek stopnia zewnętrznego jest zawsze wierzchołkiem Seymoura. W orientacjach grafów bez trójkątów każdy wierzchołek $displaystyle$ minimalnym stopniu zewnętrznym jest ponownie wierzchołkiem Seymoura, ponieważ dla dowolnej krawędzi od innego wierzchołka $v}$${\ displaystyle w}$$}$ sąsiedzi należą do drugiego sąsiedztwa ${\ displaystyle v$ . W przypadku dowolnych grafów o wyższych stopniach wierzchołków wierzchołki o minimalnym stopniu mogą nie być wierzchołkami Seymoura, ale istnienie wierzchołka niskiego stopnia może nadal prowadzić do istnienia pobliskiego wierzchołka Seymoura. Korzystając z tego rodzaju rozumowania, udowodniono, że drugie przypuszczenie sąsiedztwa jest prawdziwe dla dowolnego zorientowanego grafu, który zawiera co najmniej jeden wierzchołek o stopniu zewnętrznym ≤ 6.

Turnieje losowe i niektóre grafy losowo skierowane mają wiele wierzchołków Seymoura z dużym prawdopodobieństwem. Każdy zorientowany wykres ma wierzchołek, którego drugie sąsiedztwo jest co najmniej razy większe niż pierwsze sąsiedztwo, gdzie ${\ displaystyle \ gamma}$

${\ Displaystyle \ gamma = {\ Frac {1} {6}} \ lewo (-1 + {\ sqrt [{3 }] {53-6{\sqrt {78}}}}+{\sqrt[{3}]{53+6{\sqrt {78}}}}\right)\około 0,657}$

jest pierwiastkiem rzeczywistym wielomianu ${\ Displaystyle 2x ^ {3} + x ^ {2} -1}$ .

Zobacz też

• Paradoks przyjaźni

Linki zewnętrzne

• Druga hipoteza sąsiedztwa Seymoura , otwarte problemy w teorii grafów i kombinatoryce, Douglas B. West .