Subgrafos arcoíris de grafos coloreados con estrellas

Información Básica

• ID del Artículo: 2511.12505
• Título: Subgrafos arcoíris de grafos coloreados con estrellas
• Autores: Allan Lo, Klas Markström, Dhruv Mubayi, Katherine Staden, Maya Stein, Lea Weber
• Clasificación: math.CO (Combinatoria)
• Fecha de Publicación: 18 de noviembre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2511.12505

Resumen

Este artículo estudia el problema de subgrafos arcoíris en grafos coloreados con estrellas (star-coloured graphs). Una coloración de aristas de un grafo pierde la propiedad arcoíris por dos razones: contiene una cereza monocromática (un par de aristas adyacentes) o contiene un emparejamiento monocromático de tamaño 2. La coloración normal prohíbe la primera estructura, mientras que la coloración con estrellas prohíbe la segunda. El artículo determina el número máximo de colores en una coloración con estrellas del grafo completo grande que no contiene una copia arcoíris de un grafo H dado. Este es un caso especial del problema de números de Ramsey generalizados estudiado por Axenovich e Iverson, cuyos resultados el presente trabajo extiende.

Contexto de Investigación y Motivación

1. Problema de Investigación

El artículo estudia el número anti-Ramsey con estrellas (star-anti-Ramsey number) ar⋆(n,H), definido como: el número máximo de colores en una coloración con estrellas del grafo completo Kn en n vértices que no contiene una copia arcoíris del grafo H.

2. Importancia del Problema

• Significado Teórico: La teoría anti-Ramsey es un problema central en teoría extremal de grafos, estudiando el número máximo de colores necesarios para evitar estructuras específicas bajo restricciones de coloración dadas
• Generalización de Problemas Clásicos: El número anti-Ramsey clásico ar(n,H) (propuesto por Erdős et al. en 1975) estudia coloraciones de aristas arbitrarias; este artículo estudia el caso más restringido de coloraciones con estrellas
• Conexión de Múltiples Campos: Conecta coloración de grafos, teoría extremal de grafos, arboricidad de vértices (vertex arboricity) y otras ramas de la matemática combinatoria

3. Limitaciones de la Investigación Existente

• Axenovich e Iverson (2008) probaron que cuando va(H) ≥ 3, ar⋆(n,H) = (1+o(1))(1-1/(va(H)-1))(n choose 2)
• Pero cuando la arboricidad de vértices va(H) ≤ 2, solo existen cotas superiores muy gruesas ar⋆(n,H) ≤ n^(2-1/c)
• Se conoce muy poco sobre valores exactos para grafos específicos (como ciclos, grafos completos, uniones de grafos)

4. Motivación de la Investigación

Este artículo pretende llenar el vacío en el caso va(H) = 2, determinando valores exactos o asintóticos del número anti-Ramsey con estrellas para múltiples clases importantes de grafos.

Contribuciones Principales

Las principales contribuciones del artículo incluyen:

1. Resultados Exactos para Ciclos (Teorema 1.4): Para todo k ≥ 3, se prueba que ar⋆(n,Ck) = n + (k-2 choose 2) - 1, caracterizando completamente la estructura de las coloraciones extremales
2. Valor Exacto para K4 (Teorema 1.5): Se prueba que ar⋆(n,K4) = 2n - 3, siendo este el resultado técnicamente más complejo
3. Resultado Exacto para K4^- (Teorema 1.6): Se prueba que ar⋆(n,K4^-) = ⌊3(n-1)/2⌋, caracterizando todas las coloraciones extremales
4. Cotas Asintóticas para K5^- (Teorema 1.7): Se prueba que (1+o(1))(n choose 2)^(3/2) ≤ ar⋆(n,K5^-) ≤ (1+o(1))16(n choose 2)^(3/2)
5. Resultado General para Uniones de Árboles (Teorema 1.8): Para árboles T1, T2 con s,t ≥ 3 vértices, se prueba que ex(n,Ks,t^-)/2 ≤ ar⋆(n,T1+T2) ≤ cn^(2-1/s)
6. Realización de Densidades Extremales (Corolario 1.10): Se prueba que para cada entero s ≥ 1, la densidad 2-1/s es realizable con estrellas

