The Ramsey number of the 4-cycle versus a book graph
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913890120499200 |
|---|---|
| author | Dou, Chunyang Li, Tianyu Lin, Qizhong Peng, Xing |
| author_facet | Dou, Chunyang Li, Tianyu Lin, Qizhong Peng, Xing |
| contents | Given positive integers $n$ and $k$, the book graph $B_n^{(k)}$ consists of $n$ copies of $K_{k+1}$ sharing a common $K_k$. The book graph is a common generalization of a star and a clique, which can be seen by taking $k=1$ and $n=1$ respectively. In addition, the Ramsey number of a book graph is closely related to the diagonal Ramsey number. Thus the study of extremal problems related to the book graph is of substantial significance. In this paper, we aim to investigate the Ramsey number $r(C_4,B_n^{(k)})$ which is the smallest integer $N$ such that for any graph $G$ on $N$ vertices, either $G$ contains $C_4$ as a subgraph or the complement $\overline{G}$ contains $B_n^{(k)}$ as a subgraph. For $k=1$, a pioneer work by Parsons ({\it Trans.~Amer.~Math.~Soc.,} 209 (1975), 33--44) gives an upper bound for $r(C_4,B_n^{(1)})$, which is tight for infinitely many $n$. For $k=2$, in a recent paper ({\em J. Graph Theory,} 103 (2023), 309--322), the second, the third, and the fourth authors obtained the exact value of $r(C_4,B_{n}^{(2)})$ for infinitely many $n$. The goal of this paper is to prove a similar result for each integer $k \geq 3$. To be precise, given an integer $k \geq 3$ and a constant $0<\varepsilon<1$, let $n=q^2-kq+t+\binom{k}{2}-k$ and $Q(k,\varepsilon)=(320k^4)^{k+1}/\varepsilon^{2k}$, where $1 \leq t \leq (1-\varepsilon)q$. We first establish an upper bound for $r(C_4,B_n^{(k)})$ provided $q \geq Q(k,\varepsilon)$. Then we show the upper bound is tight for $q \geq Q(k,\varepsilon)$ being a prime power and $1 \leq t \leq (1-\varepsilon)q$ under some assumptions. The proof leverages on a simple but novel refinement of a well-known inequality related to a $C_4$-free graph. Therefore, for each $k \geq 3$, we obtain the exact value of $r(C_4,B_n^{(k)})$ for infinitely many $n$. Moreover, we prove general upper and lower bounds of $r(C_4,B_n^{(k)})$ for $k \geq 3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_10477 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Ramsey number of the 4-cycle versus a book graph Dou, Chunyang Li, Tianyu Lin, Qizhong Peng, Xing Combinatorics 05D10 Given positive integers $n$ and $k$, the book graph $B_n^{(k)}$ consists of $n$ copies of $K_{k+1}$ sharing a common $K_k$. The book graph is a common generalization of a star and a clique, which can be seen by taking $k=1$ and $n=1$ respectively. In addition, the Ramsey number of a book graph is closely related to the diagonal Ramsey number. Thus the study of extremal problems related to the book graph is of substantial significance. In this paper, we aim to investigate the Ramsey number $r(C_4,B_n^{(k)})$ which is the smallest integer $N$ such that for any graph $G$ on $N$ vertices, either $G$ contains $C_4$ as a subgraph or the complement $\overline{G}$ contains $B_n^{(k)}$ as a subgraph. For $k=1$, a pioneer work by Parsons ({\it Trans.~Amer.~Math.~Soc.,} 209 (1975), 33--44) gives an upper bound for $r(C_4,B_n^{(1)})$, which is tight for infinitely many $n$. For $k=2$, in a recent paper ({\em J. Graph Theory,} 103 (2023), 309--322), the second, the third, and the fourth authors obtained the exact value of $r(C_4,B_{n}^{(2)})$ for infinitely many $n$. The goal of this paper is to prove a similar result for each integer $k \geq 3$. To be precise, given an integer $k \geq 3$ and a constant $0<\varepsilon<1$, let $n=q^2-kq+t+\binom{k}{2}-k$ and $Q(k,\varepsilon)=(320k^4)^{k+1}/\varepsilon^{2k}$, where $1 \leq t \leq (1-\varepsilon)q$. We first establish an upper bound for $r(C_4,B_n^{(k)})$ provided $q \geq Q(k,\varepsilon)$. Then we show the upper bound is tight for $q \geq Q(k,\varepsilon)$ being a prime power and $1 \leq t \leq (1-\varepsilon)q$ under some assumptions. The proof leverages on a simple but novel refinement of a well-known inequality related to a $C_4$-free graph. Therefore, for each $k \geq 3$, we obtain the exact value of $r(C_4,B_n^{(k)})$ for infinitely many $n$. Moreover, we prove general upper and lower bounds of $r(C_4,B_n^{(k)})$ for $k \geq 3$. |
| title | The Ramsey number of the 4-cycle versus a book graph |
| topic | Combinatorics 05D10 |
| url | https://arxiv.org/abs/2506.10477 |