Cliques grandes en gráficos con estructuras semi-inducidas prohibidas

Información Básica

• ID del Artículo: 2511.13073
• Título: Large cliques in graphs with forbidden semi-induced structures
• Autores: Nannan Chen (Shandong University & IBS), Yulai Ma (Nankai University), Fan Yang (Shandong University & IBS)
• Clasificación: math.CO (Combinatoria)
• Fecha de Presentación: 17 de noviembre de 2025
• Enlace del Artículo: https://arxiv.org/abs/2511.13073

Resumen

Este artículo estudia la existencia de cliques grandes en gráficos que prohíben subestructuras semi-inducidas. Holmsen demostró en 2022 que cualquier gráfico que contenga al menos $c\binom{n}{r}$ cliques $r$ pero no contenga el gráfico completo $r$-partito inducido $K_{2,\ldots,2}$ debe contener un clique de orden $Ω(c^{2^{r-1}}n)$. Este artículo, al prohibir subestructuras semi-inducidas relacionadas con $K_{2,\ldots,2}$, demuestra que todo gráfico $G$ de $n$ vértices que contenga al menos $c\binom{n}{r}$ copias de $K_r$ debe contener un clique de orden $Ω(cn)$. Este resultado mejora la dependencia de $c$ en el límite de Holmsen de $c^{2^{r-1}}$ a lineal en $c$, y requiere prohibir solo una cantidad acotada de estructuras. Además, el método se conecta naturalmente con el concepto de dimensión VC.

Contexto de Investigación y Motivación

Antecedentes del Problema

1. Teoría Clásica de Turán: El teorema de Turán y sus generalizaciones (teorema de Erdős-Stone-Simonovits) estudian problemas extremales que prohíben subgráficos no inducidos. Para gráficos $H$ con número cromático $χ(H) ≥ 3$, prohibir $H$ como subgráfico hace que el gráfico extremal sea asintóticamente $(χ(H)-1)$-partito, limitando así el número de clique por una constante.
2. El Caso de Subgráficos Inducidos: Cuando se prohíben subgráficos inducidos, la situación es completamente diferente. Gyárfás, Hubenko y Solymosi (2002) demostraron que si un gráfico $G$ de $n$ vértices tiene al menos $c\binom{n}{2}$ aristas y no contiene $K_{2,2}$ inducido, entonces $ω(G) ≥ \frac{c^2}{10}n$.
3. Límites Ajustados para Gráficos Cordales: Los gráficos cordales (que prohíben ciclos inducidos de longitud al menos 4) alcanzan un límite mejor: $ω(G) ≥ (1-\sqrt{1-c})n$, que es $Ω(cn)$ cuando $c$ es pequeño.
4. Generalización de Holmsen: Holmsen (2020) generalizó el caso $K_{2,2}$ a la versión multipartita, demostrando que gráficos que prohíben $K_r[2]$ (la 2-expansión de $K_r$) inducido contienen un clique de orden $Ω(c^{2^{r-1}}n)$.

Motivación de la Investigación

Aunque el resultado de Holmsen es lineal respecto a $n$, su límite en $c$ se deteriora rápidamente con el crecimiento de $r$. La pregunta central de este artículo es: ¿Podemos, de manera similar a la mejora de Teorema 1.1 a Teorema 1.2, mejorar el límite de Holmsen prohibiendo más (pero una cantidad acotada) de estructuras?

Importancia

• Este problema conecta la teoría extremal de gráficos con el teorema abstracto de Helly
• Tiene importancia fundamental para entender la relación entre condiciones de prohibición de subgráficos inducidos y el número de clique
• Revela el papel de la dimensión VC en estructuras de gráficos

Contribuciones Principales

