A step towards the Ramsey-Turán conjecture for $K_3$ and $K_6$
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913063417937920 |
|---|---|
| author | Hu, Xinyu Lin, Qizhong |
| author_facet | Hu, Xinyu Lin, Qizhong |
| contents | Ramsey-Turán type problems were initiated by Erdős and Sós in 1969. Given integers $p, q\ge2$, 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 }\limits_{n \to \infty } \frac{RT(n,p, q,δn)}{n^2}$. Kim, Kim and Liu (2019) showed that $ρ(3,6,δ)\ge \frac{5}{12}+\fracδ{2}+2δ^2$ via a skillful construction and conjectured the equality holds for sufficiently small $δ>0$. Using Szemerédi's regularity lemma and a stability argument, we make the first step towards the conjecture by showing that $ρ(3,6,δ)$ is at most $\frac{5}{12} + \frac{δ}{2}+ 2.1025δ^2$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_04042 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A step towards the Ramsey-Turán conjecture for $K_3$ and $K_6$ Hu, Xinyu Lin, Qizhong Combinatorics Ramsey-Turán type problems were initiated by Erdős and Sós in 1969. Given integers $p, q\ge2$, 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 }\limits_{n \to \infty } \frac{RT(n,p, q,δn)}{n^2}$. Kim, Kim and Liu (2019) showed that $ρ(3,6,δ)\ge \frac{5}{12}+\fracδ{2}+2δ^2$ via a skillful construction and conjectured the equality holds for sufficiently small $δ>0$. Using Szemerédi's regularity lemma and a stability argument, we make the first step towards the conjecture by showing that $ρ(3,6,δ)$ is at most $\frac{5}{12} + \frac{δ}{2}+ 2.1025δ^2$. |
| title | A step towards the Ramsey-Turán conjecture for $K_3$ and $K_6$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2409.04042 |