Multicolor bipartite Ramsey number of double stars
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917624538988544 |
|---|---|
| author | DeCamillis, Gregory Song, Zi-Xia |
| author_facet | DeCamillis, Gregory Song, Zi-Xia |
| contents | For positive integers $n, m$, the double star $S(n,m)$ is the graph consisting of the disjoint union of two stars $K_{1,n}$ and $K_{1,m}$ together with an edge joining their centers. Finding monochromatic copies of double stars in edge-colored complete bipartite graphs has attracted much attention. The $k$-color bipartite Ramsey number of $ S(n,m)$, denoted by $r_{bip}(S(n,m);k)$, is the smallest integer $N$ such that, in any $k$-coloring of the edges of the complete bipartite graph $K_{N,N}$, there is a monochromatic copy of $S(n,m)$. The study of bipartite Ramsey numbers was initiated in the early 1970s by Faudree and Schelp and, independently, by Gyárfás and Lehel. The exact value of $r_{bip}(S(n,m);k)$ is only known when $n=m=1$. Applying the Turán argument in the bipartite setting, here we prove that if $k=2$ and $n\ge m$, or $k\ge3$ and $n\ge 2m$, then \[ r_{bip}(S(n,m);k)=kn+1.\] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_03670 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Multicolor bipartite Ramsey number of double stars DeCamillis, Gregory Song, Zi-Xia Combinatorics 05C55, 05C35 For positive integers $n, m$, the double star $S(n,m)$ is the graph consisting of the disjoint union of two stars $K_{1,n}$ and $K_{1,m}$ together with an edge joining their centers. Finding monochromatic copies of double stars in edge-colored complete bipartite graphs has attracted much attention. The $k$-color bipartite Ramsey number of $ S(n,m)$, denoted by $r_{bip}(S(n,m);k)$, is the smallest integer $N$ such that, in any $k$-coloring of the edges of the complete bipartite graph $K_{N,N}$, there is a monochromatic copy of $S(n,m)$. The study of bipartite Ramsey numbers was initiated in the early 1970s by Faudree and Schelp and, independently, by Gyárfás and Lehel. The exact value of $r_{bip}(S(n,m);k)$ is only known when $n=m=1$. Applying the Turán argument in the bipartite setting, here we prove that if $k=2$ and $n\ge m$, or $k\ge3$ and $n\ge 2m$, then \[ r_{bip}(S(n,m);k)=kn+1.\] |
| title | Multicolor bipartite Ramsey number of double stars |
| topic | Combinatorics 05C55, 05C35 |
| url | https://arxiv.org/abs/2312.03670 |