Le Théorème du Tournoi de Rédei revisité

Informations fondamentales

• ID de l'article : 2510.10659
• Titre : Le Théorème du Tournoi de Rédei revisité
• Auteurs : Thomas Schweser (Technische Hochschule Rosenheim), Michael Stiebitz (Technische Universität Ilmenau), Bjarne Toft (University of Southern Denmark)
• Classification : math.CO (Mathématiques combinatoires)
• Date de soumission : 12 octobre 2025 à arXiv
• Lien de l'article : https://arxiv.org/abs/2510.10659

Résumé

En 1934, L. Rédei a publié un théorème célèbre : le nombre de chemins hamiltoniens dans un tournoi est impair. En réalité, ceci est une conséquence d'un théorème plus fort dans son article. Au début des années 1970, G.A. Dirac a obtenu un théorème plus fort dans ses cours à l'Université d'Aarhus, et C. Berge dans son traité sur les graphes et hypergraphes a également obtenu un théorème plus fort. Cet article présente les théorèmes plus forts de Rédei, Dirac et Berge, et explique les connexions entre eux. Le théorème plus fort de Dirac a deux corollaires, l'un équivalent au théorème plus fort de Rédei, l'autre lié au théorème plus fort de Berge.

Contexte de recherche et motivation

Description du problème

Cet article réexamine un résultat classique de la théorie des graphes — le théorème de Rédei. Ce théorème établit que tout tournoi possède un nombre impair de chemins hamiltoniens. Cependant, cette conclusion célèbre n'est en réalité qu'un cas particulier d'un résultat théorique plus profond.

Importance de la recherche

1. Valeur historique : Le théorème de Rédei est un résultat fondamental en mathématiques combinatoires ; comprendre ses fondations théoriques plus profondes revêt une importance majeure
2. Unification théorique : En comparant les approches de différents mathématiciens, révéler les connexions profondes entre des résultats apparemment indépendants
3. Contribution méthodologique : Démontrer comment dériver des résultats classiques à partir d'un cadre théorique plus général

Limitations existantes

Bien que le théorème original de Rédei soit bien connu, ses versions plus fortes ainsi que les connexions avec les travaux d'autres mathématiciens n'ont pas été suffisamment reconnues et systématiquement organisées.

Motivation de la recherche

Les auteurs ont découvert ces connexions lors de la rédaction du livre « Jalons en théorie des graphes » et visent à présenter et prouver systématiquement ces théorèmes plus forts et leurs interrelations.

Contributions principales

1. Présentation systématique : Première présentation systématique des théorèmes plus forts des trois mathématiciens Rédei, Dirac et Berge concernant les chemins hamiltoniens
2. Connexions théoriques : Établir les relations d'équivalence et d'implication entre ces résultats apparemment indépendants
3. Cadre unifié : Fournir un cadre théorique unifié par le théorème plus fort de Dirac
4. Nouveaux résultats combinatoires : Proposer le théorème de Berge-Dirac comme combinaison de deux résultats forts

Explication détaillée des méthodes

Définitions des concepts fondamentaux

Graphe mixte : Structure graphique où chaque paire de sommets peut être une non-arête, une arête non orientée ou une arête orientée.

Représentation par permutation : Pour un graphe mixte G avec n sommets, une permutation x est définie comme un ordonnancement des sommets : $x = (x_1, x_2, \ldots, x_i, x_{i+1}, \ldots, x_n)$

Classification des ensembles d'arêtes :

• $E_1$ : Ensemble des non-arêtes
• $E_2$ : Ensemble des arêtes non orientées
• $E_3$ : Ensemble des arêtes orientées
• $\overline{E_3}$ : Ensemble de toutes les arêtes de $E_3$ avec orientations inversées

Cadre des théorèmes principaux

Théorème plus fort de Dirac (Théorème 2.1)

Soit G un graphe mixte avec au moins 2 sommets, et A un sous-ensemble de $E_1 \cup E_2$. Soit :

• $N_A$ : Nombre de permutations contenant tous les éléments de A et aucun élément de $\overline{E_3}$
• $N_{=A}$ : Nombre de permutations contenant exactement A comme éléments de $E_1 \cup E_2$ et aucun élément de $\overline{E_3}$

Alors $N_A$ et $N_{=A}$ ont la même parité, en particulier $N_A - N_{=A}$ est pair.

Techniques de preuve

Lemme clé (Lemme 2.2)

Soit A un sous-ensemble de $E_1 \cup E_2$, D un sous-ensemble de $E_3$, et N le nombre de permutations contenant tous les éléments de $A \cup D$. Alors N est pair, sauf si :

• $|A| + |D| = n - 1$
• $|D| \geq 1$
• $A \cup D = E(x)$ pour une certaine permutation $x \in P(G)$

Dans le cas exceptionnel, $N = 1$.

Stratégie de preuve

Utiliser le principe d'inclusion-exclusion et l'analyse de parité : $N_A = \sum_{D \subseteq E_3, |D| \leq n-1-|A|} (-1)^{|D|} M(D)$

Par opération modulo 2, prouver que $N_A \equiv N_{=A} \pmod{2}$.

Preuve de l'équivalence entre théorèmes

Équivalence du théorème plus fort de Rédei

Démonstration constructive montrant l'équivalence entre le corollaire 3 de Dirac et le théorème plus fort de Rédei :

