Andra grannskapsproblemet

I matematik är det andra grannskapsproblemet ett olöst problem om orienterade grafer som ställs av Paul Seymour . Intuitivt antyder det att i ett socialt nätverk som beskrivs av en sådan graf kommer någon att ha minst lika många vänner-av-vänner som vänner. Problemet är också känt som den andra grannskapsförmodan eller Seymours avstånd två gissningar .

Påstående

En orienterad graf är en ändlig riktad graf som erhålls från en enkel oriktad graf genom att tilldela en orientering till varje kant. På motsvarande sätt är det en riktad graf som inte har några självslingor, inga parallella kanter och inga tvåkantscykler. Den första grannskapet i en vertex $v$ (även kallad dess öppna grannskap ) består av alla hörn på avstånd ett från $v$ , och den andra grannskapet av $v$ består av alla hörn vid avstånd två från $v$ . Dessa två kvarter bildar disjunkta uppsättningar , ingen av dem innehåller själva ${\displaystyle v} .$

1990 antog Paul Seymour att det i varje orienterad graf alltid finns minst en vertex $v$ vars andra grannskap är minst lika stor som dess första grannskap. På motsvarande sätt graden av $v$ åtminstone fördubblad i kvadraten på grafen . Problemet publicerades först av Nathaniel Dean och Brenda J. Latka 1995, i en artikel som studerade problemet på en begränsad klass av orienterade grafer, turneringarna ( orientering av kompletta grafer). Dean hade tidigare gissat att varje turnering följer den andra grannskapsförmodan, och detta specialfall blev känt som Deans gissningar.

Olöst problem i matematik :

Innehåller varje orienterad graf en Seymour-vertex?

(fler olösta problem i matematik)

En vertex i en riktad graf vars andra grannskap är minst lika stor som dess första grannskap kallas en Seymour vertex . I den andra grannskapsförmodan är villkoret att grafen inte har några tvåkantscykler nödvändigt, för i grafer som har sådana cykler (till exempel den fullständiga orienterade grafen) kan alla andra grannskap vara tomma eller små.

Delvis resultat

Fisher (1996) bevisade Deans gissningar, specialfallet med det andra grannskapsproblemet för turneringar.

För vissa grafer kommer en vertex med minsta ut-grad att vara en Seymour-vertex. Till exempel, om en riktad graf har en sänka, en vertex utanför noll, så är sänkan automatiskt en Seymour-vertex, eftersom dess första och andra grannskap båda har storlek noll. I en graf utan sänkor är en vertex av utgradig ett alltid en Seymour-vertex. I orienteringen av triangelfria grafer är varje vertex $v$ med minsta ut-grad återigen en Seymour-vertex, eftersom för varje kant från $v$ till en annan vertex $w$ , ut-grannar till $w$ tillhör alla det andra grannskapet av $v$ . För godtyckliga grafer med högre vertexgrader kanske hörn av minsta grad inte är Seymour-vertex, men förekomsten av en låggradig vertex kan fortfarande leda till att det finns en närliggande Seymour-vertex. Med hjälp av denna typ av resonemang har den andra grannskapsförmodan visat sig vara sann för alla orienterade grafer som innehåller minst en vertex av ut-grad ≤ 6.

Slumpmässiga turneringar och några slumpmässiga riktade grafer har många Seymour-hörn med hög sannolikhet. Varje orienterad graf har en vertex vars andra grannskap är minst $\gamma$ gånger så stor som den första grannskapet, där

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

är den reella roten av polynomet $2x^{3}+x^{2}-1$ .

Se även

• Vänskapsparadox

externa länkar

• Seymours 2nd Neighborhood Conjecture , Open Problems in Graph Theory and Combinatorics, Douglas B. West .