Improved Bounds on Diffsequences with Gaps in Powers of 2
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916924993044480 |
|---|---|
| author | Talwar, Kanav Gupta, Utkarsh |
| author_facet | Talwar, Kanav Gupta, Utkarsh |
| contents | Let $D$ be a set of positive integers. A $D$-diffsequence of length $k$ is a sequence of positive integers $a_1 < \cdots < a_k$ such that $a_{i+1}-a_i\in D$ for $i=1,\ldots,k-1$. For $D=\{2^i\mid i\in \mathbb{Z}_{\ge 0}\}$, it is known that there exists a minimum integer $n$, denoted by $Δ(D,k)$, such that every $2$-coloring of $\{1,\ldots n \}$ admits a monochromatic $D$-diffsequence of length $k$. In this work, we prove a new lower bound for $Δ(D,k)$ to $Δ(D,k)\ge \left(\sqrt{\frac{8k-5}{12}}-\frac12\right)2^{\left(\sqrt{\frac{8k-5}{3}}-3\right)}$, asymptotically improving the exponential constant in the bound proved by Clifton. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_21280 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved Bounds on Diffsequences with Gaps in Powers of 2 Talwar, Kanav Gupta, Utkarsh Combinatorics Let $D$ be a set of positive integers. A $D$-diffsequence of length $k$ is a sequence of positive integers $a_1 < \cdots < a_k$ such that $a_{i+1}-a_i\in D$ for $i=1,\ldots,k-1$. For $D=\{2^i\mid i\in \mathbb{Z}_{\ge 0}\}$, it is known that there exists a minimum integer $n$, denoted by $Δ(D,k)$, such that every $2$-coloring of $\{1,\ldots n \}$ admits a monochromatic $D$-diffsequence of length $k$. In this work, we prove a new lower bound for $Δ(D,k)$ to $Δ(D,k)\ge \left(\sqrt{\frac{8k-5}{12}}-\frac12\right)2^{\left(\sqrt{\frac{8k-5}{3}}-3\right)}$, asymptotically improving the exponential constant in the bound proved by Clifton. |
| title | Improved Bounds on Diffsequences with Gaps in Powers of 2 |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.21280 |