Two-colorings of finite grids: variations on a theorem of Tibor Gallai
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_ | 1866909977610813440 |
|---|---|
| author | Dumitru, Bogdan Prunescu, Mihai |
| author_facet | Dumitru, Bogdan Prunescu, Mihai |
| contents | A celebrated but non-effective theorem of Tibor Gallai states that for any finite set $A$ of $\Z^n$ and for any finite number of colors $c$ there is a minimal $m$ such that no coloring of the finite $m^n$-grid can avoid that a homothetic image of $A$ is monochromatic. We find (or confirm) $m$ for equilateral triangles, squares, and various types of rectangles. Also, we extend the problem from homothety to general similarity, or to similarity generated using some special rotations. In particular, we compute Gallai similarity numbers for lattice rectangles similar to $1\times k$ (in all orientations) for $k=2,3,4$. The solutions have been found in the framework of the Satisfiability Problem in Propositional Logic (SAT). While some questions were solved using managed brute force, for the more computationally intensive questions we used modern SAT solvers together with symmetry breaking techniques. Some other minor questions are solved for triangles and squares, and new lower bounds are found for regular hexagons on the triangular lattice and for three-dimensional cubes in $\Z^3$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23303 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-colorings of finite grids: variations on a theorem of Tibor Gallai Dumitru, Bogdan Prunescu, Mihai Combinatorics Discrete Mathematics 05C15, 05B05, 52C05, 68V15 A celebrated but non-effective theorem of Tibor Gallai states that for any finite set $A$ of $\Z^n$ and for any finite number of colors $c$ there is a minimal $m$ such that no coloring of the finite $m^n$-grid can avoid that a homothetic image of $A$ is monochromatic. We find (or confirm) $m$ for equilateral triangles, squares, and various types of rectangles. Also, we extend the problem from homothety to general similarity, or to similarity generated using some special rotations. In particular, we compute Gallai similarity numbers for lattice rectangles similar to $1\times k$ (in all orientations) for $k=2,3,4$. The solutions have been found in the framework of the Satisfiability Problem in Propositional Logic (SAT). While some questions were solved using managed brute force, for the more computationally intensive questions we used modern SAT solvers together with symmetry breaking techniques. Some other minor questions are solved for triangles and squares, and new lower bounds are found for regular hexagons on the triangular lattice and for three-dimensional cubes in $\Z^3$. |
| title | Two-colorings of finite grids: variations on a theorem of Tibor Gallai |
| topic | Combinatorics Discrete Mathematics 05C15, 05B05, 52C05, 68V15 |
| url | https://arxiv.org/abs/2512.23303 |