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

Triángulos arcoíris que comparten un vértice común o una arista

Información Básica

  • ID del Artículo: 2302.00851
  • Título: Rainbow triangles sharing one common vertex or edge
  • Autores: Xiaozheng Chen (Universidad de Zhengzhou), Bo Ning (Universidad de Nankai)
  • Clasificación: math.CO (Matemática Combinatoria)
  • Fecha de Publicación: 2 de febrero de 2023 (preimpresión en arXiv)
  • Enlace del Artículo: https://arxiv.org/abs/2302.00851

Resumen

Este artículo investiga el problema de existencia de triángulos arcoíris en grafos con aristas coloreadas. Para un grafo GG con aristas coloreadas de nn vértices, el grado cromático de un vértice vv se define como dc(v)d^c(v), que representa la cantidad de colores distintos utilizados en las aristas adyacentes a vv. El grado cromático mínimo se denota como δc(G)=min⁡{dc(v):v∈V(G)}\delta^c(G)=\min\{d^c(v):v\in V(G)\}. El teorema de H. Li establece que cuando δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2}, el grafo GG contiene un triángulo arcoíris. Inspirados por esto, los autores investigan estructuras de libros (books) y grafos de amistad (friendship graphs) en grafos con aristas coloreadas. Los resultados principales demuestran que: cuando δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} y n≥3k−2n\geq 3k-2, GG contiene kk triángulos arcoíris que comparten una arista; cuando δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} y n≥2k+9n\geq 2k+9, GG contiene kk triángulos arcoíris que comparten un vértice.

Antecedentes de Investigación y Motivación

Contexto del Problema

  1. Problema Clásico de Triángulos: Mantel (1907) demostró que un grafo sin triángulos de nn vértices tiene como máximo ⌊n24⌋\lfloor\frac{n^2}{4}\rfloor aristas
  2. Triángulos Estructurados: Erdős y otros investigaron los números de Turán para el grafo libro BkB_k (kk triángulos que comparten una arista) y el grafo de amistad FkF_k (kk triángulos que comparten un vértice)
  3. Subgrafos Arcoíris: Los subgrafos arcoíris y los subgrafos correctamente coloreados están estrechamente relacionados con muchas propiedades de grafos, como resultados de estabilidad clásicos, la conjetura de Bermond-Thomassen y la conjetura de Caccetta-Häggkvist

Motivación de la Investigación

  1. Generalización del Teorema de H. Li: H. Li (2013) demostró que la condición de grado cromático mínimo δc(G)≥n+12\delta^c(G)\geq \frac{n+1}{2} garantiza la existencia de un triángulo arcoíris
  2. Triángulos Arcoíris Estructurados: Es natural considerar el caso de múltiples triángulos arcoíris que comparten vértices o aristas
  3. Conexión con Teoría de Grafos Clásica: Generalizar los conceptos clásicos de grafos libro y grafos de amistad a la configuración de grafos con aristas coloreadas

Limitaciones de Métodos Existentes

La investigación existente sobre triángulos arcoíris se concentra principalmente en la existencia de triángulos individuales, con menos investigación sobre arreglos estructurados de múltiples triángulos arcoíris (como compartir vértices o aristas).

Contribuciones Principales

  1. Teorema Principal 3: Demuestra que cuando δc(G)≥n+k−12\delta^c(G)\geq \frac{n+k-1}{2} y n≥3k−2n\geq 3k-2, el grafo GG contiene kk triángulos arcoíris que comparten una arista (grafo libro con aristas coloreadas BkB_k)
  2. Teorema Principal 4: Demuestra que cuando δc(G)≥n+2k−32\delta^c(G)\geq \frac{n+2k-3}{2} y n≥2k+9n\geq 2k+9, el grafo GG contiene kk triángulos arcoíris que comparten un vértice (grafo de amistad con aristas coloreadas FkF_k)
  3. Mejora del Teorema de H. Li: Cuando k=2k=2, ambos resultados principales mejoran el teorema original de H. Li
  4. Innovación Técnica: Combina la técnica de ciclos arcoíris de Czygrinow y otros con técnicas de conteo recientes
  5. Análisis de Extremalidad: Proporciona análisis de la rigidez de los resultados y construcciones extremales

Explicación Detallada de Métodos

Definición de Tareas

