Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings

Ce papier détermine le nombre anti-Ramsey des forêts linéaires couvrantes constituées de $k$ chemins disjoints à 3 sommets et de $t$ arêtes disjointes ($n=3k+2t$) pour tout $k \ge 1$ et $t \ge 2$, résolvant ainsi le problème sans les restrictions présentes dans les travaux antérieurs.

L'essentiel

Imaginez que vous organisiez une fête géante avec un nombre considérable d'invités. Appelons le nombre total d'invités $n$. À cette fête, chaque invité serre la main de tous les autres invités exactement une fois. En termes mathématiques, cela correspond à un « graphe complet » ($K_n$).

Maintenant, imaginez que vous soyez l'organisateur de la fête et que vous disposiez d'une boîte massive de feutres de couleurs. Votre tâche consiste à colorer chaque poignée de main (arête) avec une couleur spécifique. Vous souhaitez rendre la fête aussi colorée que possible, mais vous devez respecter une règle stricte : vous devez éviter de créer un « motif arc-en-ciel » spécifique.

Le Motif Interdit

Le motif que vous tentez d'éviter est un ensemble de petits groupes de personnes déconnectés :

1. $k$ groupes de trois personnes alignés (un chemin de 3 sommets, ou $P_3$).
2. $t$ paires de personnes se tenant ensemble (un couplage de 2 sommets, ou $P_2$).

Un motif « arc-en-ciel » signifie que chaque poignée de main au sein de ces groupes spécifiques doit avoir une couleur différente de toutes les autres poignées de main du groupe. Si même deux poignées de main dans le motif partagent une couleur, le motif est « brisé » et vous êtes en sécurité.

La Grande Question

L'article pose la question suivante : Quel est le nombre maximum de couleurs différentes que vous pouvez utiliser pour peindre toutes les poignées de main de la fête sans créer accidentellement ce motif arc-en-ciel interdit ?

Dans le monde des mathématiques, ce nombre maximum est appelé le Nombre Anti-Ramsey.

La Lutte Précédente

Pendant longtemps, les mathématiciens connaissaient la réponse à cette question, mais uniquement dans des conditions très strictes. C'était comme dire : « Nous connaissons la réponse si le nombre de paires ($t$) est énorme par rapport au nombre de triplets ($k$). » Plus précisément, les recherches antérieures exigeaient que $t$ soit approximativement le carré de $k$ (une relation quadratique). Si $t$ était inférieur à cela, les mathématiques ne fonctionnaient pas et la réponse était inconnue.

La Nouvelle Découverte

Cet article résout l'énigme pour le scénario le plus critique et le plus délicat : Le Cas « Couvrant » (Spanning).

Considérez le « Cas Couvrant » comme le moment où la fête est parfaitement remplie. Le nombre total d'invités ($n$) est exactement égal au nombre de personnes nécessaires pour former votre motif interdit :

• $n = 3 \times (\text{nombre de triplets}) + 2 \times (\text{nombre de paires})$
• $n = 3k + 2t$

Les auteurs, Ali Ghalavand et Xueliang Li, ont prouvé que vous n'avez plus besoin que $t$ soit énorme. Tant que vous avez au moins un triplet ($k \ge 1$) et au moins deux paires ($t \ge 2$), ils ont trouvé la formule exacte du nombre maximum de couleurs.

La Formule

L'article affirme que le nombre maximum de couleurs que vous pouvez utiliser est :
$$\frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$$

Que signifie cela en langage courant ?
Si vous essayez d'utiliser une couleur de plus que ce nombre, vous êtes mathématiquement garanti de créer accidentellement le motif arc-en-ciel interdit (les $k$ triplets et les $t$ paires avec toutes des couleurs uniques). Mais si vous vous en tenez à ce nombre ou à un nombre inférieur, vous pouvez disposer les couleurs de manière à ce que le motif n'apparaisse jamais.

