2022/12/14 by Xinyu Hu, Hu, Xinyu, Qizhong Lin +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2212.07234
openalex publication_date 2022/12/14 · openalex created_date 2023/02/14 · openalex updated_date 2026/07/28
Given integers p, q≥2, we say that a graph G is (Kp,Kq)-free if there exists a red/blue edge coloring of G such that it contains neither a red Kp nor a blue Kq. Fix a function f( n ), the Ramsey-Turán number RT( n,p,q,f( n )) is the maximum number of edges in an n-vertex (Kp,Kq)-free graph with independence number at most f( n ). For any δ>0, let ρ(p, q,δ) = \mathop lim n → ∞ (RT(n,p, q,δn))/(n2). We always call ρ(p, q):= \mathop lim δ→ 0ρ(p, q,δ) the Ramsey-Turán density of Kp and Kq. In 1993, Erdős, Hajnal, Simonovits, Sós and Szemerédi proposed to determine the value of ρ(3,q) for q≥3, and they conjectured that for q ≥ 2, ρ( 3,2q - 1 ) = (1)/(2)(1 - (1)/(r(3,q) - 1)). Recently, Kim, Kim and Liu (2019) conjectured that for q ≥ 2, ρ( 3,2q ) = (1)/(2)( 1 - \frac1r( 3,q )). Erdős et al. (1993) determined ρ(3,q) for q=3,4,5 and ρ(4,4). There is no progress on the Ramsey-Turán density ρ(p, q) in the past thirty years. In this paper, we obtain ρ(3,6)=(5)/(12) and ρ(3,7)=(7)/(16). Moreover, we show that the corresponding asymptotically extremal structures are weakly stable, which answers a problem of Erdős et al. (1993) for the two cases.