Entrada: Grafo G=(V,E)G=(V,E) con aristas coloreadas, donde ∣V∣=n|V|=n, función de coloreo de aristas C:E→{1,2,…,k}C:E\to \{1,2,\ldots,k\}Salida: Determinar si GG contiene kk triángulos arcoíris que comparten una arista (o un vértice) Restricciones: El grado cromático mínimo δc(G)\delta^c(G) satisface un umbral específico

Conceptos Técnicos Principales

1. Definiciones Relacionadas con Grado Cromático

  • Grado Cromático: dc(v)=∣{C(uv):u∈N(v)}∣d^c(v) = |\{C(uv) : u \in N(v)\}|
  • α\alpha-Vecindario: Nα(v)={u∈N(v):C(uv)=α}N_\alpha(v) = \{u \in N(v) : C(uv) = \alpha\}
  • Grado Monocromático: dmon(v)=max⁡{∣Nα(v)∣:α∈C(G)}d^{mon}(v) = \max\{|N_\alpha(v)| : \alpha \in C(G)\}

2. Técnica de Coloreo Restringido

Introducción del concepto de "coloreo restringido" de Czygrinow y otros:

  • Para un vértice vv y X⊆N(v)X \subseteq N(v), si α=C(xy)\alpha = C(xy) tal que vxyvxy constituye un P3P_3 arcoíris y α∉C(y,N(y)∖X)\alpha \notin C(y, N(y)\setminus X), entonces se dice que (v,X)(v,X) restringe el color α\alpha para yy
  • Se denota σv,X(y)\sigma_{v,X}(y) como el número de colores restringidos por (v,X)(v,X)

3. Conteo de Triángulos Arcoíris

  • rt(v)rt(v): Número de triángulos arcoíris que contienen el vértice vv
  • rt(v,x)rt(v,x): Número de triángulos arcoíris que contienen simultáneamente los vértices vv y xx
  • rt(v,X)=∑x∈Xrt(v,x)rt(v,X) = \sum_{x \in X} rt(v,x)

Lemas Clave

Lema 7 (Lema de Conteo)

Para un grafo minimal en aristas GG y un vértice vv, se tiene: 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))

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

Lema 9 (Análisis de Grado Monocromático)

Para un vértice vv con grado monocromático máximo, se tiene B(v)≥0B(v) \geq 0, y cuando B(v)=0B(v) = 0 existen propiedades estructurales especiales.

Estrategia de Demostración

Línea de Demostración del Teorema 3

  1. Asumir que no existen kk triángulos arcoíris que comparten una arista
  2. Seleccionar un vértice vv con grado monocromático máximo
  3. Utilizar la desigualdad de conteo del Lema 7
  4. Demostrar por contradicción la existencia de la estructura requerida

Línea de Demostración del Teorema 4

  1. Utilizar la teoría de números de Turán sobre emparejamientos de Erdős-Gallai
  2. Construir un grafo auxiliar G△(v)G^\triangle(v) (formado por aristas de triángulos arcoíris que contienen vv)
  3. Analizar el número de cobertura y emparejamiento de G△(v)G^\triangle(v)
  4. Obtener una contradicción mediante análisis refinado de grados

Configuración Experimental

Construcciones Extremales

Ejemplo 1: Construir un grafo tripartito completo equilibrado G[V1,V2,V3]G[V_1,V_2,V_3], donde ∣V(G)∣=3k−3|V(G)|=3k-3, ∣V1∣=∣V2∣=∣V3∣=k−1|V_1|=|V_2|=|V_3|=k-1, con coloreo correcto. Este grafo satisface dc(v)=n+k−12d^c(v) = \frac{n+k-1}{2} pero no contiene BkB_k o FkF_k, demostrando la rigidez de la condición "n≥3k−2n \geq 3k-2" en el Teorema 3.

Análisis Comparativo

El artículo compara los resultados con los siguientes resultados clásicos:

  • Teorema de H. Li: δc(G)≥n+12\delta^c(G) \geq \frac{n+1}{2} garantiza un triángulo arcoíris
  • Resultados de Erdős y otros: Números de Turán clásicos para grafos libro y grafos de amistad
  • Caso de Grafos sin Color: Condiciones de grado mínimo correspondientes

Resultados Experimentales

Comparación de Resultados Principales

EstructuraCondición en este ArtículoRequisito de VérticesCondición de H. LiMejora
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}Mejora Constructiva
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}Mejora Constructiva
BkB_kδc≥n+k−12\delta^c \geq \frac{n+k-1}{2}n≥3k−2n \geq 3k-2-Resultado Nuevo
FkF_kδc≥n+2k−32\delta^c \geq \frac{n+2k-3}{2}n≥2k+9n \geq 2k+9-Resultado Nuevo