Explicación Detallada de Métodos

Definiciones de Tareas

Coloración con estrellas: Una coloración de aristas del grafo completo Kn tal que cada clase de color induce un subgrafo que es una estrella (o un triángulo, pero este artículo excluye el caso de triángulos)

Número anti-Ramsey con estrellas: ar⋆(n,H) := max{s ∈ ℕ : existe una coloración con estrellas de s colores de Kn que no contiene una copia arcoíris de H}

Conceptos Clave:

• Arboricidad de vértices va(H): el número mínimo de partes en que se pueden dividir los vértices de modo que cada parte induce un bosque
• Arboricidad de aristas ea(H): el número mínimo de partes en que se pueden dividir las aristas de modo que cada parte induce un bosque
• Relación: va(H) ≤ ea(H) ≤ ⌈e(H)/(v(H)-1)⌉

Marco Técnico Principal

El artículo utiliza múltiples herramientas técnicas:

1. Construcciones de Coloraciones Especiales (Cotas Inferiores)

Coloración Lexicográfica (Lexical colouring) Glex_n:

• Se toma un torneo transitivo, la i-ésima estrella tiene centro vi y hojas todos los vj (j > i)
• Número de colores: n-1
• Propiedad: no contiene ciclos arcoíris (Lema 3.2)

Coloración Orientable (Orientable colouring) G^T_n:

• Dado un torneo T, la i-ésima estrella tiene centro vi
• Número de colores: n - |{v : d+(v)=0}| ∈ {n-1, n}

Coloración de Expansión Arcoíris Rn(Gn1,...,Gnℓ):

• Se usa una coloración arcoíris para el grafo de Turán Tℓ(n)
• Cada parte utiliza una coloración dada
• Número de colores: tℓ(n) + Σ|C(Gni)|

Coloración Modificada G(S):

• Se comienza con una coloración G, para cada estrella en una colección S de estrellas disjuntas en aristas se usa un nuevo color
• Se utiliza para construir subgrafos arcoíris dispersos

2. Técnicas de Cotas Superiores

Análisis de Grafos Orientados:

• Se induce un grafo orientado a partir de la coloración con estrellas: desde el centro de la estrella hacia las hojas
• Se utilizan propiedades de torneos (como el Teorema de Rédei: todo torneo tiene un camino de Hamilton dirigido)

Grafos Orientados Auxiliares:

• Se construyen grafos orientados auxiliares que capturan la estructura de la coloración
• Por ejemplo, en la prueba de K4, se define un arco −→uv cuando u es el centro de exactamente una estrella

Selección Aleatoria Dependiente (Lema 2.2):

• Para un grafo orientado G, si e(G) ≥ cn^(2-1/s), entonces existe un conjunto A de tamaño a tal que cada s-subconjunto de A tiene ≥ b vecinos de salida comunes
• Se utiliza para la prueba de la cota superior en uniones de árboles

Estrategias de Prueba de los Teoremas Principales

Estrategia de Prueba del Teorema 1.4 (Ciclos):

1. Cota Inferior: Construcción de coloración orientada modificada
   • Se toma un torneo Ck-libre T en n-k+1 vértices
   • Se añade una clique de k-1 vértices, con todos los arcos desde T hacia la clique
   • La clique se colorea de forma arcoíris
2. Cota Superior: Método de inducción
   • Si cada vértice es centro de ≥2 estrellas, entonces existe un Cn arcoíris (Lema 4.3)
   • En caso contrario, existe un vértice v que es centro de ≤1 estrella
   • Se aplica inducción sobre G-v, obteniendo una descripción estructural

Estrategia de Prueba del Teorema 1.5 (K4) (La más compleja):

Se utiliza un análisis estructural refinado:

1. Tuplas Buenas (Good tuple) P = (W,Y,Z,x,v*,cZ):
   • Descomposición de conjuntos de vértices que satisfacen 7 propiedades P1-P7
   • Clave: C(Y∪Z) = C(Y) ∪ C(Z) ∪ {cZ}
2. Construcción en Tres Pasos:
   • Lema 6.1: Si ⊛(x) ≥ 3, construir una tupla great
   • Lema 6.2: Mejorar la tupla great a una tupla restricted
   • Lema 6.3: Mejorar la tupla restricted a una tupla good que satisface C(G) = CP
