Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2306.05054 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909082520125440 |
|---|---|
| author | Fan, Chunchao Lin, Qizhong Yan, Yuanhui |
| author_facet | Fan, Chunchao Lin, Qizhong Yan, Yuanhui |
| contents | For graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest positive integer $N$ such that any red/blue edge coloring of the complete graph $K_N$ contains either a red $G$ or a blue $H$. A book $B_n$ is a graph consisting of $n$ triangles all sharing a common edge.
Recently, Conlon, Fox and Wigderson conjectured that for any $0<α<1$, the random lower bound $r(B_{\lceilαn\rceil},B_n)\ge (\sqrtα+1)^2n+o(n)$ is not tight. In other words, there exists some constant $β>(\sqrtα+1)^2$ such that $r(B_{\lceilαn\rceil},B_n)\ge βn$ for all sufficiently large $n$. This conjecture holds for every $α< 1/6$ by a result of Nikiforov and Rousseau from 2005, which says that in this range $r(B_{\lceilαn\rceil},B_n)=2n+3$ for all sufficiently large $n$.
We disprove the conjecture of Conlon, Fox and Wigderson. Indeed, we show that the random lower bound is asymptotically tight for every $1/4\leq α\leq 1$. Moreover, we show that for any $1/6\leq α\le 1/4$ and large $n$, $r(B_{\lceilαn\rceil}, B_n)\le\left(\frac 32+3α\right) n+o(n)$, where the inequality is asymptotically tight when $α=1/6$ or $1/4$. We also give a lower bound of $r(B_{\lceilαn\rceil}, B_n)$ for $1/6\leα< \frac{52-16\sqrt{3}}{121}\approx0.2007$, showing that the random lower bound is not tight, i.e., the conjecture of Conlon, Fox and Wigderson holds in this interval. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_05054 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On a conjecture of Conlon, Fox and Wigderson Fan, Chunchao Lin, Qizhong Yan, Yuanhui Combinatorics 05D10 For graphs $G$ and $H$, the Ramsey number $r(G,H)$ is the smallest positive integer $N$ such that any red/blue edge coloring of the complete graph $K_N$ contains either a red $G$ or a blue $H$. A book $B_n$ is a graph consisting of $n$ triangles all sharing a common edge. Recently, Conlon, Fox and Wigderson conjectured that for any $0<α<1$, the random lower bound $r(B_{\lceilαn\rceil},B_n)\ge (\sqrtα+1)^2n+o(n)$ is not tight. In other words, there exists some constant $β>(\sqrtα+1)^2$ such that $r(B_{\lceilαn\rceil},B_n)\ge βn$ for all sufficiently large $n$. This conjecture holds for every $α< 1/6$ by a result of Nikiforov and Rousseau from 2005, which says that in this range $r(B_{\lceilαn\rceil},B_n)=2n+3$ for all sufficiently large $n$. We disprove the conjecture of Conlon, Fox and Wigderson. Indeed, we show that the random lower bound is asymptotically tight for every $1/4\leq α\leq 1$. Moreover, we show that for any $1/6\leq α\le 1/4$ and large $n$, $r(B_{\lceilαn\rceil}, B_n)\le\left(\frac 32+3α\right) n+o(n)$, where the inequality is asymptotically tight when $α=1/6$ or $1/4$. We also give a lower bound of $r(B_{\lceilαn\rceil}, B_n)$ for $1/6\leα< \frac{52-16\sqrt{3}}{121}\approx0.2007$, showing that the random lower bound is not tight, i.e., the conjecture of Conlon, Fox and Wigderson holds in this interval. |
| title | On a conjecture of Conlon, Fox and Wigderson |
| topic | Combinatorics 05D10 |
| url | https://arxiv.org/abs/2306.05054 |