Configurations inévitables dans les tournois

Introduction.

Il existe de nombreux rapports entre les orientations et les colorations d'un graphe. Le plus ancien est le théorème de Gallai-Roy qui affirme que toute orientation d'un graphe k-chromatique contient un chemin direct (toutes les arêtes dans le même sens) d'ordre k. Plus généralement, on peut se demander quels sont les graphes orientés qui sont contenus dans toutes les orientations d'un graphe k-chromatique. Pour aborder ce problème, il est naturel de chercher d'abord les graphes orientés qui sont contenus dans les orientations des graphes complets, c'est à dire les tournois. En effet, le graphe complet à k éléments est le graphe k-chromatique le plus simple. Nous nous intéressons à l'existence de chemins, cycles et arbres dans les tournois ainsi qu'au côté algorithmique du problème.

Chemins dans les tournois.

Un des premiers résultats sur les tournois affirme l'existence d'un chemin hamiltonien direct dans tout tournoi. Plutôt que de regarder les chemins directs, on peut s'intéresser à l'existence de chemins orientés quelconques dans un tournoi. En 1971, Grünbaum [5] prouva que tout tournoi contient les chemins hamiltoniens alternés (deux arêtes consécutives sont de sens opposé), à part trois exceptions: le 3-cycle, le tournoi régulier à 5 sommets et le tournoi de Paley à 7 sommets. En 1972, Rosenfeld [8] conjectura qu'il existe un entier N>7 tel que tout tournoi d'ordre n>=N contient tout chemin orienté hamiltonien. Cette conjecture a été vérifiée pour les chemins à deux blocs par Alspach et Rosenfeld [1] et pour tous les chemins si n=2^k par Forcade [4]. Enfin, Thomason [10] l'a prouvée pour les tournois d'ordre n>=2¹²⁸ et a conjecturé qu'elle était vraie pour n>7.

Avec S. Thomassé [A1], nous avons complètement établi la conjecture de Rosenfeld en prouvant le théorème suivant:

Théorème 1 Soient T un tournoi d'ordre n et P un chemin d'ordre k <= n. Alors T contient P si et seulement si (T;P) n'est pas une exception de Grünbaum.

Dans ma thèse et [A4], je donne un algorithme en O(n²) pour trouver un chemin hamiltonien dans un tournoi.

Cycles dans les tournois.

La suite logique de ce travail est l'étude de l'existence de cycles dans un tournoi. Elle démarre là aussi sur un résultat classique du à Camion [3]: Un tournoi contient un cycle hamiltonien direct si et seulement si il est fortement connexe. On peut là aussi se pencher sur l'existence de cycles hamiltoniens quelconques dans un tournoi. En 1974, Rosenfeld [9] conjectura qu'il existe un entier N tel que tout tournoi d'ordre n>= N contient tout cycle hamiltonien non direct. Elle a été vérifiée pour les cycles avec un bloc de taille n-1 par Grünbaum, pour les cycles alternés par Thomassen [11] (n>= 50), Rosenfeld [9] (n>= 28) et Petrovic [7] (n>= 16), et pour les cycles ayant deux blocs par Benhocine et Wojda [2]. Thomason [10] l'a prouvée pour n>= 2¹²⁸ et a conjecturé qu'elle était vraie pour n>= 9.

Dans ma thèse, j'établis plusieurs résultats partiels :

Théorème 2   Soit T un tournoi réductible d'ordre n et C un cycle orienténon direct d'ordre n. Alors T contient C.

Théorème 3   Soit T un tournoi k-fortement connexe (k>= 1) d'ordre n >= 6 et C un cycle d'ordre n qui contient un bloc de longueur au moins k+2. Alors T contient C.

Théorème 4   Si T est un tournoi 1-fortement connexe d'ordre n >= 9 et C un cycle d'ordre n alors T contient C.

De plus, pour chacun de ces résultats, je caractérise toutes les exceptions de petits ordres.

