On the multicolor Ramsey numbers of balanced double stars
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_ | 1866916154764689408 |
|---|---|
| author | Bal, Deepak DeBiasio, Louis Oren-Dahan, Ella |
| author_facet | Bal, Deepak DeBiasio, Louis Oren-Dahan, Ella |
| contents | The balanced double star on $2n+2$ vertices, denoted $S_{n,n}$, is the tree obtained by joining the centers of two disjoint stars each having $n$ leaves. Let $R_r(G)$ be the smallest integer $N$ such that in every $r$-coloring of the edges of $K_N$ there is a monochromatic copy of $G$, and let $R_r^{\mathrm{bip}}(G)$ be the smallest integer $N$ such that in every $r$-coloring of the edges of $K_{N,N}$ there is a monochromatic copy of $G$. It is known that $R_2(S_{n,n})=3n+2$ and $R_2^{\mathrm{bip}}(S_{n,n})=2n+1$ \cite{HJ}, but very little is known about $R_r(S_{n,n})$ and $R^{\mathrm{bip}}_r(S_{n,n})$ when $r\geq 3$ (other than the bounds which follow from considerations on the number of edges in the majority color class).
In this paper we prove the following for all $n\geq 1$ (where the lower bounds are adapted from existing examples): \[(r-1)2n+1\leq R_r(S_{n,n})\leq (r-\frac{1}{2})(2n+2)-1,\]and
\[(2r-4)n+1\leq R^{\mathrm{bip}}_r(S_{n,n})\leq (2r-3+\frac{2}{r}+O(\frac{1}{r^2}))n.\] These bounds are similar to the best known bounds on $R_r(P_{2n+2})$ and $R_r^{\mathrm{bip}}(P_{2n+2})$, where $P_{2n+2}$ is a path on $2n+2$ vertices (which is also a balanced tree). We also give an example which improves the lower bound on $R^{\mathrm{bip}}_r(S_{n,n})$ when $r=3$ and $r=5$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_05677 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On the multicolor Ramsey numbers of balanced double stars Bal, Deepak DeBiasio, Louis Oren-Dahan, Ella Combinatorics The balanced double star on $2n+2$ vertices, denoted $S_{n,n}$, is the tree obtained by joining the centers of two disjoint stars each having $n$ leaves. Let $R_r(G)$ be the smallest integer $N$ such that in every $r$-coloring of the edges of $K_N$ there is a monochromatic copy of $G$, and let $R_r^{\mathrm{bip}}(G)$ be the smallest integer $N$ such that in every $r$-coloring of the edges of $K_{N,N}$ there is a monochromatic copy of $G$. It is known that $R_2(S_{n,n})=3n+2$ and $R_2^{\mathrm{bip}}(S_{n,n})=2n+1$ \cite{HJ}, but very little is known about $R_r(S_{n,n})$ and $R^{\mathrm{bip}}_r(S_{n,n})$ when $r\geq 3$ (other than the bounds which follow from considerations on the number of edges in the majority color class). In this paper we prove the following for all $n\geq 1$ (where the lower bounds are adapted from existing examples): \[(r-1)2n+1\leq R_r(S_{n,n})\leq (r-\frac{1}{2})(2n+2)-1,\]and \[(2r-4)n+1\leq R^{\mathrm{bip}}_r(S_{n,n})\leq (2r-3+\frac{2}{r}+O(\frac{1}{r^2}))n.\] These bounds are similar to the best known bounds on $R_r(P_{2n+2})$ and $R_r^{\mathrm{bip}}(P_{2n+2})$, where $P_{2n+2}$ is a path on $2n+2$ vertices (which is also a balanced tree). We also give an example which improves the lower bound on $R^{\mathrm{bip}}_r(S_{n,n})$ when $r=3$ and $r=5$. |
| title | On the multicolor Ramsey numbers of balanced double stars |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2403.05677 |