Vol. 2 (2021): Proceedings of the 3rd BYMAT Conference
Artículos

Inverse Turán numbers

Ervin Győri
Alfréd Rényi Institute of Mathematics
Nika Salia
Alfréd Rényi Institute of Mathematics
Casey Tompkins
Discrete Mathematics Group and Institute for Basic Science (IBS)
Oscar Zamora
Universidad de Costa Rica, San José
Cover for TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMat Conference

Publicado 28/08/2021

Palabras clave

  • Turán number,
  • extremal combinatorics,
  • paths,
  • cycles

Cómo citar

Győri, Ervin; Salia, Nika; Tompkins, Casey, y Zamora, Oscar. «Inverse Turán numbers». En: TEMat monográficos, 2 (2021): Proceedings of the 3rd BYMAT Conference, págs. 79-82. ISSN: 2660-6003.URL: https://temat.es/monograficos/article/view/vol2-p79.

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$.