Número de Turán bipartito de caminos y otros árboles

Información Básica

• ID del Artículo: 2511.07374
• Título: Número de Turán bipartito de caminos y otros árboles
• Autores: Marthe Bonamy, Théotime Leclere, Timothé Picavet
• Instituciones: CNRS, LaBRI, Université de Bordeaux; ENS Paris-Saclay
• Clasificación: math.CO (Matemática Combinatoria), cs.DM (Matemática Discreta)
• Fecha de Publicación: 11 de noviembre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2511.07374

Resumen

Este artículo resuelve completamente un problema recientemente planteado por Caro, Patkós y Tuza: determinar el máximo exacto del número de aristas en grafos bipartitos conexos, que es una función de la longitud del camino más largo y del número de vértices en ambos lados de la bipartición. Anteriormente, este problema solo se conocía en el caso donde ambos lados de la bipartición tienen tamaño igual y la longitud del camino más largo es como máximo 5. El artículo también discute posibles generalizaciones reemplazando "camino" por tipos específicos de árboles.

Antecedentes y Motivación de la Investigación

Contexto del Problema

1. Problema Clásico de Turán: El teorema de Turán determina el número máximo de aristas en un grafo de n vértices que no contiene un subgrafo completo de orden dado, iniciando el estudio sistemático de problemas extremales con subgrafos prohibidos.
2. Limitaciones del Teorema de Erdős-Stone: Este teorema proporciona asintóticamente el número de Turán para todos los grafos prohibidos no bipartitos, pero no proporciona información en el caso de grafos bipartitos.
3. Particularidad de los Grafos Bipartitos: El problema de Turán para grafos bipartitos permanece abierto, generando múltiples conjeturas fundamentales, siendo la más famosa la conjetura de Erdős-Sós: un grafo de n vértices que excluye un árbol de k vértices tiene como máximo (k-2)n/2 aristas.
4. Estudio de Grafos Bipartitos Conexos: Caro, Patkós y Tuza CPT25 recientemente enfocaron su atención en el caso donde el grafo anfitrión es tanto bipartito como conexo, introduciendo la notación exb,c(a,b,H) para denotar el número máximo de aristas en un grafo bipartito conexo con partes de tamaño a y b que no contiene H como subgrafo.

Motivación de la Investigación

• Limitaciones de Resultados Conocidos: CPT25 solo resolvió el caso de todos los árboles con 6 o menos vértices, estrellas dobles y ciertos grafos araña, en particular solo se conocía exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
• Problemas Abiertos: Se necesitaba determinar exb,c(n,n,Pₖ) para caminos arbitrarios Pₖ, al menos proporcionando valores asintóticos
• Necesidad de Generalización: Se requería investigar los valores de exb,c para familias específicas de árboles

Contribuciones Principales

1. Resolución Completa del Problema de Caminos: Para todos los caminos Pₖ, se proporcionan valores exactos de exb,c(a,b,Pₖ), no solo valores asintóticos, sino también aplicables a grafos bipartitos desbalanceados (Teorema Principal 1.5)
2. Extensión a Grafos Escoba: Para grafos escoba Sp,d* (combinación de una estrella con d ramas y un camino de longitud p), se proporcionan valores exactos cuando la estrella es más grande que el camino (Teorema 1.6)
3. Resultados de Cota Superior: Cuando la estrella es como máximo la mitad del tamaño del camino, se proporcionan cotas superiores (Teorema 1.7)
4. Innovación Técnica: Se desarrollaron nuevas técnicas para manejar grafos bipartitos conexos, incluyendo lemas de existencia de vértices críticos y marcos inductivos

Explicación Detallada de Métodos

Definición de la Tarea

Definición 1.1: Para enteros fijos a, b y un grafo H, exb,c(a,b,H) es el número máximo de aristas en un grafo bipartito conexo con partes de tamaño a y b que no contiene H como subgrafo.

Este artículo estudia principalmente:

• Entrada: Longitud del camino k, tamaños de bipartición a, b
• Salida: Valor exacto de exb,c(a,b,Pₖ)
• Restricciones: El grafo debe ser conexo, bipartito y no contener Pₖ como subgrafo

Teoremas Principales

Teorema 1.5 (Resultado Principal): Para todo k ≥ 3 y b ≥ a ≥ k, $\text{ex}_{b,c}(a,b,P_{2k}) = \text{ex}_{b,c}(a,b,P_{2k-1}) = (k-2)(b-1) + a$