1. Teorema Principal: Se demuestra que para un gráfico $G$ que es $K_r^{[2]}$-libre inducido y contiene al menos $c\binom{n}{r}$ copias de $K_r$, se tiene $ω(G) ≥ \frac{c}{18r}n$ (Teorema 1.5)
2. Mejora de Límites: Se mejora el límite $Ω(c^{2^{r-1}}n)$ de Holmsen a $Ω(cn)$, logrando dependencia lineal en $c$
3. Estructuras Prohibidas Acotadas: Se requiere prohibir solo a lo sumo $2^{\binom{r}{2}}$ subestructuras inducidas (en comparación con infinitas para gráficos cordales)
4. Método de Dimensión VC: Se establece una conexión natural entre subgráficos semi-inducidos y dimensión VC, generalizando la teoría de subgráficos doblemente inducidos existente
5. Perspectiva Estructural: Se revela que incluso prohibiendo significativamente menos estructuras que los gráficos cordales, se puede garantizar un clique de tamaño lineal

Explicación Detallada del Método

Definición de la Tarea

Entrada: Gráfico $G$ de $n$ vértices que satisface:

• Contiene al menos $c\binom{n}{r}$ copias de $K_r$ ($c > 0$ es una constante)
• Es $K_r^{[2]}$-libre inducido (no contiene ningún gráfico de $K_r^{[2]}$ como subgráfico inducido)

Salida: Demostrar que $G$ contiene un clique de orden al menos $\frac{c}{18r}n$

Definiciones Clave:

