{
  "id": "2409.04042",
  "version": "v1",
  "published": "2024-09-06T06:25:19.000Z",
  "updated": "2024-09-06T06:25:19.000Z",
  "title": "On a conjecture of Kim, Kim and Liu",
  "authors": [
    "Xinyu Hu",
    "Qizhong Lin"
  ],
  "comment": "32 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "In 1969, Erd\\H{o}s and S\\'{o}s initiated the study of the Ramsey-Tur\\'{a}n type problems: Determine the maximum number of edges of an $n$-vertex $K_{p+1}$-free graph without large independent set. 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\\'{a}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 $\\delta>0$, let $\\rho (p, q,\\delta ) = \\mathop {\\lim }\\limits_{n \\to \\infty } \\frac{RT(n,p, q,\\delta n)}{n^2}$. Kim, Kim and Liu (2019) determined the value of $\\rho(3,p,\\delta)$ for $p=3,4,5$ and sufficiently small $\\delta>0$. Moreover, they showed $\\rho(3,6,\\delta)\\ge \\frac{5}{12}+\\frac{\\delta}{2}+2\\delta^2$ from a skilful construction and conjectured the equality holds for sufficiently small $\\delta>0$. In this paper, we obtain $\\rho(3,6,\\delta)\\le\\frac{5}{{12}} + \\frac{\\delta }{2}+ 2.1025\\delta ^2$ for sufficiently small $\\delta>0$, which is pretty close to solving the conjecture. The key step of the proof is to establish a stability lemma of the $n$-vertex graph that is $(K_3,K_6)$-free with independence number $\\delta n$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-09-06T06:25:19.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "conjecture",
      "sufficiently small",
      "independence number",
      "maximum number",
      "free graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}