Esta fórmula indica que:

• Los caminos de longitud impar y par tienen el mismo número de Turán
• El número de aristas crece linealmente con la parte más grande b, con coeficiente (k-2)
• Existe un término de corrección aditivo a

Arquitectura de la Prueba

1. Construcción de Cota Inferior (Sección 2)

Proposición 2.1 proporciona una prueba constructiva:

Se construye un grafo G con bipartición A = {u₁,...,uₐ} y B = {v₁,...,vᵦ}:

• Los primeros k-2 vértices en A están completamente conectados a todos los vértices en B (formando Kₖ₋₂,ᵦ)
• Los a-(k-2) vértices restantes en A actúan como hojas, todos conectados a un vértice específico en B

Cálculo del Número de Aristas: $|E(G)| = b(k-2) + (a-(k-2)) = (k-2)(b-1) + a$

Prueba de Propiedad P₂ₖ₋₁-libre:

• El camino más largo en el grafo bipartito completo Kₖ₋₂,ᵦ tiene 2k-3 vértices
• Las hojas añadidas no pueden extender el camino, ya que todos son vértices de grado 1

2. Prueba de Cota Superior (Sección 3)

Se utiliza inducción, siendo clave tres lemas:

Lema 3.2 (Existencia de Vértices de Pequeño Grado): En la parte más grande B existe un vértice x de grado ≤ k-2 cuya eliminación mantiene la conexidad.

Esquema de prueba:

• Se usa un árbol DFS para encontrar una hoja b en B
• Si d(b) ≤ k-2, se toma x = b
• Si d(b) = k-1, entonces la longitud del camino debe ser 2k-2, formando un ciclo
• En este caso se puede encontrar otro vértice b' de grado ≤ k-2

Lema 3.3 (Pares de Vértices Eliminables en Grafos Balanceados): Para un grafo bipartito balanceado, existen dos vértices x, y tales que d(x) + d(y) ≤ k-1 y su eliminación mantiene la conexidad y el balance.

La prueba utiliza análisis de los extremos del camino más largo P:

• Si los extremos están en diferentes partes, posiblemente se pueden usar directamente
• En caso contrario, se usa el árbol DFS para encontrar un emparejamiento adecuado de hojas

Lema 3.4 (Caso Base): Cuando a = b = k, |E(G)| ≤ (k-1)² + 1.

La prueba utiliza inducción, con la observación clave:

• Se encuentra un vértice de grado mínimo que no es punto de corte
• Se analiza la estructura del grafo restante después de su eliminación
• Se utiliza la propiedad P₂ₖ-libre para limitar el grado y la estructura

Prueba del Teorema Principal:

• Si b > a: Se usa el Lema 3.2 para eliminar un vértice, luego inducción
• Si a = b > k: Se usa el Lema 3.3 para eliminar dos vértices, luego inducción
• Si a = b = k: Se usa el Lema 3.4

Resultados para Grafos Escoba

Teorema 1.6: Para k, d ≥ 2, cuando n ≥ d²/2 y d > 2k, $\text{ex}_{b,c}(n,n,S_{2k,d}) = \text{ex}_{b,c}(n,n,S_{2k+1,d}) = nd$

Lemas técnicos clave:

Lema 4.1: Si el grafo contiene un vértice que no es extremo de un camino de longitud 2k, entonces |E(G)| ≤ (k-1)(b+a)

Lema 4.2: Si |E(G)| ≥ k(b+a)+1, entonces cada vértice tiene grado como máximo k+d-1

La prueba combina estos lemas, eliminando vértices de grado máximo y sus vecinos, utilizando conexidad y restricciones de grado para obtener una contradicción.

Configuración Experimental

Como artículo de matemática pura teórica, este trabajo no incluye una sección de experimentos, siendo todos los resultados obtenidos mediante pruebas matemáticas rigurosas.

Resultados Experimentales

Verificación de Resultados Principales

Fórmula Exacta para Caminos:

• Para P₅ y P₆: exb,c(n,n,P₅) = exb,c(n,n,P₆) = 2n-1
  • Usando la fórmula: cuando k=3, (3-2)(n-1)+n = n-1+n = 2n-1 ✓