• $K_r[2]$: La 2-expansión de $K_r$, reemplazando cada vértice por un conjunto independiente de tamaño 2
• $K_r^{[2]}$: La familia de subgráficos de $K_r[2]$ cuyo conjunto de aristas tiene la forma $(E(K_r[2])\backslash E(K_{U'})) \cup E'$, donde $U' = \{u'_1, \ldots, u'_r\}$ es el conjunto de segundos vértices de cada parte, y $E' \subseteq E(K_{U'})$

Arquitectura Principal

La demostración se divide en tres pasos clave:

1. Límite de Dimensión VC (Afirmación 2.3)

Lema Central: El conjunto de cliques maximales $MC(G)$ de un gráfico $K_r^{[2]}$-libre inducido tiene dimensión VC a lo sumo $r-1$.

Esquema de Demostración:

• Supongamos que existe un conjunto $S = \{u_1, \ldots, u_r\}$ de tamaño $r$ que es dispersado por $MC(G)$
• Para cada $i \in [r]$, existe un clique maximal $K_i$ tal que $K_i \cap S = S \backslash \{u_i\}$
• Por maximalidad, existe $u'_i \in K_i \backslash S$ tal que $u_i u'_i \notin E(G)$
• Entonces $\{u_1, u'_1, \ldots, u_r, u'_r\}$ induce algún gráfico en $K_r^{[2]}$, contradicción

2. Aplicación del Lema de Sauer-Shelah

Para un sistema de conjuntos $\mathcal{F}$ con dimensión VC $k$, cualquier conjunto $S$ de tamaño $m$ satisface: $|\mathcal{F}|_S| \leq \sum_{i=0}^{k} \binom{m}{i}$

Para nuestro caso, $k = r-1$, eligiendo $m = \lfloor\frac{9r}{c}\rfloor$, obtenemos: $|MC(G)|_{S_m}| \leq \sum_{i=0}^{r-1} \binom{m}{i} < \frac{1}{4}c\binom{m}{r}$

3. Argumento Probabilístico

Prueba por Contradicción: Supongamos que $ω(G) < c'n$, donde $c' = \frac{c}{18r}$

Selección Aleatoria: Seleccionamos aleatoriamente $S_r \subseteq S_m$, donde $|S_r| = r$, $|S_m| = m$

Análisis Probabilístico:

• La probabilidad de que $S_r$ induzca un clique es al menos $c$
• Si $S_r$ induce un clique y está contenido en un clique maximal $K$ de tamaño $< c'n$, entonces la probabilidad de que $S_m$ contenga $S_r$ pero $S_m \backslash S_r$ no contenga ningún vértice de $K$ es al menos: $\frac{\binom{n-c'n}{m-r}}{\binom{n-r}{m-r}} \geq \left(\frac{n-c'n-m}{n-m}\right)^m \geq e^{-2c'm} \geq \frac{1}{4}$
• Por lo tanto, la probabilidad de que existe $S_r = S_m \cap K$ es al menos $\frac{1}{4}c$
• El número esperado de $S_r$ que satisfacen la condición es al menos $\frac{1}{4}c\binom{m}{r}$

Contradicción: Esto contradice el límite superior dado por el lema de Sauer-Shelah.

Puntos de Innovación Técnica

1. Introducción de Estructuras Semi-Inducidas: La familia $K_r^{[2]}$ equilibra ingeniosamente la intensidad de la restricción estructural con la cantidad de estructuras, proporcionando suficiente poder restrictivo mientras mantiene un número acotado de prohibiciones
2. Conexión Natural con Dimensión VC: Se vincula directamente la dimensión VC del sistema de cliques maximales con las subestructuras inducidas del gráfico, proporcionando una nueva perspectiva analítica
3. Estimaciones Probabilísticas Refinadas: Bajo el marco de selección aleatoria, se establecen relaciones cuantitativas entre la densidad de cliques y el tamaño de cliques mediante cálculos probabilísticos cuidadosos
4. Optimización de Parámetros: La elección de $m = \lfloor\frac{9r}{c}\rfloor$ hace que el límite de Sauer-Shelah y el límite inferior probabilístico produzcan exactamente una contradicción

Configuración Experimental

Este es un artículo de matemática pura teórica que no implica verificación experimental. Todos los resultados se obtienen mediante demostraciones matemáticas rigurosas.

Verificación Teórica

• Ejemplos Extremales: Para el caso $r=2$, el artículo señala que gráficos $K_2^{[2]}$-libres inducidos (prohibiendo $P_4$ y $K_{2,2}$ inducidos) forman una subclase de gráficos cordales
• Análisis de Ajuste: Aunque no se proporcionan construcciones extremales precisas, se demuestra que el orden de magnitud del límite es razonable

Resultados Experimentales

Resultados Teóricos Principales

Teorema 1.5 (Resultado Principal): Sea $r ≥ 2$, $0 < c < 1$, y sea $G$ un gráfico de $n$ vértices que contiene al menos $c\binom{n}{r}$ copias de $K_r$. Si $G$ es $K_r^{[2]}$-libre inducido, entonces para $n$ suficientemente grande, $ω(G) ≥ \frac{c}{18r}n$

Comparación con Resultados Existentes

Mejoras Clave

1. De Exponencial a Lineal: La dependencia en $c$ mejora de $c^{2^{r-1}}$ a $c/r$
   • Cuando $r=3$: de $c^4$ a $c/3$
   • Cuando $r=5$: de $c^{16}$ a $c/5$
2. Número de Estructuras Acotado: Se requiere prohibir solo $2^{\binom{r}{2}}$ estructuras
   • $r=2$: 2 estructuras
   • $r=3$: 8 estructuras
   • $r=4$: 64 estructuras
3. Optimalidad: Para $r=2$, el resultado de este artículo es consistente en orden de magnitud con el límite de gráficos cordales (ambos $Ω(cn)$), pero prohibiendo menos estructuras

Trabajo Relacionado

Teoría Extremal de Gráficos Clásica

1. Teorema de Turán (1941): Determina el valor exacto de $ex(n, K_k)$ y el gráfico extremal
2. Teorema de Erdős-Stone-Simonovits (1946, 1966): $ex(n,H) = \left(1 - \frac{1}{χ(H)-1}\right)\binom{n}{2} + o(n^2)$
   • Para gráficos no bipartitos $H$, resuelve completamente el comportamiento asintótico
   • Para gráficos bipartitos, solo proporciona $ex(n,H) = o(n^2)$

Teoría Extremal de Subgráficos Inducidos

3. Gyárfás-Hubenko-Solymosi (2002):
   • Gráficos $K_{2,2}$-libres inducidos: $ω(G) ≥ \frac{c^2}{10}n$
   • Gráficos $C_4$-libres (gráficos cordales): $ω(G) ≥ (1-\sqrt{1-c})n$
4. Abbott-Katchalski (1979): Demostración independiente del límite ajustado para gráficos cordales
5. Loh et al. (2018): Generalización a gráficos $K_{2,t}$-libres inducidos
6. Holmsen (2020):
   • Generalización a hipergráficos y versiones multipartitas
   • Demuestra que Helly colorido abstracto implica Helly fraccional abstracto
   • Este artículo mejora directamente el resultado de teoría de gráficos de Holmsen

Aplicaciones de Dimensión VC en Teoría de Gráficos

7. Nguyen-Scott-Seymour (2025): Establece la conexión entre densidad de subgráficos doblemente inducidos y dimensión VC
8. Sauer (1972), Shelah (1972): Demuestran independientemente el límite fundamental de dimensión VC (Lema de Sauer-Shelah)

Posicionamiento de Este Artículo

Este artículo, basándose en el trabajo de Holmsen, logra mejoras cuantitativas mediante la introducción de subestructuras semi-inducidas y el método de dimensión VC. La conexión con la teoría de gráficos cordales proporciona una explicación natural para el caso $r=2$.

Conclusiones y Discusión

Conclusiones Principales

1. Mejora Cuantitativa: Al prohibir la familia $K_r^{[2]}$ (a lo sumo $2^{\binom{r}{2}}$ estructuras), se mejora el límite inferior del clique de $Ω(c^{2^{r-1}}n)$ a $Ω(cn)$
2. Contribución Metodológica: Se establece una conexión natural entre subgráficos semi-inducidos y dimensión VC, generalizando el marco teórico existente
3. Perspectiva Estructural: Se revela que condiciones de prohibición de estructuras finitas son suficientes para garantizar un clique de tamaño lineal, sin necesidad de prohibir infinitas estructuras como en gráficos cordales

Limitaciones

1. Factor Constante: El factor constante $\frac{1}{18r}$ en el límite puede no ser óptimo, y el artículo no discute su ajuste
2. Cantidad de Estructuras Prohibidas: Aunque es acotada, $2^{\binom{r}{2}}$ crece exponencialmente con $r$, siendo aún considerable para $r$ grande
3. Ausencia de Construcciones Extremales: El artículo no proporciona construcciones de gráficos extremales que alcancen el límite inferior
4. Propiedades Asintóticas: Los resultados requieren $n$ suficientemente grande, sin especificar el umbral exacto

Direcciones Futuras

El artículo plantea explícitamente problemas abiertos en la sección de conclusiones:

Problema Central: ¿Cuándo ocurre la transición de dependencia $c^{2^{r-1}}$ a dependencia lineal en $c$? Más precisamente, ¿cuál es el número mínimo de estructuras prohibidas necesarias para forzar un límite lineal en $c$?

Posibles direcciones de investigación:

1. Determinar la familia de estructuras prohibidas mínima que alcanza el límite lineal
2. Mejorar el factor constante $\frac{1}{18r}$
3. Construir ejemplos extremales o demostrar el ajuste del límite
4. Generalizar a hipergráficos
5. Explorar otras condiciones de prohibición de estructuras semi-inducidas

Evaluación Profunda

Fortalezas

1. Mejora Cuantitativa Importante:
   • La mejora de dependencia exponencial a lineal es un progreso sustancial
   • Tiene importancia significativa para aplicaciones (como teoremas abstractos de Helly)
2. Técnicas de Demostración Elegantes:
   • El método de dimensión VC proporciona un marco de análisis unificado
   • El argumento probabilístico es conciso y poderoso
   • La demostración es completamente autocontenida, dependiendo solo de herramientas básicas
3. Innovación Conceptual:
   • La definición de la familia $K_r^{[2]}$ equilibra ingeniosamente intensidad de restricción y cantidad
   • La introducción de estructuras semi-inducidas es una generalización natural
4. Claridad de Presentación:
   • Motivación suficientemente explicada
   • Detalles técnicos completos
   • Relaciones con trabajo existente claramente establecidas
5. Profundidad Teórica:
   • Revela estructuras profundas en teoría de subgráficos inducidos
   • Conecta múltiples ramas matemáticas (teoría extremal de gráficos, teoría de dimensión VC, geometría combinatoria)

Deficiencias

1. Optimización de Constantes:
   • El factor constante $\frac{1}{18r}$ puede no ser suficientemente refinado
   • No se discute el ajuste del límite o se proporcionan construcciones de límites superiores coincidentes
2. Dependencia de Cantidad de Estructuras:
   • $2^{\binom{r}{2}}$ aún crece rápidamente con $r$
   • No se explora si se pueden lograr resultados similares con menos estructuras prohibidas
3. Ausencia de Umbrales Concretos:
   • "Para $n$ suficientemente grande" no se cuantifica
   • Puede afectar aplicaciones prácticas
4. Discusión Insuficiente de Generalización:
   • No se discute si el método es aplicable a otras estructuras prohibidas
   • La conexión con hipergráficos se menciona solo en la introducción
5. Especificidad de Problemas Abiertos:
   • Aunque se plantean problemas importantes, no se proporcionan conjeturas o resultados parciales

Evaluación de Impacto

Impacto Teórico:

• Proporciona nuevas herramientas para teoría extremal de subgráficos inducidos
• El método de dimensión VC puede inspirar más aplicaciones
• Contribución directa a investigación de teoremas abstractos de Helly

Valor Práctico:

• Principalmente de naturaleza teórica
• Posibles aplicaciones en teoría de gráficos algorítmicos y geometría computacional

Reproducibilidad:

• Las demostraciones son completamente verificables
• No implica experimentos computacionales

Valor Potencial de Citación:

• Se espera alta citación en el campo de combinatoria extremal
• Probablemente se convertirá en referencia estándar en este área

Escenarios de Aplicabilidad

1. Investigación Teórica:
   • Problemas de subgráficos inducidos prohibidos en teoría extremal de gráficos
   • Aplicaciones de dimensión VC en estructuras combinatorias
   • Teoremas de Helly abstractos y sus generalizaciones
2. Problemas Relacionados:
   • Investigación de otras estructuras semi-inducidas
   • Relaciones entre número de clique y otros parámetros de gráficos
   • Estructuras de cliques en gráficos aleatorios
3. Aplicaciones Potenciales:
   • Diseño de algoritmos (explotando propiedades estructurales)
   • Teoría de complejidad computacional
   • Problemas de optimización combinatoria

Referencias

El artículo cita las siguientes referencias clave:

1. Abbott & Katchalski (1979): Problemas tipo Turán para gráficos de intervalos
2. Erdős & Simonovits (1966), Erdős & Stone (1946): Teorema ESS
3. Gyárfás, Hubenko & Solymosi (2002): Cliques grandes en gráficos $C_4$-libres
4. Holmsen (2020): Cliques grandes en hipergráficos con subestructuras prohibidas (trabajo que este artículo mejora directamente)
5. Loh et al. (2018): Números de Turán inducidos
6. Nguyen, Scott & Seymour (2025): Densidad de subgráficos inducidos y dimensión VC
7. Sauer (1972), Shelah (1972): Límites fundamentales de dimensión VC
8. Turán (1941): Teorema clásico de Turán

Evaluación General: Este es un artículo de alta calidad en matemática combinatoria que logra progreso sustancial en un problema importante de teoría extremal de gráficos. Mediante la introducción de estructuras semi-inducidas y el método de dimensión VC, los autores mejoran exitosamente el límite exponencial de Holmsen a un límite lineal, manteniendo la cantidad de estructuras prohibidas acotada. Las técnicas de demostración son elegantes y perspicaces, proporcionando nuevas herramientas de investigación para el campo. Las contribuciones principales son de naturaleza teórica, pero sus métodos e ideas pueden tener amplio impacto en áreas relacionadas.