Geodesic
Generalized Ramsey–Turán density for cliques
Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e78

Voir la notice de l'article provenant de la source Cambridge University Press

We study the generalized Ramsey–Turán function $\mathrm {RT}(n,K_s,K_t,o(n))$, which is the maximum possible number of copies of $K_s$ in an n-vertex $K_t$-free graph with independence number $o(n)$. The case when $s=2$ was settled by Erdős, Sós, Bollobás, Hajnal, and Szemerédi in the 1980s. We combinatorially resolve the general case for all $s\ge 3$, showing that the (asymptotic) extremal graphs for this problem have simple (bounded) structures. In particular, it implies that the extremal structures follow a periodic pattern when t is much larger than s. Our results disprove a conjecture of Balogh, Liu, and Sharifzadeh and show that a relaxed version does hold. 
Gao, Jun; Jiang, Suyun; Liu, Hong; Sankar, Maya. Generalized Ramsey–Turán density for cliques. Forum of Mathematics, Sigma, Tome 13 (2025) no. 1, p. e78. doi: 10.1017/fms.2025.29
@article{10_1017_fms_2025_29,
     author = {Gao, Jun and Jiang, Suyun and Liu, Hong and Sankar, Maya},
     title = {Generalized {Ramsey{\textendash}Tur\'an} density for cliques},
     journal = {Forum of Mathematics, Sigma},
     pages = {e78},
     year = {2025},
     volume = {13},
     number = {1},
     doi = {10.1017/fms.2025.29},
     url = {http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.29/}
}
TY  - JOUR
AU  - Gao, Jun
AU  - Jiang, Suyun
AU  - Liu, Hong
AU  - Sankar, Maya
TI  - Generalized Ramsey–Turán density for cliques
JO  - Forum of Mathematics, Sigma
PY  - 2025
SP  - e78
VL  - 13
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.29/
DO  - 10.1017/fms.2025.29
ID  - 10_1017_fms_2025_29
ER  - 
%0 Journal Article
%A Gao, Jun
%A Jiang, Suyun
%A Liu, Hong
%A Sankar, Maya
%T Generalized Ramsey–Turán density for cliques
%J Forum of Mathematics, Sigma
%D 2025
%P e78
%V 13
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1017/fms.2025.29/
%R 10.1017/fms.2025.29
%F 10_1017_fms_2025_29

[1] Alon, N. and Shikhelman, C., ‘Many copies in -free graphs’, Journal of Combinatorial Theory, Series B 121 (2016), 146–172. Google Scholar | DOI

[2] Balogh, J., Bradac, D. and Lidický, B., ‘Weighted Turán theorems with applications to Ramsey–Turán type of problems’, Preprint, 2023, . Google Scholar | arXiv

[3] Balogh, J., Chen, C., Mccourt, G. and Murley, C., ‘Ramsey–Turán problems with small independence numbers’, European Journal of Combinatorics 118 (2024), 103872. Google Scholar

[4] Balogh, J., Hu, P. and Simonovits, M., ‘Phase transitions in Ramsey–Turán theory’, Journal of Combinatorial Theory, Series B 114 (2015), 148–169. Google Scholar | DOI

[5] Balogh, J. and Lenz, J., ‘Some exact Ramsey–Turán numbers’, Bulletin of the London Mathematical Society 44 (2012), 1251–1258. Google Scholar | DOI

[6] Balogh, J., Liu, H. and Sharifzadeh, M., ‘On two problems in Ramsey–Turán theory’, SIAM Journal on Discrete Mathematics 31(3) (2017), 1848–1866. Google Scholar | DOI

[7] Balogh, J., Magnan, V. and Palmer, C., ‘Generalized Ramsey–Turán numbers’, Preprint, 2024, . Google Scholar | arXiv

[8] Balogh, J., Molla, T. and Sharifzadeh, M., ‘Triangle factors of graphs without large independent sets and of weighted graphs’, Random Structures & Algorithms 49(4) (2016), 669–693. Google Scholar | DOI

[9] Beke, C. and Janzer, O., ‘On the generalized Turán problem for odd cycles’, SIAM Journal on Discrete Mathematics 38(3) (2024), 2416–2428. Google Scholar | DOI

[10] Bollobás, B. and Erdős, P., ‘On a Ramsey–Turán type problem’, Journal of Combinatorial Theory, Series B 21 (1976), 166–168. Google Scholar | DOI

[11] Chang, F., Han, J., Kim, J., Wang, G. and Yang, D., ‘Embedding clique-factors in graphs with low -independence number’, Journal of Combinatorial Theory, Series B 161 (2023), 301–330. Google Scholar

[12] Duke, R. A., Lefmann, H. and Rödl, V., ‘A fast approximation algorithm for computing the frequencies of subgraphs in a given graph’, SIAM Journal on Computing 24(3) (1995), 598–620. Google Scholar | DOI

[13] Erdős, P., ‘On the number of complete subgraphs contained in certain graphs’, Magyar Tud. Akad. Mat. Kut. Int. Kőzl 7 (1962), 459–464. Google Scholar

[14] Erdős, P. and Simonovits, M., ‘A limit theorem in graph theory’, Studia Scientiarum Mathematicarum Hungarica 1 (1966), 51–57. Google Scholar

[15] Erdős, P. and Stone, A. H., ‘On the structure of linear graphs’, Bulletin of the American Mathematical Society 52 (1946), 1087–1091. Google Scholar | DOI

[16] Erdős, P., Hajnal, A., Sós, V. T. and Szemerédi, E., ‘More results on Ramsey–Turán type problem’, Combinatorica 3 (1983), 69–81. Google Scholar | DOI

[17] Erdős, P. and Sós, V. T., ‘Some remarks on Ramsey’s and Turán’s theorem’, In Colloquia mathematica societatis János Bolyai, 4. Combinatorial theory and its applications, (Balatonfüred, Hungary, 1969), 395–404. Google Scholar

[18] Fox, J., Loh, P. and Zhao, Y., ‘The critical window for the classical Ramsey–Turán problem’, Combinatorica 35(4) (2015), 435–476. Google Scholar | DOI

[19] Gao, J., Wu, Z. and Xue, Y., ‘Counting cliques without generalized theta graphs’, Preprint, 2023, . Google Scholar | arXiv

[20] Gishboliner, L. and Shapira, A., ‘A generalized Turán problem and its applications’, International Mathematics Research Notices 2020(11) (2020), 3417–3452. Google Scholar

[21] Han, J., Hu, P., Wang, G. and Yang, D., ‘Clique-factors in graphs with sublinear -independence number’, Combinatorics, Probability and Computing 32(4) (2023), 665–681. Google Scholar

[22] Han, J., Morris, P., Wang, G. and Yang, D., ‘A Ramsey–Turán theory for tilings in graphs’, Random Structures & Algorithms 64(1) (2024), 94–124. Google Scholar | DOI

[23] Hu, X. and Lin, Q., ‘Two Ramsey–Turán numbers involving triangles’, Preprint, 2023, . Google Scholar | arXiv

[24] Kim, J., Kim, Y. and Liu, H., ‘Two conjectures in Ramsey–Turán theory’, SIAM Journal on Discrete Mathematics 33(1) (2019), 564–586. Google Scholar | DOI

[25] Knierim, C. and Su, P., ‘-factors in graphs with low independence number’, Journal of Combinatorial Theory, Series B 148 (2021), 60–83. Google Scholar | DOI

[26] Liu, H., Reiher, C., Sharifzadeh, M. and Staden, K., ‘Geometric constructions for Ramsey–Turán theory’, Preprint, 2021, . Google Scholar | arXiv

[27] Liu, M. and Li, Y., ‘Two Results on Ramsey–Turán Theory’, The Electronic Journal of Combinatorics 28(4) (2021), #P4.6. Google Scholar | DOI

[28] Łuczak, T., Polcyn, J. and Reiher, C., ‘On the Ramsey–Turán density of triangles’, Combinatorica 42(1) (2022), 115–136. Google Scholar

[29] Lüders, C. M. and Reiher, C., ‘The Ramsey–Turán problem for cliques’, Israel Journal of Mathematics 230 (2019), 613–652. Google Scholar | DOI

[30] Ma, J. and Qiu, Y., ‘Some sharp results on the generalized Turán numbers’, European Journal of Combinatorics 84 (2020), 103026. Google Scholar | DOI

[31] Morrison, N., Nir, J., Norin, S., Rzążewski, P. and Wesolek, A., ‘Every graph is eventually Turán-good’, Journal of Combinatorial Theory, Series B 162 (2023), 231–243. Google Scholar | DOI

[32] Ramsey, F. P., ‘On a problem of formal logic’, Proceedings of the London Mathematical Society 30 (1930), 264–286. Google Scholar | DOI

[33] Simonovits, M. and Sós, V. T., ‘Ramsey–Turán theory’, Discrete Mathematics 229 (2001), 293–340. Google Scholar | DOI

[34] Sós, V. T., ‘On extremal problems in graph theory’, In Combinatorial structures and their applications, Proceedings of the Calgary International Conference, (Calgary, 1969), 407–410. Google Scholar

[35] Szemerédi, E., ‘On graphs containing no complete subgraph with 4 vertices (Hungarian)’, Mat. Lapok 23 (1972), 113–116. Google Scholar

[36] Szemerédi, E., ‘Regular partitions of graphs’, Colloques Internationaux C.N.R.S. 260 - Problèmes Combinatoires et Théorie des Graphes, (Orsay, 1976), 399–401. Google Scholar

[37] Turán, P., ‘On an extremal problem in graph theory’, Mat. Fiz. Lapok (in Hungarian) 48 (1941), 436–452. Google Scholar

Cité par Sources :