Ramsey Theory on the Integer Grid: The "L" Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917916413263872 |
|---|---|
| author | Mammel, Isaac Smith, William Yerger, Carl |
| author_facet | Mammel, Isaac Smith, William Yerger, Carl |
| contents | In an $[n] \times [n]$ integer grid, a monochromatic $L$ is any set of points $\{(i, j), (i, j+t), (i+t, j+t)\}$ for some positive integer $t$, where $1 \leq i, j, i+t, j+t \leq n$. In this paper, we investigate the upper bound for the smallest integer $n$ such that a $3$-colored $n \times n$ grid is guaranteed to contain a monochromatic $L$. We use various methods, such as counting intervals on the main diagonal and using Golomb rulers, to improve the upper bound. This bound originally sat at 2593, and we improve it first to 1803, then to 1573, then to 772, and finally to 493. In the latter part of this paper, we discuss the lower bound and our attempts to improve it using SAT solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05162 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Ramsey Theory on the Integer Grid: The "L" Problem Mammel, Isaac Smith, William Yerger, Carl Combinatorics In an $[n] \times [n]$ integer grid, a monochromatic $L$ is any set of points $\{(i, j), (i, j+t), (i+t, j+t)\}$ for some positive integer $t$, where $1 \leq i, j, i+t, j+t \leq n$. In this paper, we investigate the upper bound for the smallest integer $n$ such that a $3$-colored $n \times n$ grid is guaranteed to contain a monochromatic $L$. We use various methods, such as counting intervals on the main diagonal and using Golomb rulers, to improve the upper bound. This bound originally sat at 2593, and we improve it first to 1803, then to 1573, then to 772, and finally to 493. In the latter part of this paper, we discuss the lower bound and our attempts to improve it using SAT solvers. |
| title | Ramsey Theory on the Integer Grid: The "L" Problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.05162 |