• Para Pₖ general: La fórmula proporciona valores exactos para todos los casos, incluyendo grafos bipartitos desbalanceados

Resultados para Grafos Escoba:

• Cuando la parte de la estrella es dominante (d > 2k), el número de Turán es nd
• Esto es consistente con las restricciones de grado máximo

Comparación con Resultados Conocidos

1. Generalización de la Proposición 1.2: Los resultados de este artículo contienen completamente y generalizan exb,c(n,n,P₅) = 2n-1 de CPT25
2. Mejora de Generalidad:
   • Extensión de grafos balanceados a grafos desbalanceados
   • Extensión de caminos pequeños específicos a caminos arbitrarios
   • Transición de resultados asintóticos a fórmulas exactas

Trabajo Relacionado

Resultados Clásicos

1. Teorema de Turán Tur45: Problema extremal para grafos completos
2. Teorema de Erdős-Stone ES46: Número de Turán asintótico para grafos no bipartitos
3. Gallai-Erdős GE59: Resultados asintóticos para grafos conexos excluyendo caminos de tamaño fijo
4. Gyárfás-Rousseau-Schelp GRS84: Números de Turán exactos para grafos bipartitos excluyendo caminos de tamaño fijo

Trabajo Directamente Relacionado

Caro-Patkós-Tuza CPT25:

• Introdujo la notación exb,c
• Resolvió el caso de árboles pequeños (≤ 6 vértices)
• Resolvió el caso de estrellas dobles y ciertos grafos araña
• Planteó los problemas resueltos en este artículo

Trabajo Independiente

He-Salia-Zhu HSZ25: Los autores mencionan trabajo independiente similar presentado el mismo día

Conclusiones y Discusión

Conclusiones Principales

1. Respuesta Completa a la Pregunta 1.3: Se proporcionan valores exactos de exb,c(n,n,Pₖ) para todos los caminos Pₖ, superando los valores asintóticos requeridos por la pregunta
2. Respuesta Parcial a la Pregunta 1.4: Para la familia de grafos escoba, se proporcionan valores exactos o cotas superiores dentro de rangos de parámetros específicos
3. Contribución Metodológica: Se desarrolló un nuevo marco técnico para abordar problemas extremales en grafos bipartitos conexos

Limitaciones

1. Restricciones en Grafos Escoba:
   • El Teorema 1.6 requiere d > 2k y n ≥ d²/2
   • El Teorema 1.7 solo proporciona cotas superiores, no valores exactos
   • Los casos intermedios (d ≈ k) no están completamente resueltos
2. Caso General de Árboles: Solo se tratan caminos y grafos escoba, dejando abiertas familias más generales de árboles
3. Limitaciones Técnicas: Ciertos pasos de la prueba dependen de propiedades estructurales específicas, que pueden ser difíciles de generalizar a subgrafos prohibidos más complejos

Direcciones Futuras

1. Perfeccionamiento de Resultados para Grafos Escoba: Determinar valores exactos para todos los rangos de parámetros
2. Extensión a Otras Familias de Árboles:
   • Caracterización completa de grafos araña
   • Otras estructuras de árboles especiales
3. Investigación Profunda de Casos Desbalanceados: Aunque este artículo trata el caso a ≠ b, pueden existir resultados más refinados
4. Complejidad Computacional: Investigar problemas algorítmicos para determinar si un grafo dado alcanza la cota de Turán

Evaluación Profunda

Fortalezas

1. Resolución Completa de Problema Abierto:
   • No solo responde la Pregunta 1.3, sino que proporciona una fórmula exacta más fuerte que lo requerido
   • Extensión a grafos bipartitos desbalanceados, aumentando la generalidad de los resultados
2. Técnicas de Prueba Elegantes:
   • La construcción de cota inferior es concisa y clara
   • La estructura inductiva de la prueba de cota superior es transparente
   • Los lemas clave (3.2, 3.3, 3.4) están enunciados y probados de manera refinada
3. Completitud de Resultados:
   • Para caminos, se proporciona una fórmula exacta para todos los parámetros
   • La forma de la fórmula es simple: (k-2)(b-1)+a
   • Se unifican los tratamientos de caminos de longitud impar y par
4. Calidad de Redacción:
   • La estructura del artículo es clara y la lógica rigurosa
   • Los pasos clave están respaldados por proposiciones detalladas
   • Las figuras (como la Figura 1) ayudan a comprender las construcciones
