Deuxième problème de voisinage

En mathématiques, le deuxième problème de voisinage est un problème non résolu concernant les graphes orientés, posé par Paul Seymour. Intuitivement, il suggère que dans un réseau social décrit par un tel graphe, une personne aura au moins autant d'amis d'amis que d'amisGhazal, Salman (2015), « Une remarque sur le problème du second voisinage », Electronic Journal of Graph Theory and Applications , 3 (2) : 182– 190, https://arxiv.org/abs/1509.03282West, Douglas B., « Conjecture du deuxième voisinage de Seymour » , Open Problems – Graph Theory and Combinatorics , Université de l'Illinois, https://dwest.web.illinois.edu/openp/2ndnbhd.html.

Le problème est également connu sous le nom de conjecture du deuxième voisinage ou conjecture de la distance deux de Seymour.

Déclaration Un graphe orienté est un graphe orienté fini obtenu à partir d'un graphe non orienté simple en attribuant une orientation à chaque arête. De manière équivalente, c'est un graphe orienté sans auto-boucle, sans arêtes parallèles et sans cycles à deux arêtes. Le premier voisinage d'un sommet v (également appelé son voisinage ouvert ) se compose de tous les sommets à une distance de un de v, et le deuxième voisinage de v se compose de tous les sommets à une distance de deux de v. Ces deux voisinages forment des ensembles disjoints , dont aucun ne contient v elle-même.

En 1990, Paul Seymour a conjecturé que, dans tout graphe orienté, il existe toujours au moins un sommet v dont le second voisinage est au moins aussi grand que son premier voisinage. De manière équivalente, dans le carré du graphe , le degré de v est au moins doublé. Le problème a été publié pour la première fois par Nathaniel Dean et Brenda J. Latka en 1995, dans un article étudiant le problème sur une classe restreinte de graphes orientés, les tournois (orientations de graphes complets). Dean avait précédemment conjecturé que tout tournoi obéissait à la conjecture du second voisinage, et ce cas particulier est devenu la conjecture de DeanDean, Nathaniel ; Latka, Brenda J. (1995), « Squaring the tournament—an open problem », Actes de la vingt-sixième Conférence internationale du Sud-Est sur la combinatoire, la théorie des graphes et l'informatique (Boca Raton, FL, 1995), Congressus Numerantium , 109 : 73– 80, MR https://mathscinet.ams.org/mathscinet-getitem?mr=1369296.

Un sommet dans un graphe orienté dont le deuxième voisinage est au moins aussi grand que son premier voisinage est appelé un sommet de SeymourCohn, Zachary ; Godbole, Anant ; Wright Harkness, Elizabeth ; Zhang, Yiguang (2016), « Le nombre de sommets de Seymour dans les tournois aléatoires et les digraphes »,Graphs and Combinatorics,32(5) :1805–1816 https://arxiv.org/abs/1502.04061 https://doi.org/10.1007%2Fs00373-015-1672-9 , MR https://mathscinet.ams.org/mathscinet-getitem?mr=3543199 , S2CID https://api.semanticscholar.org/CorpusID:253889516.

Dans la conjecture du deuxième voisinage, la condition que le graphe n'ait pas de cycles à deux arêtes est nécessaire, car dans les graphes qui ont de tels cycles (par exemple le graphe orienté complet), tous les deuxièmes voisinages peuvent être vides ou petits.

Résultats partiels Fisher (1996) a prouvé la conjecture de Dean, le cas particulier du problème du deuxième voisinage pour les tournoisFisher, David C. (1996), « Élever un tournoi au carré : une preuve de la conjecture de Dean », Journal of Graph Theory , 23 (1) : 43– 48, https://doi.org/10.1002%2F%28SICI%291097-0118%28199609%2923%3A1%3C43%3A%3AAID-JGT4%3E3.0.CO%3B2-K , MR https://mathscinet.ams.org/mathscinet-getitem?mr=1402137.

Pour certains graphes, un sommet de degré sortant minimal sera un sommet de Seymour. Par exemple, si un graphe orienté possède un puits, un sommet de degré sortant nul, alors le puits est automatiquement un sommet de Seymour, car ses premier et second voisinages sont de taille nulle. Dans un graphe sans puits, un sommet de degré sortant un est toujours un sommet Seymour. Dans les orientations des graphes sans triangles , tout sommet v de degré sortant minimum est à nouveau un sommet de Seymour, car pour toute arête de v vers un autre sommet w, les voisins extérieurs de w tous appartiennent au deuxième quartier de vBrantner, James ; Brockman, Greg ; Kay, Bill ; Snively, Emma (2009), « Contributions à la conjecture du second voisinage de Seymour », Involve , 2 (4) : 385– 393, https://arxiv.org/abs/0808.0946 , https://doi.org/10.2140%2Finvolve.2009.2.387 , MR https://mathscinet.ams.org/mathscinet-getitem?mr=2579558 , S2CID https://api.semanticscholar.org/CorpusID:6206110.

Pour les graphes arbitraires de degrés de sommets élevés, les sommets de degré minimal peuvent ne pas être des sommets Seymour, mais l'existence d'un sommet de faible degré peut néanmoins conduire à l'existence d'un sommet de Seymour voisin. Grâce à ce raisonnement, la conjecture du second voisinage a été prouvée vraie pour tout graphe orienté contenant au moins un sommet de degré sortant ≤ 6Kaneko, Yoshihiro ; Locke, Stephen C. (2001), « L'approche du degré minimum pour la conjecture de distance 2 de Paul Seymour », Actes de la trente-deuxième Conférence internationale du Sud-Est sur la combinatoire, la théorie des graphes et l'informatique (Baton Rouge, LA, 2001), Congressus Numerantium , 148 : 201– 206, MR https://mathscinet.ams.org/mathscinet-getitem?mr=1887387.

Les tournois aléatoires et certains graphes orientés aléatoires ont de nombreux sommets Seymour avec une probabilité élevée. Chaque graphe orienté a un sommet dont le deuxième voisinage est au moins γ fois plus grand que le premier quartier, où est la vraie racine du polynôme .

Voir aussi

Deuxième problème de voisinage

Źródło i licencja