Publicado 28/08/2021
Palabras clave
- Turán number,
- extremal combinatorics,
- paths,
- cycles
Cómo citar
Esta obra está bajo una licencia internacional Creative Commons Atribución 4.0.
Resumen
Para dos grafos $G$ y $F$, el número de Turán ex$(G,F)$ se define como el número máximo de aristas en un subfrafo $F$-libre de $G$. Foucaud, Krivelevich y Perarnau, e independientemente Briggs y Cox, introdujeron una versión dual de este problema en la que, dado un número $k$, se maximiza el número de aristas en un grafo $G$ tal que ex$(G,F) < k$.
Abordando un problema de Briggs y Cox, determinamos el valor asintótico del número de Turán inverso de los caminos de longitud $4$ y $5$, y proporcionamos una cota inferior mejorada para todos los caminos de longitud par. Además, obtenemos cotas para el número de Turán inverso de los ciclos pares, dando cotas mejoradas para el término dominante en el caso de $C_4$. Por último, planteamos múltiples conjeturas sobre el número de Turán inverso de $C_4$ y $P_{\ell}$, sugiriendo que en el segundo caso el comportamiento asintótico depende fuertemente de la paridad de $\ell$.