Generalized Ramsey-Turán Numbers

2024/05/03 by Balogh, József, Magnan, Van, Palmer, Cory
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2405.01804

Abstract

The Ramsey-Turán 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₂ 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₃,K_p,o(n)). In this paper we will establish the asymptotics for counting copies of K₄, K₅, and for the case p ≥ 5q. We also provide a family of counterexamples to a conjecture of Balogh, Liu and Sharifzadeh.

Related

• Generalized Ramsey--Turán density for cliques
• Ramsey-Turán Problems with small independence numbers
• Critical behaviors of the Ramsey-Turán number of K₃ and K₆
• On the Ramsey-Turán number with small s-independence number
• On two problems in Ramsey-Turán theory