fr | en

Séparés par des virgules

Soutenance de thèse de Monsieur Charbel BOU HANNA

11h00 | École doctorale Sciences et Technologie | HADATH | LIBAN

Sujet : Rosenfeld's Conjecture

Directeur de thèse : Monsieur Abdallah ASSI

RÉSUMÉ

Ma thèse de Doctorat est basée sur un sujet très intéressant en Théorie de Graphe : Le tournoi. En 1934, Redei [21] a prouvé que tout tournoi contient un chemin Hamiltonien direct. En 1971, Grünbaum [11] a prouvé que tout tournoi contient tout chemin Hamiltonien antidirect avec exactement trois exceptions. Un circuit d'ordre trois, un tournoi regulier d'ordre cinq et un tournoi de Paley d'ordre sept ne contiennent pas un chemin Hamiltonien antidirect. En 1972, Rosenfeld [23], inspiré par le résultat de Grünbaum, propose la conjecture suivante : Conjecture de Rosenfeld : il existe k ≥ 8 tel que tout tournoi d'ordre n ≥ 8 contient tout chemin Hamiltonien orienté. Alspach, Rosenfeld [1] et Straight [28] ont prouvé la conjecture de Rosenfeld pour les chemins à deux blocs. En 1973, Forcade [10] a prouvé la conjecture de Rosenfeld dans le cas de tournois d'ordre 2 n . Thomason [29] était le premier à donner une réponse générale. Il a proposé, en 1986, qu'il existe n0 ≤ 2 128, tel que, pour tout entier n ≥ n0, tout tournoi d'ordre n contient tout chemin Hamiltonien orienté. Il a encore démontré que tout ensemble de b1 − 1 sommets dans un n−tournoi contient un origine de tout (n − 1)−chemin ayant son premier bloc de longueur b1. En 2000, Havet et Thomassé [14] avaient amélioré cette idée-clé introduite par Thomason et avaient démontré que tout tournoi T d'ordre n contient tout chemin P d'ordre n avec exactement les exceptions de Grünbaum. Pour tout x et y, deux sommets de T, ils ont deni s +(x, y) = |{z ∈ V (T) tel que z peut être atteint par un chemin direct d'origine x ou y}| et ils ont prouvé que si s +(x, y) ≥ b1 + 1, alors x ou y est un origine d'un tel chemin. Cette nouvelle idée-clé leur permet de remarquer que la démonstration de l'existence d'un n − 1−chemin orienté dans un n−tournoi est équivalente à l'existence de tout chemin Hamiltonien P dans ce tournoi sauf si (T, P) est l'un parmi 69 exceptions qui étaient vériées l'une après l'autre. Leur preuve était longue et comliquée. Encouragé par la conance de mon Professeur Amine El Sahili de l'existence d'une preuve simple et courte de la conjecture de Rosenfeld, j'ai prouvé durant l'année 2019, dans ma thèse de Master II, d'une manière simple, que tout tournoi d'order n ≥ 4 contient tout chemin à 2 blocs ou á 3 blocs. En 2020, après une année complète de travail dur, j'ai réussi à trouver deux preuves simples de la Conjecture de Rosenfeld. La première était la plus courte. J'ai utilisé un théorème établi par El Sahili-Ghazo Hanna [24] qui m'a permis de reduire à moitié le nombre de cas que j'avais à étudier. Dans la deuxième preuve, je n'avais pas utilisé le théorème établi par El Sahili-Ghazo Hanna. Dans le chapitre 1 de cette thèse, je donné quelques dénitions, notations et propriétés qui seront utilisées pour lire la thèse. Dans le chapitre 2, je présente quelques resultats que j'ai trouvé en Master II. Ces résultats donnant une simple preuve de la conjecture de Rosenfeld dans les chemins orientés à deux et trois blocs était la source de lumière qui m'a aidé à généraliser ma preuve. J'ai encore démontré, en chapitre 2, que pour deux entiers positifs donnés a 4 et b tel que a < b, il existe un tournoi T tel que {d +(v), v ∈ V (T)} = {a, b}. Ce résultat est trouvé par K.B. Reid [22]. Dans le chapitre 3, je donne ma première preuve de la Conjecture de Rosenfeld. On donne un tournoi T d'ordre n tel que δ −(T) = i et un chemin orienté P = x1...xn. El Sahili et Ghazo Hanna ont prouvé que T contient P si et seulement si T contient P. Tout d'abord, je démontre que T contient P si (xi, xi+1) ∈ E(P). Sinon, (xi+1, xi) ∈ E(P). Puisque (xi, xi+1) ∈ E(P), alors T contient P. Par suite, par le théoreme de El Sahili-Ghazo Hanna, T contient P. Dans le chapitre 4, pour un tournoi donné T d'ordre n tel que δ −(T) = i et un chemin P = x1...xn tel que (xi+1, xi) ∈ E(P), je démontre que T contient une copie de P. Dans le cas contraire, (xi, xi+1) ∈ E(P). L'existence de P dans T étant démontrée dans le chapitre 3, on peut déduire une preuve de la Conjecture de Rosenfeld sans utiliser le théorème de El Sahili-Ghazo Hanna. Dans le chapitre 5, je dénis le vecteur représentatif d'un tournoi. C'est une représentation simpliée d'un tournoi qui utilise n − 1 entrées au lieu de n(n−1) 2. Je donne en plus un programme qui transforme un tournoi d'ordre n en un vecteur d'ordre n−1 par rapport à une enumération donnée des sommets de ce tournoi et vice versa. Ce programme donne aussi tous les chemins directs et les ordres moyens du tournoi.

Télécharger l'avis de soutenance de thèse

Scroll