1. Direction directe : Dériver le théorème plus fort de Rédei du corollaire 3 de Dirac
2. Direction inverse : Construire une preuve du corollaire 3 de Dirac à partir du théorème plus fort de Rédei

Résultats théoriques principaux

Théorème plus fort de Rédei (Théorème 1.1)

Soit T un tournoi avec au moins 2 sommets. En ajoutant à T un nouvel ensemble non vide de sommets W et certaines arêtes non orientées entre W et T ainsi qu'à l'intérieur de W, le nombre de chemins hamiltoniens du nouveau graphe ayant leurs extrémités dans T est pair.

Théorème plus fort de Berge (Théorème 1.2)

Soit G un graphe mixte avec au moins 2 sommets, et $\overline{G}$ son graphe complémentaire. Alors le nombre de chemins hamiltoniens dans G et $\overline{G}$ a la même parité.

Corollaires de Dirac

1. Corollaire 1 : Dans un graphe mixte complet, le nombre de chemins hamiltoniens contenant au moins une arête non orientée est pair
2. Corollaire 2 : La différence du nombre de permutations de types spécifiques est paire
3. Corollaire 3 : Équivalent au théorème plus fort de Rédei

Théorème de Berge-Dirac (Théorème 4.1)

Pour un graphe mixte G, soit :

• $P_0$ : Ensemble des permutations ne contenant aucun élément de $\overline{E_3}$
• $P_i$ : Ensemble des permutations ne contenant aucun élément de $E_i \cup \overline{E_3}$ ($i \in \{1,2\}$)
• $P_3 = P_1 \cap P_2$

Alors $|P_0| + |P_1| + |P_2| + |P_3|$ est pair.

Analyse des connexions théoriques

Relations d'équivalence

• Corollaire 3 de Dirac ⟺ Théorème plus fort de Rédei
• Dans le cas des graphes complets : Corollaire 2 de Dirac ⟺ Théorème plus fort de Berge

Relations d'implication

• Théorème plus fort de Dirac → Corollaires 1, 2, 3 de Dirac
• Corollaire 2 de Dirac + Théorème plus fort de Berge → Théorème de Berge-Dirac
• Théorème de Berge-Dirac → Corollaire 2 de Dirac ⟺ Théorème plus fort de Berge

Travaux connexes

Développement historique

1. 1934 : Rédei publie le théorème original et sa version plus forte
2. Début des années 1970 : Dirac découvre indépendamment un résultat plus fort dans ses cours à l'Université d'Aarhus
3. 1970 : Berge propose une autre version plus forte dans son traité sur les graphes et hypergraphes
4. 2025 : Cet article organise systématiquement les connexions entre ces résultats

Comparaison des méthodes

• Méthode de Rédei : Basée sur la technique d'inversion d'arêtes dans les tournois
• Méthode de Dirac : Utilisant les permutations et le principe d'inclusion-exclusion
• Méthode de Berge : Analyse par symétrie du graphe complémentaire

Conclusions et discussion

Conclusions principales

1. Établir les connexions systématiques entre trois théorèmes plus forts apparemment indépendants
2. La méthode de Dirac fournit le cadre le plus général
3. Le théorème classique de Rédei est un cas particulier de ces résultats plus profonds

Signification théorique

Cet article non seulement clarifie les relations entre des résultats historiquement importants, mais démontre également comment unifier la compréhension de différentes approches par le biais d'un cadre théorique plus général.

Directions futures

1. Explorer l'application de ces techniques à d'autres structures combinatoires
2. Chercher des preuves plus concises du théorème de Berge-Dirac
3. Étudier les généralisations sur des classes de graphes plus générales

Évaluation approfondie

Points forts

1. Valeur historique : Organisation systématique des résultats historiques importants et de leurs connexions
2. Profondeur théorique : Fournir un cadre théorique unifié pour comprendre différentes méthodes
3. Rigueur des preuves : Reformulation et preuve des résultats classiques en langage mathématique moderne
4. Valeur pédagogique : Présentation claire du développement historique des idées mathématiques et de leurs interrelations

Contributions techniques

1. Unification des méthodes : Traitement unifié de différents types de chemins par le concept de permutation
2. Techniques de preuve : Utilisation ingénieuse du principe d'inclusion-exclusion et de l'analyse de parité
3. Preuves constructives : Fournir des preuves constructives de l'équivalence entre théorèmes

Limitations

1. Portée des applications : Résultats principalement théoriques, applications pratiques limitées
2. Complexité computationnelle : Pas de discussion sur la complexité computationnelle des algorithmes connexes
3. Généralisation : Les généralisations à des classes de graphes plus générales restent à explorer

Évaluation de l'impact

1. Impact théorique : Fournir une nouvelle perspective de compréhension des résultats classiques en mathématiques combinatoires
2. Valeur éducative : Approprié comme matériel pédagogique pour les cours avancés de théorie des graphes
3. Inspiration pour la recherche : Peut inspirer la recherche de cadres d'unification similaires dans d'autres structures combinatoires

Références

1 L.W. Beineke, B. Toft, R.J. Wilson, Milestones in Graph Theory. A Century of Progress, MMA Press Spectrum Vol. 108 (2025).

2 C. Berge, Graphes et hypergraphes, Dunod 1970.

3 G. A. Dirac, Handwritten notes, Aarhus University 1970s.

4 L. Rédei, Ein kombinatorisher Satz, Acta Sci. Math. (Szeged) 7 (1934), 39–43.