Sous-graphes arc-en-ciel de graphes colorés en étoile

Informations de base

• ID de l'article : 2511.12505
• Titre : Rainbow subgraphs of star-coloured graphs
• Auteurs : Allan Lo, Klas Markström, Dhruv Mubayi, Katherine Staden, Maya Stein, Lea Weber
• Classification : math.CO (Combinatoire)
• Date de publication : 18 novembre 2025
• Lien de l'article : https://arxiv.org/abs/2511.12505

Résumé

Cet article étudie le problème des sous-graphes arc-en-ciel dans les graphes colorés en étoile (star-coloured graphs). Une coloration de bord perd sa propriété arc-en-ciel pour deux raisons : elle contient une cerise monochromatique (une paire d'arêtes adjacentes) ou elle contient un appariement monochromatique de taille 2. La coloration propre interdit la première structure, tandis que la coloration en étoile interdit la seconde. L'article détermine le nombre maximal de couleurs dans une coloration en étoile du graphe complet Kn qui ne contient pas de copie arc-en-ciel d'un graphe donné H. Il s'agit d'un cas particulier du problème des nombres de Ramsey généralisés étudié par Axenovich et Iverson, et cet article étend leurs résultats.

Contexte et motivation de la recherche

1. Problème de recherche

Cet article étudie le nombre anti-Ramsey en étoile (star-anti-Ramsey number) ar⋆(n,H), défini comme : le nombre maximal de couleurs dans une coloration en étoile de Kn sur n sommets qui ne contient pas de copie arc-en-ciel du graphe H.

2. Importance du problème

• Signification théorique : La théorie anti-Ramsey est un problème central de la théorie extrémale des graphes, étudiant le nombre maximal de couleurs nécessaires pour éviter des structures spécifiques sous des restrictions de coloration données
• Généralisation de problèmes classiques : Le nombre anti-Ramsey classique ar(n,H) (introduit par Erdős et al. en 1975) étudie les colorations de bords arbitraires ; cet article étudie le cas plus restreint des colorations en étoile
• Connexion entre plusieurs domaines : Relie la coloration de graphes, la théorie extrémale des graphes, l'arboricité des sommets (vertex arboricity) et d'autres branches des mathématiques combinatoires

3. Limitations de la recherche existante

• Axenovich et Iverson (2008) ont prouvé que lorsque va(H) ≥ 3, ar⋆(n,H) = (1+o(1))(1-1/(va(H)-1))(n choose 2)
• Cependant, lorsque l'arboricité des sommets va(H) ≤ 2, seules des bornes supérieures très grossières ar⋆(n,H) ≤ n^(2-1/c) sont connues
• Les valeurs exactes pour des graphes spécifiques (comme les cycles, les graphes complets, les jointures de graphes) sont peu connues

4. Motivation de la recherche

Cet article vise à combler le vide dans le cas va(H) = 2, en déterminant les valeurs exactes ou asymptotiques du nombre anti-Ramsey en étoile pour plusieurs classes importantes de graphes.

Contributions principales

Les principales contributions de cet article incluent :

1. Résultats exacts pour les cycles (Théorème 1.4) : Pour tout k ≥ 3, on prouve que ar⋆(n,Ck) = n + (k-2 choose 2) - 1, et on caractérise complètement la structure des colorations extrémales
2. Valeur exacte pour K4 (Théorème 1.5) : On prouve que ar⋆(n,K4) = 2n - 3, ce qui est le résultat techniquement le plus complexe
3. Résultat exact pour K4^- (Théorème 1.6) : On prouve que ar⋆(n,K4^-) = ⌊3(n-1)/2⌋, et on caractérise toutes les colorations extrémales
4. Bornes asymptotiques pour K5^- (Théorème 1.7) : On prouve que (1+o(1))(n choose 2)^(3/2) ≤ ar⋆(n,K5^-) ≤ (1+o(1))16(n choose 2)^(3/2)
5. Résultat général pour les jointures d'arbres (Théorème 1.8) : Pour les arbres T1, T2 sur s, t ≥ 3 sommets, on prouve que ex(n,Ks,t^-)/2 ≤ ar⋆(n,T1+T2) ≤ cn^(2-1/s)
6. Réalisation des densités extrémales (Corollaire 1.10) : On prouve que pour chaque entier s ≥ 1, la densité 2-1/s est réalisable en étoile

Explication détaillée des méthodes

Définition des tâches

Coloration en étoile : Une coloration de bord du graphe complet Kn telle que chaque classe de couleur induit un sous-graphe qui est une étoile (ou un triangle, mais cet article exclut les triangles)

Nombre anti-Ramsey en étoile : ar⋆(n,H) := max{s ∈ ℕ : il existe une coloration en étoile s-colore de Kn qui ne contient pas de copie arc-en-ciel de H}

Concepts clés :

• Arboricité des sommets va(H) : le nombre minimum de parties en lesquelles on peut partitionner les sommets de sorte que chaque partie induit une forêt
• Arboricité des arêtes ea(H) : le nombre minimum de parties en lesquelles on peut partitionner les arêtes de sorte que chaque partie induit une forêt
• Relation : va(H) ≤ ea(H) ≤ ⌈e(H)/(v(H)-1)⌉

Cadre technique principal

L'article utilise plusieurs outils techniques :

1. Constructions de colorations spéciales (bornes inférieures)

Coloration lexicographique (Lexical colouring) Glex_n :

• Prendre un tournoi transitif, la i-ème étoile a vi comme centre et les feuilles sont tous les vj (j > i)
• Nombre de couleurs : n-1
• Propriété : ne contient pas de cycle arc-en-ciel (Lemme 3.2)

Coloration orientable (Orientable colouring) G^T_n :

• Étant donné un tournoi T, la i-ème étoile a vi comme centre
• Nombre de couleurs : n - |{v : d+(v)=0}| ∈ {n-1, n}

Coloration d'expansion arc-en-ciel Rn(Gn1,...,Gnℓ) :

• Utiliser une coloration arc-en-ciel pour le graphe de Turán Tℓ(n)
• Utiliser les colorations données à l'intérieur de chaque partie
• Nombre de couleurs : tℓ(n) + Σ|C(Gni)|

Coloration modifiée G(S) :

• Commencer à partir d'une coloration G, utiliser une nouvelle couleur pour chaque étoile dans un ensemble S d'étoiles disjointes en arêtes
• Utilisée pour construire des sous-graphes arc-en-ciel creux

2. Techniques pour les bornes supérieures

Analyse de graphes orientés :

• Induire une orientation à partir d'une coloration en étoile : du centre de l'étoile vers les feuilles
• Utiliser les propriétés des tournois (par exemple, le théorème de Rédei : tout tournoi a un chemin de Hamilton orienté)

Graphes orientés auxiliaires :

• Construire des graphes orientés auxiliaires qui capturent la structure de la coloration
• Par exemple, dans la preuve de K4, définir l'arc −→uv lorsque u est le centre d'exactement une étoile

Sélection aléatoire dépendante (Lemme 2.2) :

• Pour un graphe orienté G, si e(G) ≥ cn^(2-1/s), alors il existe un ensemble A de taille a tel que chaque s-sous-ensemble de A a ≥ b voisins sortants communs
• Utilisée pour la preuve de la borne supérieure pour les jointures d'arbres

Stratégies de preuve des théorèmes principaux

Preuve du Théorème 1.4 (Cycles) :

1. Borne inférieure : Construire une coloration orientée modifiée
   • Prendre un tournoi Ck-libre T sur n-k+1 sommets
   • Ajouter une clique de k-1 sommets, avec tous les arcs de T pointant vers la clique
   • Coloration arc-en-ciel à l'intérieur de la clique
2. Borne supérieure : Preuve par induction
   • Si chaque sommet est le centre de ≥2 étoiles, alors il existe un Cn arc-en-ciel (Lemme 4.3)
   • Sinon, il existe un sommet v qui est le centre de ≤1 étoile
   • Appliquer l'induction à G-v pour obtenir une description structurelle

Preuve du Théorème 1.5 (K4) - Stratégie de preuve (la plus complexe) :

Utiliser une analyse structurelle fine :

1. Tuples bons (Good tuple) P = (W,Y,Z,x,v*,cZ) :
   • Décomposition d'ensembles de sommets satisfaisant 7 propriétés P1-P7
   • Clé : C(Y∪Z) = C(Y) ∪ C(Z) ∪ {cZ}
2. Construction en trois étapes :
   • Lemme 6.1 : Si ⊛(x) ≥ 3, construire un great tuple
   • Lemme 6.2 : Améliorer le great tuple en restricted tuple
   • Lemme 6.3 : Améliorer le restricted tuple en good tuple satisfaisant C(G) = CP
3. Achèvement par induction :
   • |C(G)| ≤ |C(W)| + |C(Y)| + |C(Z)| + 1
   • Appliquer récursivement l'hypothèse d'induction à W, Y, Z

Preuve du Théorème 1.6 (K4^-) :

1. Borne inférieure : Modifier la coloration lexicographique
   • Base : coloration lexicographique (n-1 couleurs)
   • Ajouter ⌊(n-1)/2⌋ arêtes arc-en-ciel disjointes en arêtes
2. Borne supérieure : Induction + analyse structurelle
   • Analyser l'appariement M : le sous-graphe induit par les arêtes de couleur unique
   • M est au plus un appariement plus un chemin 2-arête ou un triangle
   • Prouver que e(M) ≥ ⌈n/2⌉

Preuve du Théorème 1.8 (Jointures d'arbres) :

1. Borne supérieure : Sélection aléatoire dépendante
   • Orienter chaque étoile du centre vers l'extérieur
   • Trouver un ensemble A de nar⋆(T1) sommets tel que chaque s-sous-ensemble a ≥nar⋆(T2)+s-1 voisins sortants communs
   • Plonger T1 dans A et T2 dans les voisins sortants communs
2. Borne inférieure : Modifier la coloration lexicographique
   • Lemme clé 7.2 : T1+T2 moins toute forêt F contient un cycle impair ou Ks,t^-
   • Utiliser ex(n,Ks,t^-) ≥ Ω(n^(2-1/s))

Configuration expérimentale

Cet article est un article de mathématiques théoriques pures et n'implique pas d'expériences. Tous les résultats sont obtenus par des preuves mathématiques rigoureuses.

Outils principaux

1. Résultats classiques de la théorie extrémale des graphes :
   • Théorème de Kővári-Sós-Turán
   • Théorème d'Erdős-Stone
   • Bornes connues pour le problème de Zarankiewicz
2. Structures combinatoires :
   • Théorie des tournois
   • Graphes de Turán
   • Jointures de graphes
3. Méthode probabiliste :
   • Sélection aléatoire dépendante
   • Inégalité de Chernoff

Résultats expérimentaux

Résumé des résultats principaux

Caractérisation structurelle

Colorations extrémales du Théorème 1.4 (Cycles) :

• Il existe des ensembles de sommets A et B de tailles n-k+1 et k-1
• Obtenir l'orientation à partir d'un tournoi Ck-libre T sur A
• Tous les arcs de A vers B pointent de A vers B
• Coloration arc-en-ciel à l'intérieur de B

Colorations extrémales du Théorème 1.6 (K4^-) :

• n impair : ordre des sommets v1,...,vn, vivj coloré par min{i,j}, plus ⌊n/2⌋ arêtes arc-en-ciel
• n pair : similaire mais permettant une structure spéciale de 3 sommets

Découvertes importantes

1. ar(n,H) et ar⋆(n,H) peuvent différer considérablement :
   • ar(n,K4) = ex(n,K3) + 1 = Θ(n²)
   • ar⋆(n,K4) = 2n - 3 = Θ(n)
2. Réalisation des densités extrémales :
   • Preuve que 2-1/s est réalisable en étoile pour tous les s≥1
   • Pose la question 1.9 : quels r∈1,2 sont réalisables en étoile ?
3. Le comportement des graphes avec ea(H)=2 est complexe :
   • Lorsque ea(H)≥3, ar⋆(n,H) est super-linéaire
   • Lorsque ea(H)=2, il peut être linéaire (conjecture)

Travaux connexes

1. Théorie anti-Ramsey

Nombre anti-Ramsey classique ar(n,H) (Erdős-Simonovits-Sós, 1975) :

• ar(n,Ck) = (k-2 choose 2) + n/(k-1) + O(1)
• ar(n,Kk) = ex(n,Kk-1) + 1
• Bornes générales : ex(n,FH^-) + 1 ≤ ar(n,H) ≤ ex(n,H)

2. Sous-graphes arc-en-ciel dans les colorations propres

• Maamoun-Meyniel (1989) : Il existe une coloration propre de Kn sans chemin de Hamilton arc-en-ciel
• Andersen (1989) : Conjecture qu'on peut garantir un chemin arc-en-ciel de longueur n-2
• Alon-Pokrovskiy-Sudakov (2017) : Preuve qu'il existe un chemin arc-en-ciel de longueur n-o(n)

3. Nombres de Ramsey généralisés

Axenovich-Iverson (2008) :

• Étudier RF(n,H) : nombre maximal de couleurs évitant un F monochromatique et un H arc-en-ciel
• Preuve que lorsque F n'est pas une étoile, l'asymptotique de RF(n,H) est déterminée par va(H)
• Résultat de cet article : ar⋆(n,H) = R{M2,K3}(n,{H})

4. Théorie extrémale des graphes

• Théorème d'Erdős-Stone : ex(n,H) = (1-1/(χ(H)-1)+o(1))(n choose 2) lorsque χ(H)≥3
• Problème de Zarankiewicz : bornes sur z(m,n;s,t)
• Densité de Turán : quels r∈1,2 sont réalisables comme densités extrémales

Conclusion et discussion

Conclusions principales

1. Résolution complète de plusieurs cas importants avec va(H)=2 :
   • Cycles : valeurs exactes et caractérisation structurelle
   • Petits graphes complets : valeurs exactes pour K3, K4, K4^-
   • Jointures d'arbres : ordres asymptotiques
2. Établissement d'un nouveau cadre technique :
   • Méthode des bons tuples pour traiter les structures complexes
   • Construction de colorations modifiées pour les bornes inférieures
   • Sélection aléatoire dépendante pour les bornes supérieures
3. Connexion entre plusieurs domaines mathématiques :
   • Coloration en étoile et arboricité des sommets
   • Théorie extrémale des graphes et théorie de Ramsey
   • Théorie des tournois

Limitations

1. Caractérisation incomplète des colorations extrémales pour K4^- et graphes plus grands :
   • K4 a plusieurs colorations extrémales, l'article ne donne pas de classification complète
   • Les valeurs exactes pour K5 et les graphes complets plus grands restent inconnues
2. Théorie générale incomplète pour ea(H)=2 :
   • Conjecture que ar⋆(n,H) = Θ(n) lorsque ea(H)=2, mais non prouvée
   • Le comportement des graphes 4-réguliers n'est pas clair
3. Écarts dans les bornes pour les jointures d'arbres :
   • Les bornes supérieure et inférieure diffèrent par un facteur constant
   • Les constantes exactes ne sont pas déterminées
4. Ensemble des densités réalisables en étoile non complètement déterminé :
   • Seule la réalisabilité de 2-1/s est prouvée
   • Question 1.9 : quels r∈1,2 sont réalisables en étoile ?

Directions futures

L'article propose plusieurs problèmes ouverts dans la section 8 :

Problème 8.1 : Déterminer les valeurs exactes de ar⋆(n,Kk) (k≥5)

Problème 8.2 : Caractériser les graphes H satisfaisant ar⋆(n,H) = Θ(n)

• Connu : ea(H)≥3 ⟹ ar⋆(n,H) super-linéaire
• Conjecture : ea(H)=2 ⟹ ar⋆(n,H) = Θ(n)

Problème 8.5 : Prouver ou réfuter que ar⋆(n,H) = Θ(n) lorsque ea(H)=2

Autres directions :

• Cube 3-dimensionnel Q3 : ar⋆(n,Q3) ≥ 2n+21, est-ce Θ(n) ?
• Comportement des graphes 4-réguliers
• Bornes plus précises pour les jointures d'arbres

Évaluation approfondie

Points forts

1. Profondeur technique :
   • La preuve pour K4 est extrêmement fine, introduisant des concepts hiérarchiques de bons tuples, great, restricted, etc.
   • Combinaison innovante de plusieurs outils techniques (graphes orientés, graphes auxiliaires, induction)
2. Complétude des résultats :
   • Non seulement des valeurs numériques, mais aussi caractérisation de la structure des colorations extrémales (Ck, K4^-)
   • Étude systématique allant des graphes spécifiques aux classes générales (jointures d'arbres)
3. Contribution théorique :
   • Comble un vide important dans les résultats d'Axenovich-Iverson
   • Établit des connexions profondes entre coloration en étoile et théorie extrémale des graphes
   • Pose de nouveaux problèmes sur les densités réalisables en étoile
4. Clarté de la rédaction :
   • Structure bien organisée, allant du simple au complexe
   • Lemmes préliminaires suffisants
   • Explication claire des stratégies de preuve
5. Innovation méthodologique :
   • Systématisation de la technique de coloration modifiée
   • Cadre des bons tuples pour traiter les contraintes complexes
   • Application de la sélection aléatoire dépendante aux problèmes de coloration

Insuffisances

1. Caractérisation incomplète des colorations extrémales pour K4 :
   • L'article reconnaît l'existence de plusieurs colorations extrémales mais ne donne pas de classification complète
   • Cela peut être une difficulté inhérente au problème, mais laisse un vide théorique
2. Certaines preuves sont longues :
   • La preuve pour K4 occupe une grande partie du texte (section 6)
   • Bien que nécessaire, cela peut affecter la lisibilité
3. Existence d'écarts :
   • Les bornes supérieure et inférieure pour K5^- diffèrent d'un facteur constant 16
   • Les bornes pour les jointures d'arbres ne sont pas suffisamment serrées
4. Nombreux problèmes ouverts :
   • Bien que des problèmes importants soient posés, de nombreux cas fondamentaux (comme Kk, k≥5) restent non résolus
   • La conjecture pour ea(H)=2 n'est pas prouvée
5. Discussion insuffisante des applications :
   • En tant qu'article de mathématiques pures, ne discute pas des applications possibles
   • Les connexions avec l'informatique théorique et la théorie des réseaux ne sont pas explorées

Impact

1. Impact théorique :
   • Ouvre une étude systématique de la théorie anti-Ramsey en étoile
   • Fournit une méthodologie pour traiter le cas va(H)=2
   • Relie plusieurs branches des mathématiques combinatoires
2. Directions de recherche ultérieures :
   • Stimule la recherche sur les densités réalisables en étoile
   • Favorise le développement de la théorie pour le cas ea(H)=2
   • Fournit des problèmes concrets pour la recherche ultérieure
3. Contribution technique :
   • La méthode des bons tuples peut s'appliquer à d'autres problèmes de coloration
   • La technique de coloration modifiée peut être généralisée
   • Nouvelles applications de la sélection aléatoire dépendante
4. Limitations :
   • En tant que résultat purement théorique, les applications directes sont limitées
   • Nécessite une connaissance considérable des mathématiques combinatoires pour être compris

Scénarios d'application

1. Recherche théorique :
   • Chercheurs en théorie extrémale des graphes
   • Chercheurs en théorie de Ramsey
   • Chercheurs en théorie de la coloration de graphes
2. Problèmes connexes :
   • Recherche sur l'arboricité des sommets/arêtes
   • Nombres de Ramsey généralisés
   • Problèmes de réalisation de densités extrémales
3. Emprunt de méthodes :
   • Problèmes de coloration nécessitant une analyse structurelle fine
   • Problèmes nécessitant la construction d'exemples extrémaux
   • Problèmes impliquant l'analyse de graphes orientés

Références (Références clés)

1. Erdős, Simonovits, Sós (1975) : Anti-Ramsey theorems - Pose les fondations de la théorie anti-Ramsey
2. Axenovich, Iverson (2008) : Edge-colorings avoiding rainbow and monochromatic subgraphs - Travail directement étendu par cet article
3. Erdős, Stone (1946) : On the structure of linear graphs - Théorème fondamental de la théorie extrémale des graphes
4. Kővári, Sós, Turán (1954) : On a problem of K. Zarankiewicz - Résultat classique du problème de Zarankiewicz
5. Fox, Sudakov (2011) : Dependent random choice - Outil probabiliste clé utilisé dans cet article

Évaluation générale : Ceci est un article de haute qualité en mathématiques combinatoires théoriques, étudiant systématiquement le problème anti-Ramsey pour les graphes colorés en étoile, donnant des résultats exacts ou asymptotiques dans plusieurs cas importants. La profondeur technique est élevée, en particulier la preuve pour K4 qui démontre des techniques combinatoires sophistiquées. L'article ne résout pas seulement des problèmes spécifiques, mais établit également un cadre méthodologique pour traiter ce type de problèmes et pose des problèmes ouverts importants. Pour les chercheurs en théorie extrémale des graphes et en théorie de Ramsey, ceci est une référence essentielle et incontournable.