Back to Search Start Over

Generalized Ramsey-Tur\'an Numbers

Authors :
Balogh, József
Magnan, Van
Palmer, Cory
Publication Year :
2024

Abstract

The Ramsey-Tur\'an problem for $K_p$ asks for the maximum number of edges in an $n$-vertex $K_p$-free graph with independence number $o(n)$. In a natural generalization of the problem, cliques larger than the edge $K_2$ are counted. Let {\bf RT}$(n,\#K_q,K_p,o(n))$ denote the maximum number of copies of $K_q$ in an $n$-vertex $K_p$-free graph with independence number $o(n)$. Balogh, Liu and Sharifzadeh determined the asymptotics of {\bf RT}$(n,\# K_3,K_p,o(n))$. In this paper we will establish the asymptotics for counting copies of $K_4$, $K_5$, and for the case $p \geq 5q$. We also provide a family of counterexamples to a conjecture of Balogh, Liu and Sharifzadeh.<br />Comment: Fixed an icorrect row in Table 1 and corresponding computation in proof of Theorem 1.5

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2405.01804
Document Type :
Working Paper