Critical behaviors of the Ramsey-Turán number of K₃ and K₆

2024/09/06 by Hu, Xinyu, Lin, Qizhong
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2409.04042

Abstract

In 1969, Erdős and Sós initiated the study of the Ramsey-Turán type problems. Given integers p, q≥2, a graph G is (K_p,K_q)-free if there exists a red/blue edge coloring of G such that it contains neither a red K_p nor a blue K_q. For any δ>0, the Ramsey-Turán number RT( n,p,q,δn) is the maximum number of edges in an n-vertex (K_p,K_q)-free graph with independence number at most δn. Let ρ(p, q,δ) = \mathop lim _{n → ∞} (RT(n,p, q,δn))/(n²). Kim, Kim and Liu (2019) showed ρ(3,6,δ)≥ (5)/(12)+\fracδ2+2δ² from a skilful construction and conjectured the equality holds for sufficiently small δ>0. We make the first step to the conjecture by showing that ρ(3,6,δ)≤(5)/(12) + (δ)/(2)+ 2.1025δ² for sufficiently small δ>0.

Related

• Two Ramsey-Turán numbers involving triangles
• Two conjectures in Ramsey-Turán theory
• Generalized Ramsey-Turán Numbers
• Geometric constructions for Ramsey-Turán theory
• On the Ramsey-Turán number with small s-independence number