Dans [A2], je complète le théorème 3 en montrant que tout tournoi k-fortement connexe contient tous les cycles hamiltoniens dont les blocs sont de taille au plus k+1 pour k>7$. Etudiant plus en détails, les cycles dans les tournois de petite forte connexité je montre la conjecture de Rosenfeld pour N=68 :

Théorème 5   Tout tournoi d'ordre n>67 contient tous les cycles orientés non-directs hamiltoniens.

Les preuves des théorèmes ci-dessus se traduisent en des algorithmes en O(n²) pour trouver des cycles hamiltoniens dans les tournois.

Arbres dans les tournois.

Soit f(n) le plus petit entier tel que tout tournoi d'ordre f(n) contient tout arbre orienté d'ordre n. Et soit g(k) le plus petit entier tel que tout tournoi d'ordre n+g(k) contient tout arbre orienté d'ordre n ayant k feuilles. Sumner a conjecturé que f(n) = 2n - 2 en remarquant que cette condition est nécessaire. En effet, un tournoi régulier à 2n-1 sommets ne contient pas de sommets de degré externe n-1 ou plus et ne contient donc pas l'arbre orienté composé d'une racine dominant n-1 feuilles. Häggkvist et Thomason [6] ont prouvé f(n)<= 12n et f(n)<= (4+o(1))n. De plus, ils ont prouvé que g(k)<= 2^512k³.

Avec Stéphan Thomassé, nous conjecturons que g(k) = k-1. Cette conjecture implique celle de Sumner.

Dans ma thèse et [A3],je montre entre autres que g(3)<= 5. On en déduit que f(n)<= 38/ 5 n.

Avec S. Thomassé [A7], nous montrons que f(n)<= 7/ 2n. De plus, nous montrons la conjecture de Sumner pour les arborescences, i.e. les arbres dirigés depuis une racine.

Enfin dans [A8], je donne une large classe d'arbres pour laquelle g(k) = k-1 et avec S. Céroi, dans [A9], nous montrons que tout arbre d'ordre n avec trois feuilles est contenu dans tout tournoi d'ordre n+1, à une exception près (l'arbre constitué d'un sommet qui domine 3 feuilles). Ceci implique g(3) = 2.

Références:

  [1] B. Alspach and M. Rosenfeld Realisation of certain generalized paths in tournaments. Discrete Math. 34: 199-202, 1981.

  [2] A. Benhocine and A. P. Wojda On the existence of a specified cycle in a tournament. J. Graph Theory 7: 469-474, 1983.

  [3] P. Camion Chemins et circuits hamiltoniens dans les graphes complets. C. R. Acad. Sci. Paris 249: 2151-2152, 1959.

  [4] R. Forcade Parity of paths and circuits in tournaments. Discrete Math. 6: 115-118, 1973.

  [5] B. Grünbaum Antidirected hamiltonian paths in tournaments. J. Comb. Theory B 11: 249-257, 1971.

  [6] R. Häggkvist and A. G. Thomason Trees in tournaments. Combinatorica 11: 123-130, 1991.

  [7] V. Petrovic Antidirected hamiltonian circuits in tournaments. In Graph Theory (Novi Sad, 1983), pages 259-269, Univ. Novi Sad, Novi Sad, 1984.

  [8] M. Rosenfeld Antidirected hamiltonian paths in tournaments. J. Comb. Theory B 12: 93-99, 1972.

  [9] M. Rosenfeld Antidirected hamiltonian cycles in tournaments. J. Comb. Theory B 16: 234-242, 1974.

[10] A. G. Thomason Paths and cycles in tournaments. Trans. Amer. Math. Soc. 296: 167-180, 1986.

[11] C. Thomassen Antidirected hamiltonian cycles and paths in tournaments. Math. Ann. 201: 231-238, 1973.

fhavet@sophia.inria.fr