3. Completación de la Inducción:
   • |C(G)| ≤ |C(W)| + |C(Y)| + |C(Z)| + 1
   • Se aplica recursivamente la hipótesis de inducción a W, Y, Z

Estrategia de Prueba del Teorema 1.6 (K4^-):

1. Cota Inferior: Modificación de coloración lexicográfica
   • Base: coloración lexicográfica (n-1 colores)
   • Se añaden ⌊(n-1)/2⌋ aristas arcoíris disjuntas en aristas
2. Cota Superior: Inducción + análisis estructural
   • Se analiza el emparejamiento M: el subgrafo inducido por aristas de color único
   • M es como máximo un emparejamiento más un camino de 2 aristas o un triángulo
   • Se prueba que e(M) ≥ ⌈n/2⌉

Estrategia de Prueba del Teorema 1.8 (Uniones de Árboles):

1. Cota Superior: Selección aleatoria dependiente
   • Se orienta cada estrella desde su centro
   • Se encuentra un conjunto A de nar⋆(T1) vértices tal que cada s-subconjunto tiene ≥nar⋆(T2)+s-1 vecinos de salida comunes
   • Se incrusta T1 en A y T2 en los vecinos de salida comunes
2. Cota Inferior: Modificación de coloración lexicográfica
   • Lema clave 7.2: T1+T2 menos cualquier bosque F contiene un ciclo impar o Ks,t^-
   • Se utiliza ex(n,Ks,t^-) ≥ Ω(n^(2-1/s))

Configuración Experimental

Este es un artículo de matemática pura teórica que no involucra experimentos. Todos los resultados se obtienen mediante pruebas matemáticas rigurosas.

Herramientas Principales

1. Resultados Clásicos de Teoría Extremal de Grafos:
   • Teorema de Kővári-Sós-Turán
   • Teorema de Erdős-Stone
   • Cotas conocidas para el problema de Zarankiewicz
2. Estructuras Combinatorias:
   • Teoría de torneos
   • Grafos de Turán
   • Uniones de árboles
3. Método Probabilístico:
   • Selección aleatoria dependiente
   • Desigualdad de Chernoff

Resultados Experimentales

Resumen de Resultados Principales

Caracterización Estructural

Coloraciones Extremales del Teorema 1.4 (Ciclos):

• Existen conjuntos de vértices A, B de tamaños n-k+1 y k-1
• La orientación se obtiene de un torneo Ck-libre T en A
• Todos los arcos de A a B van desde A hacia B
• La coloración en B es arcoíris

Coloraciones Extremales del Teorema 1.6 (K4^-):

• Para n impar: ordenamiento de vértices v1,...,vn, arista vivj coloreada con min{i,j}, más ⌊n/2⌋ aristas arcoíris
• Para n par: similar pero permitiendo una estructura especial de 3 vértices

Hallazgos Importantes

1. ar(n,H) y ar⋆(n,H) pueden diferir significativamente:
   • ar(n,K4) = ex(n,K3) + 1 = Θ(n²)
   • ar⋆(n,K4) = 2n - 3 = Θ(n)
2. Realización de Densidades Extremales:
   • Se prueba que 2-1/s es realizable con estrellas para todo s≥1
   • Se plantea la Pregunta 1.9: ¿Cuáles r∈1,2 son realizables con estrellas?
3. El Comportamiento de Grafos con ea(H)=2 es Complejo:
   • Cuando ea(H)≥3, ar⋆(n,H) es superlineal
   • Cuando ea(H)=2, puede ser lineal (conjetura)

Trabajo Relacionado

1. Teoría Anti-Ramsey

Número Anti-Ramsey Clásico 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
• Cota general: ex(n,FH^-) + 1 ≤ ar(n,H) ≤ ex(n,H)

2. Subgrafos Arcoíris en Coloraciones Normales

• Maamoun-Meyniel (1989): Existe una coloración normal de Kn sin camino de Hamilton arcoíris
• Andersen (1989): Conjetura que se puede garantizar un camino arcoíris de longitud n-2
• Alon-Pokrovskiy-Sudakov (2017): Prueba la existencia de un camino arcoíris de longitud n-o(n)

