论文标题
两个涉及三角形的Ramsey-Turán数字
Two Ramsey-Turán numbers involving triangles
论文作者
论文摘要
给定整数$ p，q \ ge2 $，我们说图$ g $是$（k_p，k_q）$ - 如果存在$ g $的红色/蓝色边缘着色，则免费，因此它既不包含红色$ k_p $也不包含蓝色$ k_q $。修复函数$ f（n）$，ramsey-turán编号$ rt（{n，p，q，f（n））} $是$ n $ -vertex $（k_p，k_q）$的最大边数，最多具有独立$ f（n）$的自由图。对于任何$δ> 0 $，令$ρ（p，q，δ）= \ mathop {\ lim} \ limits_ {n \ to \ infty} \ frac {rt（n，p，q，q，Δn）} {n^2} $。我们始终调用$ρ（p，q）：= \ mathop {\ lim} \ limits_ {δ\ to 0}ρ（p，q，q，δ）$ ramsey-turán密度为$ k_p $和$ k_q $。 在1993年，Erdős，Hajnal，Simonovits，Sós和Szemerédi提议确定$ρ（3，Q）$的价值（3，Q）$，$ Q \ ge3 $，他们猜想了$ q \ ge 2 $，$ q \ ge 2 $，$ρ\ weft（{3,2Q -1}} \ right） \ frac {1} {r（3，q）-1}）$。最近，Kim，Kim和Liu（2019）指出，对于$ q \ ge 2 $，$ρ（{3,2Q}）= \ frac {1} {1} {2} {2}（1 - \ frac {1} {1} {r（{3，q}}）}）$。 Erdős等。 （1993年）确定$ρ（3，Q）$，$ Q = 3,4,5 $和$ρ（4,4）$。过去三十年来，Ramsey-Turán密度$ρ（P，Q）$没有进展。在本文中，我们获得$ρ（3,6）= \ frac {5} {12} $和$ρ（3,7）= \ frac {7} {16} $。此外，我们表明，相应的渐近极端结构是弱稳定的，它回答了Erdős等人的问题。 （1993）在这两个案例中。
Given integers $p, q\ge2$, we say that 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$. 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 $(K_p,K_q)$-free graph with independence number at most $f( n )$. For any $δ>0$, let $ρ(p, q,δ) = \mathop {\lim }\limits_{n \to \infty } \frac{RT(n,p, q,δn)}{n^2}$. We always call $ρ(p, q):= \mathop {\lim }\limits_{δ\to 0}ρ(p, q,δ)$ the Ramsey-Turán density of $K_p$ and $K_q$. In 1993, Erdős, Hajnal, Simonovits, Sós and Szemerédi proposed to determine the value of $ρ(3,q)$ for $q\ge3$, and they conjectured that for $q \ge 2$, $ρ\left( {3,2q - 1} \right) = \frac{1}{2}(1 - \frac{1}{r(3,q) - 1})$. Recently, Kim, Kim and Liu (2019) conjectured that for $q \ge 2$, $ρ( {3,2q } ) = \frac{1}{2}( 1 - \frac{1}{r( {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)=\frac{5}{12}$ and $ρ(3,7)=\frac{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.