Análisis de Rigidez

  • Rigidez del Teorema 3: El Ejemplo 1 muestra que cuando n≤3k−3n \leq 3k-3 se requiere una condición de grado cromático más fuerte δc≥n+k2\delta^c \geq \frac{n+k}{2}
  • Rigidez Asintótica: Cuando k=o(n)k = o(n), el resultado es asintóticamente riguroso

Trabajos Relacionados

Investigación sobre Triángulos Arcoíris

  1. H. Li (2013): Primer demostración de que la condición de grado cromático δc≥n+12\delta^c \geq \frac{n+1}{2} garantiza un triángulo arcoíris
  2. B. Li y otros (2014): Demuestran que la condición más débil ∑vdc(v)≥n(n+1)2\sum_{v} d^c(v) \geq \frac{n(n+1)}{2} también es suficiente
  3. X. Li y otros (2022): Proporcionan una versión de conteo para triángulos arcoíris

Resultados Clásicos de Teoría de Grafos

  1. Mantel (1907): Cota superior del número de aristas en grafos sin triángulos
  2. Erdős-Edwards-Khadžiivanov-Nikiforov: Números de Turán para grafos libro
  3. Erdős y otros (1995): Números de Turán para grafos de amistad

Métodos Técnicos

  1. Czygrinow y otros (2021): Técnica de coloreo restringido para ciclos arcoíris
  2. Erdős-Gallai (1959): Teoría de números de Turán sobre emparejamientos

Conclusiones y Discusión

Conclusiones Principales

  1. Se generaliza exitosamente el resultado clásico de H. Li sobre triángulos arcoíris al caso de múltiples triángulos que comparten estructuras
  2. Se establecen condiciones suficientes para la existencia de grafos libro y grafos de amistad en grafos con aristas coloreadas
  3. Se proporciona análisis de rigidez y construcciones extremales de los resultados

Limitaciones

  1. Requisito de Vértices: La condición n≥2k+9n \geq 2k+9 en el Teorema 4 es relativamente fuerte
  2. Complejidad Técnica: La demostración involucra múltiples técnicas de conteo complejas y análisis estructural
  3. Grado de Generalización: Los resultados se enfocan principalmente en patrones de compartición específicos (arista única o vértice único)

Direcciones Futuras

  1. Patrones de Compartición Más Generales: Investigar arreglos más complejos de triángulos arcoíris
  2. Otras Estructuras Arcoíris: Generalizar a ciclos arcoíris, caminos arcoíris, etc.
  3. Problemas Algorítmicos: Diseñar algoritmos eficientes para encontrar estas estructuras
  4. Grafos Aleatorios: Resultados correspondientes en grafos con coloreo de aristas aleatorio

Evaluación Profunda

Fortalezas

  1. Contribución Teórica Significativa: Generalización exitosa de un resultado clásico importante, estableciendo un nuevo marco teórico
  2. Innovación Técnica: Combinación ingeniosa de múltiples técnicas modernas (coloreo restringido, métodos de conteo, teoría de Turán)
  3. Completitud de Resultados: No solo proporciona resultados de existencia, sino que también analiza rigidez y casos extremales
  4. Escritura Clara: Estructura del artículo razonable, línea de demostración clara

Deficiencias

  1. Complejidad de Demostración Alta: Muchos detalles técnicos que pueden afectar la accesibilidad de los resultados
  2. Alcance de Aplicación: Principalmente resultados teóricos, con escenarios de aplicación práctica poco claros
  3. Factores Constantes: Algunos factores constantes en las condiciones (como 2k+92k+9) pueden no ser óptimos

Impacto

  1. Valor Teórico: Proporciona nuevas direcciones de investigación para la combinatoria extremal y la teoría de subgrafos arcoíris
  2. Contribución Metodológica: Las técnicas de demostración pueden ser aplicables a otros problemas similares
  3. Investigación Posterior: Sienta las bases para investigación adicional en problemas relacionados

Escenarios Aplicables

Esta investigación es principalmente aplicable a:

  1. Investigación teórica en combinatoria extremal
  2. Teoría de coloreo de grafos
  3. Problemas de existencia en teoría de grafos estructurales
  4. Problemas de detección de subestructuras en optimización combinatoria

Referencias

El artículo cita 29 referencias importantes, incluyendo:

  • 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
  • Múltiples referencias clásicas en los campos de matemática combinatoria y teoría de grafos