Acyclic Dichromatic Number of Tournaments: these are the Champions

Résumé technique : Nombre dichromatique acyclique des tournois

Énoncé du problème
Cet article étudie le nombre dichromatique acyclique ($\vec{\chi}_a$) des graphes orientés, plus précisément dans le contexte des tournois. Une $k$-dicoloration acyclique est une partition des sommets en $k$ ensembles tels que le sous-digraphe induit par chaque partie est acyclique, et que le graphe bipartite orienté entre deux parties soit également acyclique. Le nombre dichromatique acyclique est le nombre minimal $k$ requis pour une telle partition.

Les auteurs traitent de deux conjectures spécifiques posées par Bang-Jensen, Picasarri-Arrieta et Yeo [4] :

1. Caractérisation des champions : Identifier quels tournois $H$ sont des « champions » (analogues aux « héros » dans la théorie classique du nombre dichromatique), c'est-à-dire que tout tournoi exempt de $H$ possède un nombre dichromatique acyclique borné.
2. Propriété local-global : Déterminer si le nombre dichromatique acyclique d'un tournoi est borné par une fonction du nombre dichromatique acyclique maximal des voisinages sortants de ses sommets.

Méthodologie
L'article emploie la théorie structurelle des graphes et des arguments de type Ramsey pour établir des bornes sur le nombre dichromatique acyclique.

• Dimatchings : Un outil central introduit est le dimatching, défini comme un ensemble d'arcs disjoints par paires $\{a_1b_1, \dots, a_kb_k\}$ tels que $a_i \to b_j$ si $i=j$ et $a_i \leftarrow b_j$ si $i \neq j$. Les auteurs exploitent un résultat de Bang-Jensen et al. [4] stipulant que l'existence d'un grand dimatching implique un nombre dichromatique acyclique élevé.
• Théorie de Ramsey : La preuve utilise le théorème d'Erdős-Moser [8] concernant l'existence de sous-tournois transitifs dans de grands tournois pour localiser des configurations structurelles spécifiques (notamment le tournoi $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$) au sein de tournois contenant de grands dimatchings.
• Réduction aux graphes bipartites : Pour prouver l'existence de grands dimatchings dans les tournois ayant un nombre dichromatique acyclique élevé, les auteurs réduisent le problème aux propriétés des graphes bipartites. Ils utilisent un résultat d'Atminas [2] concernant les appariements induits et les co-appariements dans les graphes bipartites. Plus précisément, ils relient le nombre dichromatique acyclique d'un tournoi bipartite à l'absence de $2K_2$ induit (appariements induits de taille 2) dans le graphe bipartite non orienté sous-jacent.
• Partition récursive : Les preuves impliquent la décomposition de tournois en ensembles transitifs et l'analyse de leurs interactions à l'aide de corollaires dérivés du Lemme 9, qui borne le nombre dichromatique acyclique d'un digraphe en fonction de ses sous-digraphes induits.

Contributions clés et résultats

1. Confirmation de la conjecture des champions (Théorème 3) :
   Les auteurs prouvent qu'un tournoi $H$ est un champion si et seulement s'il est isomorphe à un sous-tournoi de $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$ pour un certain entier $k \ge 1$.

• Mécanisme : Ils démontrent que tout tournoi possédant un dimatching suffisamment grand doit contenir un sous-tournoi isomorphe à $TT_k \Rightarrow (\Delta(1, 1, k) \Rightarrow TT_k)$. Puisque les grands dimatchings imposent un nombre dichromatique acyclique élevé, tout tournoi évitant cette structure spécifique doit avoir un nombre dichromatique acyclique borné.

2. Existence de dimatchings (Théorème 4) :
   L'article établit une fonction $f: \mathbb{N} \to \mathbb{N}$ telle que tout tournoi dont le nombre dichromatique acyclique est au moins $f(k)$ contient un dimatching de taille $k$.

• Mécanisme : Ce résultat repose sur le théorème d'Atminas [2] concernant les graphes bipartites. En montrant que si un tournoi manque d'un grand dimatching, sa structure peut être partitionnée en un nombre borné d'ensembles transitifs avec des interactions bipartites spécifiques, les auteurs bornent le nombre dichromatique acyclique.

3. Confirmation de la propriété local-global (Théorème 5) :
   Les auteurs prouvent l'existence d'une fonction $g: \mathbb{N} \to \mathbb{N}$ telle que pour tout tournoi $T$, $\vec{\chi}_a(T) \le \max_{v \in V(T)} g(\vec{\chi}_a(v^+))$.

• Mécanisme : Ceci est dérivé comme une conséquence du Théorème 4. Si un tournoi possède un grand nombre dichromatique acyclique, il contient un grand dimatching. La structure de ce dimatching garantit que le voisinage sortant de certains sommets contient un grand dimatching, imposant ainsi un nombre dichromatique acyclique élevé dans le voisinage local.

Signification et affirmations
L'article confirme deux conjectures de Bang-Jensen, Picasarri-Arrieta et Yeo [4], complétant ainsi la caractérisation des « champions » pour le nombre dichromatique acyclique et établissant sa propriété local-global.

Les auteurs notent que si l'implication directe de la caractérisation des champions (que les champions doivent avoir cette forme spécifique) était déjà connue, la réciproque (que les tournois de cette forme sont effectivement des champions) constitue la contribution inédite de ce travail. De plus, l'article fournit une preuve alternative pour le Théorème 3 dans l'appendice qui ne repose pas sur le Théorème 4 ou le résultat d'Atminas, ce qui, selon les auteurs, permet d'obtenir de meilleures bornes supérieures et pourrait faire l'objet d'un intérêt indépendant pour des recherches futures.

Ce travail comble le fossé entre le nombre dichromatique bien compris (où les « héros » sont caractérisés par une structure récursive spécifique) et le nombre dichromatique acyclique, plus restrictif, montrant que bien que les structures diffèrent, les propriétés fondamentales de bornage et de localité s'appliquent aux deux paramètres dans les tournois.