2025-11-10T03:03:05.603358

Rainbow triangles sharing one common vertex or edge

Chen, Ning
Let $G$ be an edge-colored graph on $n$ vertices. For a vertex $v$, the \emph{color degree} of $v$ in $G$, denoted by $d^c(v)$, is the number of colors appearing on the edges incident with $v$. Denote by $δ^c(G)=\min\{d^c(v):v\in V(G)\}$. By a theorem of H. Li, an $n$-vertex edge-colored graph $G$ contains a rainbow triangle if $δ^c(G)\geq \frac{n+1}{2}$. Inspired by this result, we consider two related questions concerning edge-colored books and friendship subgraphs of edge-colored graphs. Let $k\geq 2$ be a positive integer. We prove that if $δ^c(G)\geq \frac{n+k-1}{2}$ where $n\geq 3k-2$, then $G$ contains $k$ rainbow triangles sharing one common edge; and if $δ^c(G)\geq \frac{n+2k-3}{2}$ where $n\geq 2k+9$, then $G$ contains $k$ rainbow triangles sharing one common vertex. The special case $k=2$ of both results improves H. Li's theorem. The main novelty of our proof of the first result is a combination of the recent new technique for finding rainbow cycles due to Czygrinow, Molla, Nagle, and Oursler and some recent counting technique from \cite{LNSZ}. The proof of the second result is with the aid of the machine implicitly in the work of Turán numbers for matching numbers due to Erdős and Gallai.
academic

Triangles arc-en-ciel partageant un sommet ou une arête commune

Informations de base

  • ID de l'article : 2302.00851
  • Titre : Rainbow triangles sharing one common vertex or edge
  • Auteurs : Xiaozheng Chen (Université de Zhengzhou), Bo Ning (Université de Nankai)
  • Classification : math.CO (Mathématiques combinatoires)
  • Date de publication : 2 février 2023 (prépublication arXiv)
  • Lien de l'article : https://arxiv.org/abs/2302.00851

Résumé

Cet article étudie l'existence de triangles arc-en-ciel dans les graphes à arêtes colorées. Pour un graphe GG à arêtes colorées avec nn sommets, le degré chromatique d'un sommet vv est défini par dc(v)d^c(v), représentant le nombre de couleurs distinctes utilisées par les arêtes adjacentes à vv. Le degré chromatique minimum est noté δc(G)=min⁡{dc(v):v∈V(G)}\delta^c(G)=\min\{d^c(v):v\in V(G)\}. Le théorème de H. Li établit que lorsque δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2}, le graphe GG contient un triangle arc-en-ciel. Inspirés par ce résultat, les auteurs étudient les structures de livres (books) et de graphes d'amitié (friendship graphs) dans les graphes à arêtes colorées. Les résultats principaux démontrent que : lorsque δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} et n≥3k−2n\geq 3k-2, GG contient kk triangles arc-en-ciel partageant une arête commune ; lorsque δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} et n≥2k+9n\geq 2k+9, GG contient kk triangles arc-en-ciel partageant un sommet commun.

Contexte et motivation de la recherche

Contexte du problème

  1. Problème classique des triangles : Mantel (1907) a prouvé que un graphe sans triangle à nn sommets possède au maximum ⌊n24⌋\lfloor\frac{n^2}{4}\rfloor arêtes
  2. Triangles structurés : Erdős et ses collaborateurs ont étudié les nombres de Turán pour les livres BkB_k (kk triangles partageant une arête) et les graphes d'amitié FkF_k (kk triangles partageant un sommet)
  3. Sous-graphes arc-en-ciel : Les sous-graphes arc-en-ciel et les sous-graphes correctement colorés sont étroitement liés à de nombreuses propriétés de théorie des graphes, notamment les résultats de stabilité classiques, la conjecture de Bermond-Thomassen et la conjecture de Caccetta-Häggkvist

