Conjecture du deuxième voisinage.
Une des conjectures sur les digraphes les plus faciles à énoncer
est la conjecture suivante due à Seymour :
Conjecture 1 [Seymour]
Pout tout digraphe D, il existe un sommet
x de D tel que
|N++(x)| >=
|N+(x)|, c'est à dire un sommet dont le
deuxième voisinage au moins aussi grand que le premier voisinage.
Cette conjecture imliquerait une des versions de la
très ancienne conjecture de Cacetta et Häggkvist:
Conjecture 2 [Cacetta -
Häggkvist] Soit D un digraphe dont tous les sommets
sont de degrés interne et externe au moins n/3. Alors
D contient un 3-circuit.
La conjecture de Seymour n'a été résolue que dans le cas des tournois.
Dans ce cas particulier, elle était connue sous le nom de conjecture de
Dean (voir[1]). Fisher [2] l'a
résolue en 1996 en utilisant l'existence d'une probabilité
p sur les sommets d'un digraphe telle que p(N+(x)) >= p(N-(x) pour tout sommet x. Dans le cas d'un
tournoi, Fisher montre que cette probabilitévérifie
p(N--(x)) >=
p(N-(x) pour tout sommet
(Ceci est faux en général pour un digraphe.) et, par un argument
de moyenne et une inversion de somme, en déduit l'existence d'un sommet
tel que |N++(x)| >=
|N+(x)|.
Cependant, la
méthode de Fisher n'était pas constructive. Avec S.
Thomassé [A7], nous donnons
une preuve élémentaire du résulat de Fisher, qui de plus
est constructive. De plus, nous montrons le résultat plus fort suivant:
Théorème 1 [Havet -
Thomassé] Soit T un tournoi.
- T possède un sommet tel que
|N++| >=
|N+|.
- si
T ne contient pas de sommet dominé (qui est
dominé par tous les autres) alors T contient deux
sommets tels que |N++| >= |N+|.
Références:
[1]
N. Dean and B. J. Latka Squaring the tournament: an open problem,
In Proceedings of the 26th Southeastern International Conference on
Combinatorics, Graph Theory and Computing Congr. Num. 109:73-80, 1995.
[2]
D. C. Fisher Squaring a tournament: a proof of Dean's conjecture,
J. Graph Theory 23:43-48,
1996.