3. Números de Ramsey Generalizados

Axenovich-Iverson (2008):

• Estudian RF(n,H): número máximo de colores evitando F monocromático y H arcoíris
• Prueban que cuando F no es una estrella, el valor asintótico de RF(n,H) está determinado por va(H)
• Resultado de este artículo: ar⋆(n,H) = R{M2,K3}(n,{H})

4. Teoría Extremal de Grafos

• Teorema de Erdős-Stone: Cuando χ(H)≥3, ex(n,H) = (1-1/(χ(H)-1)+o(1))(n choose 2)
• Problema de Zarankiewicz: Cotas para z(m,n;s,t)
• Densidad de Turán: Cuáles r∈1,2 son realizables extremalmente

Conclusiones y Discusión

Conclusiones Principales

1. Resolución Completa de Múltiples Casos Importantes con va(H)=2:
   • Ciclos: valores exactos y caracterización estructural
   • Grafos completos pequeños: valores exactos para K3, K4, K4^-
   • Uniones de árboles: órdenes asintóticos
2. Establecimiento de un Nuevo Marco Técnico:
   • Método de tuplas buenas para manejar estructuras complejas
   • Construcciones de coloraciones modificadas para cotas inferiores
   • Selección aleatoria dependiente para cotas superiores
3. Conexión de Múltiples Campos Matemáticos:
   • Coloración con estrellas y arboricidad de vértices
   • Teoría extremal de grafos y teoría de Ramsey
   • Teoría de torneos

Limitaciones

1. Caracterización Incompleta de Coloraciones Extremales para K4^- y Grafos Mayores:
   • K4 tiene múltiples coloraciones extremales, el artículo no proporciona una clasificación completa
   • Los valores exactos para K5 y grafos completos mayores permanecen desconocidos
2. Teoría General Incompleta para ea(H)=2:
   • Se conjetura que ar⋆(n,H) = Θ(n) cuando ea(H)=2, pero no se prueba
   • El comportamiento de grafos 4-regulares no está claro
3. Existencia de Brechas en las Cotas para Uniones de Árboles:
   • Las cotas superior e inferior difieren por un factor constante
   • Las constantes exactas no se han determinado
4. Conjunto de Densidades Realizables con Estrellas No Completamente Determinado:
   • Solo se prueba la realizabilidad de 2-1/s
   • Pregunta 1.9: ¿Cuáles r∈1,2 son realizables con estrellas?

Direcciones Futuras

El artículo propone múltiples problemas abiertos en la Sección 8:

Pregunta 8.1: Determinar los valores exactos de ar⋆(n,Kk) (k≥5)

Pregunta 8.2: Caracterizar grafos H que satisfacen ar⋆(n,H) = Θ(n)

• Conocido: ea(H)≥3 ⟹ ar⋆(n,H) es superlineal
• Conjetura: ea(H)=2 ⟹ ar⋆(n,H) = Θ(n)

Pregunta 8.5: Probar o refutar que ar⋆(n,H) = Θ(n) cuando ea(H)=2

Otras Direcciones:

• Cubo tridimensional Q3: ar⋆(n,Q3) ≥ 2n+21, ¿es Θ(n)?
• Comportamiento de grafos 4-regulares
• Cotas más precisas para uniones de árboles

Evaluación Profunda

Fortalezas

1. Profundidad Técnica:
   • La prueba de K4 es extremadamente refinada, introduciendo conceptos jerárquicos de tuplas buenas, great, restricted
   • Combinación innovadora de múltiples herramientas técnicas (grafos orientados, grafos auxiliares, inducción)
2. Completitud de Resultados:
   • No solo proporciona valores numéricos, sino que caracteriza estructuras de coloraciones extremales (Ck, K4^-)
   • Estudio sistemático desde grafos específicos hasta clases generales (uniones de árboles)
3. Contribución Teórica:
   • Llena un vacío importante en los resultados de Axenovich-Iverson
   • Establece conexiones profundas entre coloración con estrellas y teoría extremal de grafos
   • Plantea nuevos problemas sobre densidades realizables con estrellas