Motivation de la recherche

  1. Généralisation du théorème de H. Li : H. Li (2013) a prouvé que la condition de degré chromatique minimum δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} garantit l'existence d'un triangle arc-en-ciel
  2. Triangles arc-en-ciel structurés : Il est naturel de considérer le cas où plusieurs triangles arc-en-ciel partagent des sommets ou des arêtes
  3. Connexion avec la théorie des graphes classique : Généralisation des concepts classiques de livres et de graphes d'amitié au cadre des graphes à arêtes colorées

Limitations des méthodes existantes

Les recherches existantes sur les triangles arc-en-ciel se concentrent principalement sur l'existence de triangles individuels, avec peu d'études sur les arrangements structurés de plusieurs triangles arc-en-ciel (tels que le partage de sommets ou d'arêtes).

Contributions principales

  1. Théorème principal 3 : Démontre que lorsque δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} et n≥3k−2n\geq 3k-2, le graphe GG contient kk triangles arc-en-ciel partageant une arête commune (livre à arêtes colorées BkB_k)
  2. Théorème principal 4 : Démontre que lorsque δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} et n≥2k+9n\geq 2k+9, le graphe GG contient kk triangles arc-en-ciel partageant un sommet commun (graphe d'amitié à arêtes colorées FkF_k)
  3. Amélioration du théorème de H. Li : Lorsque k=2k=2, les deux résultats principaux améliorent le théorème original de H. Li
  4. Innovation technique : Combine les techniques de cycles arc-en-ciel de Czygrinow et les techniques de comptage récentes
  5. Analyse de l'optimalité : Fournit une analyse de la finesse des résultats et des constructions extrémales

Explication détaillée de la méthode

Définition de la tâche

Entrée : Graphe G=(V,E)G=(V,E) à arêtes colorées, où ∣V∣=n|V|=n, fonction de coloration C:E→{1,2,…,k}C:E\to \{1,2,\ldots,k\}Sortie : Déterminer si GG contient kk triangles arc-en-ciel partageant une arête (ou un sommet) Contraintes : Le degré chromatique minimum δc(G)\delta^c(G) satisfait un seuil spécifique

Concepts et techniques fondamentaux

1. Définitions relatives au degré chromatique

  • Degré chromatique : dc(v)=∣{C(uv):u∈N(v)}∣d^c(v) = |\{C(uv) : u \in N(v)\}|
  • α\alpha-voisinage : Nα(v)={u∈N(v):C(uv)=α}N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}
  • Degré monochromatique : dmon(v)=max⁡{∣Nα(v)∣:α∈C(G)}d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}

2. Technique de coloration restreinte

Introduction du concept de « coloration restreinte » de Czygrinow et al. :

  • Pour un sommet vv et X⊆N(v)X \subseteq N(v), si α=C(xy)\alpha = C(xy) tel que vxyvxy forme un P3P_3 arc-en-ciel et α∉C(y,N(y)∖X)\alpha \notin C(y, N(y)\setminus X), alors (v,X)(v,X) restreint la couleur α\alpha pour yy
  • Notons σv,X(y)\sigma_{v,X}(y) le nombre de couleurs restreintes par (v,X)(v,X)

3. Comptage des triangles arc-en-ciel

  • rt(v)rt(v) : nombre de triangles arc-en-ciel contenant le sommet vv
  • rt(v,x)rt(v,x) : nombre de triangles arc-en-ciel contenant simultanément les sommets vv et xx
  • rt(v,X)=∑x∈Xrt(v,x)rt(v,X) = \sum_{x \in X} rt(v,x)

Lemmes clés

Lemme 7 (Lemme de comptage)

Pour un graphe minimal en arêtes GG et un sommet vv, on a : rt(v,Ni(v))≥∑x∈Ni(v)(dc(x)+dc(v)−n)+di(v)∑1≤j≤s(dj(v)−1)−di(v)(di(v)−1)−∑y∈N!(v)dvyc(y,Ni(v))rt(v,N_i(v)) \geq \sum_{x\in N_i(v)}(d^c(x) + d^c(v) - n) + d_i(v)\sum_{1\leq j\leq s}(d_j(v)-1) - d_i(v)(d_i(v)-1) - \sum_{y\in N^!(v)}d^c_{vy}(y,N_i(v))