5. Innovación Técnica:
   • El Lema 3.2 sobre la existencia de vértices de pequeño grado que no son puntos de corte es una idea clave
   • La caracterización de pares de vértices eliminables en grafos balanceados (Lema 3.3) tiene valor independiente
   • El uso de árboles DFS se extiende a lo largo de la prueba, demostrando la aplicación efectiva de herramientas clásicas

Deficiencias

1. Resultados Incompletos para Grafos Escoba:
   • Existe una brecha de parámetros entre los Teoremas 1.6 y 1.7
   • El Teorema 1.7 solo proporciona cota superior 2nk+1, con distancia desconocida del valor exacto posible
   • La condición n ≥ d²/2 parece técnicamente fuerte, posiblemente no óptima
2. Complejidad de Prueba del Caso Base:
   • La prueba del Lema 3.4 (caso a=b=k) ocupa un espacio considerable
   • Requiere múltiples subproposiciones (Claims 3.11-3.13)
   • Posiblemente existe un argumento más directo
3. Generalidad Limitada:
   • El método depende altamente de estructuras especiales de caminos y grafos escoba
   • Para árboles generales, no está claro cómo aplicar estas técnicas
   • No se discute un posible marco unificador
4. Relación con Trabajo Independiente:
   • Se menciona el trabajo independiente HSZ25 pero sin comparación detallada
   • No está claro si los enfoques técnicos de ambos artículos son similares

Impacto

1. Contribución Teórica:
   • Resolución completa de un problema claramente planteado
   • Proporciona nuevas herramientas técnicas para problemas de Turán bipartito conexo
   • La exactitud de los resultados los convierte en referencia de este campo
2. Valor Metodológico:
   • El marco inductivo puede ser aplicable a otros problemas de subgrafos prohibidos
   • Los lemas clave pueden ser útiles en otros contextos
3. Investigación Posterior:
   • Naturalmente motiva la pregunta sobre caracterización completa de grafos escoba
   • Inspira investigación de valores exb,c para otras familias de árboles
   • Puede motivar investigación del caso no conexo
4. Verificabilidad:
   • Como resultado teórico puro, puede verificarse mediante inspección de la prueba
   • Las construcciones son explícitas y fáciles de entender
   • La fórmula es simple, facilitando su aplicación y citación

Escenarios de Aplicación

1. Investigación Teórica:
   • Resultado de referencia para investigadores en teoría extremal de grafos
   • Fuente técnica para problemas de tipo Turán
   • Estudio de caso de problemas extremales bajo restricción de conexidad
2. Problemas Relacionados:
   • Posible inspiración para investigación de la conjetura de Erdős-Sós
   • Proporciona comparación para números de Turán de otros árboles
   • Investigación de propiedades estructurales de grafos bipartitos conexos
3. Valor Pedagógico:
   • Demuestra aplicación de inducción en combinatoria extremal
   • Ejemplo de análisis de caminos y árboles DFS
   • Caso completo de coincidencia de cotas superior e inferior

Referencias (Literatura Clave)

1. CPT25 Caro, Patkós, Tuza: Número de Turán bipartito de árboles - Plantea los problemas resueltos en este artículo
2. Tur45 Turán: Sobre un problema extremal en teoría de grafos - Fundamenta la base de problemas de Turán
3. ES46 Erdős, Stone: Sobre la estructura de grafos lineales - Teorema de Erdős-Stone
4. GRS84 Gyárfás, Rousseau, Schelp: Un problema extremal para caminos en grafos bipartitos - Números de Turán exactos para caminos en grafos bipartitos (sin requisito de conexidad)
5. HSZ25 He, Salia, Zhu: El problema de Turán bipartito conexo para ciclos largos y caminos - Trabajo relacionado independiente

Evaluación General

Este es un artículo de alta calidad en matemática combinatoria que resuelve completamente un problema abierto claramente planteado, proporcionando resultados más fuertes que los requeridos. Las técnicas de prueba son elegantes e innovadoras, y los resultados poseen completitud y exactitud. Aunque aún hay trabajo por hacer en la generalización a casos de árboles más generales, el artículo proporciona una respuesta definitiva para el caso de caminos. Este trabajo realiza una contribución sustancial a la investigación del problema de Turán bipartito conexo y se espera que se convierta en una referencia importante en este campo.