4. Claridad de Exposición:
   • Estructura bien organizada, progresando de lo simple a lo complejo
   • Lemas preparatorios suficientes
   • Explicaciones claras de estrategias de prueba
5. Innovación Metodológica:
   • Sistematización de técnicas de coloración modificada
   • Marco de tuplas buenas para manejar restricciones complejas
   • Nuevas aplicaciones de selección aleatoria dependiente a problemas de coloración

Debilidades

1. Caracterización Incompleta de Coloraciones Extremales para K4:
   • El artículo reconoce la existencia de múltiples coloraciones extremales pero no proporciona una clasificación completa
   • Esto puede ser una dificultad inherente al problema, pero deja un vacío teórico
2. Algunas Pruebas son Extensas:
   • La prueba de K4 ocupa una cantidad significativa de espacio (Sección 6)
   • Aunque necesario, puede afectar la legibilidad
3. Existencia de Brechas:
   • Las cotas superior e inferior para K5^- difieren por un factor constante de 16
   • Las cotas para uniones de árboles no son suficientemente ajustadas
4. Abundancia de Problemas Abiertos:
   • Aunque plantea problemas importantes, muchos casos básicos (como Kk, k≥5) permanecen sin resolver
   • La conjetura sobre ea(H)=2 no se prueba
5. Discusión Limitada de Aplicaciones:
   • Como artículo de matemática pura, no discute posibles aplicaciones
   • Las conexiones con informática teórica y teoría de redes no se exploran

Impacto

1. Impacto Teórico:
   • Abre el estudio sistemático de la teoría anti-Ramsey con coloración de estrellas
   • Proporciona metodología para manejar casos con va(H)=2
   • Conecta múltiples ramas de la matemática combinatoria
2. Direcciones de Investigación Posterior:
   • Estimula investigación sobre densidades realizables con estrellas
   • Impulsa desarrollo de teoría para casos con ea(H)=2
   • Proporciona problemas concretos para investigación futura
3. Contribución Técnica:
   • El método de tuplas buenas puede aplicarse a otros problemas de coloración
   • Las técnicas de coloración modificada pueden generalizarse
   • Nuevas aplicaciones de selección aleatoria dependiente
4. Limitaciones:
   • Como resultado de matemática pura, la aplicación directa es limitada
   • Requiere conocimiento considerable de matemática combinatoria para comprender

Escenarios de Aplicabilidad

1. Investigación Teórica:
   • Investigadores en teoría extremal de grafos
   • Investigadores en teoría de Ramsey
   • Investigadores en teoría de coloración de grafos
2. Problemas Relacionados:
   • Investigación de arboricidad de vértices/aristas
   • Números de Ramsey generalizados
   • Problemas de realización de densidades extremales
3. Préstamo de Métodos:
   • Problemas de coloración que requieren análisis estructural refinado
   • Problemas que requieren construcción de ejemplos extremales
   • Problemas que involucran análisis de grafos orientados

Referencias (Literatura Clave)

1. Erdős, Simonovits, Sós (1975): Teoremas Anti-Ramsey - Establece los fundamentos de la teoría anti-Ramsey
2. Axenovich, Iverson (2008): Coloraciones de aristas evitando subgrafos arcoíris y monocromáticos - Trabajo que este artículo extiende directamente
3. Erdős, Stone (1946): Sobre la estructura de grafos lineales - Teorema fundamental de teoría extremal de grafos
4. Kővári, Sós, Turán (1954): Sobre un problema de K. Zarankiewicz - Resultado clásico del problema de Zarankiewicz
5. Fox, Sudakov (2011): Selección aleatoria dependiente - Herramienta probabilística clave utilizada en este artículo

Evaluación General: Este es un artículo de alta calidad en matemática combinatoria teórica que estudia sistemáticamente el problema anti-Ramsey en grafos coloreados con estrellas, proporcionando resultados exactos o asintóticos en múltiples casos importantes. La profundidad técnica es alta, particularmente la prueba de K4 que demuestra técnicas combinatorias sofisticadas. El artículo no solo resuelve problemas concretos sino que establece un marco metodológico para abordar este tipo de problemas, planteando además preguntas abiertas importantes. Para investigadores en teoría extremal de grafos y teoría de Ramsey, este es un artículo de referencia esencial.