où N!(v)=⋃α∈C(G){Nα(v):∣Nα(v)∣=1}N^!(v) = \bigcup_{\alpha\in C(G)}\{N_\alpha(v) : |N_\alpha(v)| = 1\}.

Lemme 9 (Analyse du degré monochromatique)

Pour un sommet vv ayant le degré monochromatique maximal, on a B(v)≥0B(v) \geq 0, et lorsque B(v)=0B(v) = 0, il existe des propriétés structurelles spéciales.

Stratégie de preuve

Approche de preuve du théorème 3

  1. Supposer qu'il n'existe pas kk triangles arc-en-ciel partageant une arête
  2. Sélectionner un sommet vv ayant le degré monochromatique maximal
  3. Utiliser l'inégalité de comptage du lemme 7
  4. Prouver par contradiction l'existence d'une structure satisfaisant les conditions

Approche de preuve du théorème 4

  1. Utiliser la théorie de Turán d'Erdős-Gallai concernant le nombre d'appariements
  2. Construire le graphe auxiliaire G△(v)G^\triangle(v) (composé des arêtes des triangles arc-en-ciel contenant vv)
  3. Analyser le nombre de couverture et le nombre d'appariement de G△(v)G^\triangle(v)
  4. Obtenir une contradiction par une analyse fine des degrés

Configuration expérimentale

Constructions extrémales

Exemple 1 : Construction d'un graphe 3-partite complet équilibré G[V1,V2,V3]G[V_1,V_2,V_3], où ∣V(G)∣=3k−3|V(G)|=3k-3, ∣V1∣=∣V2∣=∣V3∣=k−1|V_1|=|V_2|=|V_3|=k-1, avec coloration correcte. Ce graphe satisfait dc(v)=n+k−12d^c(v) = \frac{n+k-1}{2} mais ne contient ni BkB_k ni FkF_k, prouvant l'optimalité de la condition « n≥3k−2n \geq 3k-2 » du théorème 3.

Analyse comparative

L'article compare les résultats avec les résultats classiques suivants :

  • Théorème de H. Li : δc(G)≥n+12\delta^c(G) \geq \frac{n+1}{2} garantit un triangle arc-en-ciel
  • Résultats d'Erdős et al. : Nombres de Turán classiques pour les livres et graphes d'amitié
  • Cas non coloré : Conditions de degré minimum correspondantes

Résultats expérimentaux

Comparaison des résultats principaux

StructureCondition de cet articleExigence sur les sommetsCondition de H. LiAmélioration
B2B_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥4n \geq 4δc≥n+12\delta^c \geq \frac{n+1}{2}Amélioration constructive
F2F_2δc≥n+12\delta^c \geq \frac{n+1}{2}n≥13n \geq 13δc≥n+12\delta^c \geq \frac{n+1}{2}Amélioration constructive
BkB_kδc≥n+k−12\delta^c \geq \frac{n+k-1}{2}n≥3k−2n \geq 3k-2-Nouveau résultat
FkF_kδc≥n+2k−32\delta^c \geq \frac{n+2k-3}{2}n≥2k+9n \geq 2k+9-Nouveau résultat

Analyse de l'optimalité

  • Optimalité du théorème 3 : L'exemple 1 montre que lorsque n≤3k−3n \leq 3k-3, une condition de degré chromatique plus forte δc≥n+k2\delta^c \geq \frac{n+k}{2} est nécessaire
  • Optimalité asymptotique : Lorsque k=o(n)k = o(n), les résultats sont asymptotiquement optimaux

Travaux connexes

Recherche sur les triangles arc-en-ciel

  1. H. Li (2013) : Première preuve que la condition de degré chromatique δc≥n+12\delta^c \geq \frac{n+1}{2} garantit un triangle arc-en-ciel
  2. B. Li et al. (2014) : Preuve que la condition plus faible ∑vdc(v)≥n(n+1)2\sum_{v} d^c(v) \geq \frac{n(n+1)}{2} est également suffisante
  3. X. Li et al. (2022) : Version de comptage pour les triangles arc-en-ciel

