Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2411.14364 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913583835643904 |
|---|---|
| author | Taranchuk, Vladislav |
| author_facet | Taranchuk, Vladislav |
| contents | In this short note, we provide a new infinite family of $K_{2, t+1}$-free graphs for each prime power $t$. Using these graphs, we show that it is possible to partition the edges of $K_n$ into parts, such that each part is isomorphic to our $K_{2, t+1}$-free graph. This yields an improved lower bound to the multicolor Ramsey number $r_k(K_{2, t+1})$ when $k$ and $t$ are powers of the same prime. For these values of $k$ and $t$, our coloring implies that $$ tk^2 + 1 \leq r_k(K_{2, t+1}) \leq tk^2 + k + 2. $$ where the upper bound is due to Chung and Graham. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_14364 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A new lower bound for the multicolor Ramsey number $r_k(K_{2, t + 1})$ Taranchuk, Vladislav Combinatorics In this short note, we provide a new infinite family of $K_{2, t+1}$-free graphs for each prime power $t$. Using these graphs, we show that it is possible to partition the edges of $K_n$ into parts, such that each part is isomorphic to our $K_{2, t+1}$-free graph. This yields an improved lower bound to the multicolor Ramsey number $r_k(K_{2, t+1})$ when $k$ and $t$ are powers of the same prime. For these values of $k$ and $t$, our coloring implies that $$ tk^2 + 1 \leq r_k(K_{2, t+1}) \leq tk^2 + k + 2. $$ where the upper bound is due to Chung and Graham. |
| title | A new lower bound for the multicolor Ramsey number $r_k(K_{2, t + 1})$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2411.14364 |