Comment Ils L'Ont Prouvé

Les auteurs ont utilisé une stratégie astucieuse de « diviser pour régner », qu'ils ont décomposée en 16 scénarios différents (comme vérifier chaque façon possible d'arranger les couleurs) :

1. La Majoration (La Voie « Sûre ») : Ils ont montré une façon de colorer le graphe avec le nombre de couleurs donné par la formule sans créer le motif. Imaginez prendre une grande partie de la fête, la colorer entièrement de manière unique, puis peindre toutes les poignées de main restantes avec une seule nouvelle couleur. Cela brise tout motif arc-en-ciel potentiel car les poignées de main « supplémentaires » partagent une couleur.
2. La Minoration (La Voie « Dangereuse ») : Ils ont prouvé que si vous essayez d'utiliser ne serait-ce qu'une couleur de plus, vous êtes contraint de créer le motif. Ils ont fait cela en supposant que vous n'avez pas créé le motif, puis en montrant que, mathématiquement, cela conduit à une contradiction (comme essayer d'enfoncer un clou carré dans un trou rond). Ils ont analysé chaque façon possible dont les couleurs pourraient être distribuées parmi les invités « supplémentaires » (les 3 personnes n'appartenant pas au groupe principal) et ont démontré que, quoi qu'il arrive, le motif finirait par apparaître.

La Conclusion

Cet article élimine la restriction de la « borne inférieure quadratique ». Il nous indique que pour le cas spécifique où la taille de la fête correspond exactement à la taille du motif interdit, la réponse est simple et universelle, indépendamment du nombre de triplets ou de paires que vous avez. C'est une solution complète à une énigme spécifique et difficile dans le domaine de la théorie des graphes.

Résumé technique

Résumé technique : Nombres anti-Ramsey pour les forêts linéaires couvrantes de chemins à 3 sommets et de couplages

Énoncé du problème
L'article étudie le nombre anti-Ramsey, noté $AR(n, G)$, pour une classe spécifique de forêts linéaires dans le graphe complet $K_n$. Un sous-graphe est défini comme arc-en-ciel si toutes ses arêtes possèdent des couleurs distinctes. Le nombre anti-Ramsey $AR(n, G)$ est le nombre maximal de couleurs dans un coloriage des arêtes de $K_n$ qui évite de contenir une copie arc-en-ciel de $G$.

Le graphe spécifique $G$ à l'étude est la forêt linéaire $kP_3 \cup tP_2$, composée de $k$ chemins disjoints de longueur 2 (3 sommets) et d'un couplage de taille $t$ (arêtes disjointes). L'objectif principal est le cas couvrant, où le nombre de sommets du graphe hôte est égal au nombre de sommets de la forêt, c'est-à-dire $n = 3k + 2t$. Alors que la littérature précédente avait abordé ce problème pour $k \ge 2$ sous des conditions restrictives sur $t$ (spécifiquement $t \ge \frac{k^2-3k+4}{2}$), ce travail vise à résoudre le cas couvrant pour tous $k \ge 1$ et $t \ge 2$ sans contraintes supplémentaires sur la relation entre $k$ et $t$.

Méthodologie
La preuve du théorème principal repose sur une combinaison d'induction et d'une analyse détaillée par cas des coloriages d'arêtes. La méthodologie est structurée comme suit :

1. Cadre inductif : La preuve procède par récurrence sur $k$. Le cas de base $k=1$ est établi en utilisant un résultat connu de He et Jin concernant $AR(n, P_3 \cup tP_2)$.
2. Lemme clé (Lemme 2.2) : Un lemme crucial est établi pour gérer l'étape de réduction. Il affirme que si un coloriage des arêtes de $K_n$ contient un nombre suffisant de couleurs (spécifiquement $\frac{1}{2}(3k+2t-3)(3k+2t-4)+2$), alors il existe un sous-graphe $K_{n-3}$ (obtenu en retirant 3 sommets) qui conserve une forte densité de couleurs distinctes, spécifiquement au moins $\frac{1}{2}(3(k-1)+2t-3)(3(k-1)+2t-4)+2$. Cela permet d'appliquer l'hypothèse de récurrence pour trouver un $(k-1)P_3 \cup tP_2$ arc-en-ciel dans $K_{n-3}$.
3. Analyse exhaustive des scénarios : Pour compléter l'induction, les auteurs analysent les arêtes reliant les sommets retirés $S = \{s_1, s_2, s_3\}$ au reste du graphe et les couleurs attribuées aux arêtes au sein de $S$. La preuve suppose l'existence d'un $(k-1)P_3 \cup tP_2$ arc-en-ciel dans $K_{n-3}$ et examine 16 scénarios distincts basés sur la distribution des couleurs des arêtes dans l'ensemble $S$ et leurs intersections avec les couleurs du sous-graphe arc-en-ciel existant.
   • Ces scénarios couvrent diverses configurations, telles que savoir si les arêtes dans $S$ introduisent de nouvelles couleurs, répètent des couleurs du sous-graphe existant, ou forment des chemins arc-en-ciel spécifiques ($P_3$) ou des couplages ($P_2$) qui peuvent être combinés avec la structure existante.
   • Pour chaque scénario, les auteurs démontrent que si le nombre total de couleurs dépasse la borne proposée, un $kP_3 \cup tP_2$ arc-en-ciel peut être construit.
   • Si une telle construction n'est pas immédiatement possible, les auteurs déduisent une contradiction en calculant le nombre maximal possible de couleurs dans $K_n$ sous l'hypothèse que les conditions spécifiques pour former le sous-graphe arc-en-ciel ne sont pas remplies. Dans tous les cas, cette borne supérieure tombe en dessous du nombre de couleurs supposé, prouvant qu'un sous-graphe arc-en-ciel doit exister.

Contributions et résultats clés
L'article établit la valeur exacte du nombre anti-Ramsey pour la forêt linéaire couvrante $kP_3 \cup tP_2$.

Théorème 1.1 : Pour les entiers positifs $k \ge 1$, $t \ge 2$, et $n = 3k + 2t$ :
$$AR(n, kP_3 \cup tP_2) = \frac{1}{2}(3k + 2t - 3)(3k + 2t - 4) + 1$$

Ce résultat confirme que le nombre maximal de couleurs dans un coloriage de $K_n$ sans $kP_3 \cup tP_2$ arc-en-ciel est exactement égal au nombre d'arêtes d'un graphe complet sur $n-3$ sommets plus un. L'article fournit une construction de borne inférieure correspondante (colorier un sous-graphe $K_{n-3}$ avec des couleurs distinctes et attribuer une nouvelle couleur unique à toutes les arêtes restantes) et prouve la borne supérieure via l'analyse exhaustive par cas décrite ci-dessus.

Signification
L'importance de ce travail réside dans la suppression de la borne inférieure quadratique sur $t$ requise dans les études précédentes. Plus précisément, un résultat antérieur de deux des auteurs (dans la référence [11]) avait déterminé ce nombre uniquement pour $t \ge \frac{k^2-3k+4}{2}$. Cet article démontre que la formule vaut pour tous $t \ge 2$, quelle que soit la magnitude de $k$.

Les auteurs caractérisent cela comme fournissant une « caractérisation complète du cas critique où le graphe hôte a exactement le même nombre de sommets que la forêt ». En résolvant le cas couvrant sans restrictions sur le rapport entre les composantes de chemins et les composantes de couplage, l'article comble une lacune significative dans la compréhension des nombres anti-Ramsey pour les forêts linéaires. Les auteurs notent que le problème ouvert restant consiste à améliorer les résultats pour le cas non couvrant ($n \ge 3k + 2t + 1$) lorsque $t$ est petit.