Résultats de théorie des graphes classique

  1. Mantel (1907) : Borne supérieure sur le nombre d'arêtes des graphes sans triangle
  2. Erdős-Edwards-Khadžiivanov-Nikiforov : Nombres de Turán pour les livres
  3. Erdős et al. (1995) : Nombres de Turán pour les graphes d'amitié

Méthodes techniques

  1. Czygrinow et al. (2021) : Technique de coloration restreinte pour les cycles arc-en-ciel
  2. Erdős-Gallai (1959) : Théorie de Turán pour le nombre d'appariements

Conclusions et discussion

Conclusions principales

  1. Généralisation réussie du résultat classique de H. Li sur les triangles arc-en-ciel au cas de plusieurs triangles partageant des structures
  2. Établissement de conditions suffisantes pour l'existence de livres et de graphes d'amitié dans les graphes à arêtes colorées
  3. Fourniture d'une analyse de l'optimalité et de constructions extrémales pour les résultats

Limitations

  1. Exigences sur le nombre de sommets : La condition n≥2k+9n \geq 2k+9 du théorème 4 est relativement forte
  2. Complexité technique : La preuve implique plusieurs techniques de comptage complexes et une analyse structurelle
  3. Degré de généralisation : Les résultats se concentrent principalement sur des modèles de partage spécifiques (arête unique ou sommet unique)

Directions futures

  1. Modèles de partage plus généraux : Étude d'arrangements plus complexes de triangles arc-en-ciel
  2. Autres structures arc-en-ciel : Généralisation aux cycles arc-en-ciel, chemins arc-en-ciel, etc.
  3. Problèmes algorithmiques : Conception d'algorithmes efficaces pour trouver ces structures
  4. Graphes aléatoires : Résultats correspondants dans les graphes à coloration aléatoire

Évaluation approfondie

Points forts

  1. Contribution théorique significative : Généralisation réussie d'un résultat classique important, établissement d'un nouveau cadre théorique
  2. Innovation technique : Combinaison ingénieuse de plusieurs techniques modernes (coloration restreinte, méthodes de comptage, théorie de Turán)
  3. Complétude des résultats : Non seulement des résultats d'existence, mais aussi une analyse de l'optimalité et des cas extrémaux
  4. Clarté de la rédaction : Structure bien organisée, preuves claires et logiques

Insuffisances

  1. Complexité des preuves : Nombreux détails techniques qui peuvent affecter l'accessibilité des résultats
  2. Portée des applications : Principalement des résultats théoriques, avec des applications pratiques peu claires
  3. Facteurs constants : Certaines constantes dans les conditions (comme 2k+92k+9) peuvent ne pas être optimales

Impact

  1. Valeur théorique : Fournit de nouvelles directions de recherche pour la combinatoire extrémale et la théorie des sous-graphes arc-en-ciel
  2. Contribution méthodologique : Les techniques de preuve peuvent s'appliquer à d'autres problèmes similaires
  3. Recherche ultérieure : Jette les bases pour des recherches ultérieures sur les problèmes connexes

Scénarios d'application

Cette recherche s'applique principalement à :

  1. Recherche théorique en combinatoire extrémale
  2. Théorie de la coloration des graphes
  3. Problèmes d'existence dans la théorie structurelle des graphes
  4. Détection de sous-structures en optimisation combinatoire

Références

L'article cite 29 références importantes, notamment :

  • H. Li (2013) : Rainbow C3C_3's and C4C_4's in edge-colored graphs
  • Erdős, Füredi, Gould, Gunderson (1995) : Extremal graphs for intersecting triangles
  • Czygrinow, Molla, Nagle, Oursler (2021) : On odd rainbow cycles in edge-colored graphs
  • Et plusieurs autres références classiques dans les domaines des mathématiques combinatoires et de la théorie des graphes