Ramsey problems for graphs in Euclidean spaces and Cartesian powers
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_ | 1866908719712829440 |
|---|---|
| author | Axenovich, Maria Liu, Dingyuan Sagdeev, Arsenii |
| author_facet | Axenovich, Maria Liu, Dingyuan Sagdeev, Arsenii |
| contents | Given a graph $H$, let $χ_H(\mathbb{R}^n)$ be the smallest positive integer $r$ such that there exists an $r$-coloring of $\mathbb{R}^n$ with no monochromatic unit-copy of $H$, that is a set of $|V(H)|$ vertices of the same color such that any two vertices corresponding to an edge of $H$ are at distance one.
This Ramsey-type function extends the famous Hadwiger--Nelson problem on the chromatic number $χ(\mathbb{R}^n)=χ_{K_2}(\mathbb{R}^n)$ of the space from a complete graph $K_2$ on two vertices to an arbitrary graph $H$. It also extends the classical Euclidean Ramsey problem for congruent monochromatic subsets to the family of those defined by a specific subset of unit distances.
Among others, we show that $χ_H(\mathbb{R}^n)=χ(\mathbb{R}^n)$ for any even cycle $H$ of length $8$ or at least $12$ as well as for any forest and that $χ_H(\mathbb{R}^n)=\lceilχ(\mathbb{R}^n)/2\rceil$ for any sufficiently long odd cycle. Our main tools and results, which are of independent interest, establish that Cartesian powers enjoy Ramsey-type properties for graphs with favorable Turán-type characteristics, such as zero hypercube Turán density.
In addition, we prove induced variants of these results, find bounds on $χ_H(\mathbb{R}^n)$ for growing dimensions $n$, and prove a canonical-type result. We conclude with many open problems. One of these is to determine $χ_{C_4}(\mathbb{R}^2)$, for a cycle $C_4$ on four vertices. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_15516 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Ramsey problems for graphs in Euclidean spaces and Cartesian powers Axenovich, Maria Liu, Dingyuan Sagdeev, Arsenii Combinatorics 05D10, 05C15, 05C35 Given a graph $H$, let $χ_H(\mathbb{R}^n)$ be the smallest positive integer $r$ such that there exists an $r$-coloring of $\mathbb{R}^n$ with no monochromatic unit-copy of $H$, that is a set of $|V(H)|$ vertices of the same color such that any two vertices corresponding to an edge of $H$ are at distance one. This Ramsey-type function extends the famous Hadwiger--Nelson problem on the chromatic number $χ(\mathbb{R}^n)=χ_{K_2}(\mathbb{R}^n)$ of the space from a complete graph $K_2$ on two vertices to an arbitrary graph $H$. It also extends the classical Euclidean Ramsey problem for congruent monochromatic subsets to the family of those defined by a specific subset of unit distances. Among others, we show that $χ_H(\mathbb{R}^n)=χ(\mathbb{R}^n)$ for any even cycle $H$ of length $8$ or at least $12$ as well as for any forest and that $χ_H(\mathbb{R}^n)=\lceilχ(\mathbb{R}^n)/2\rceil$ for any sufficiently long odd cycle. Our main tools and results, which are of independent interest, establish that Cartesian powers enjoy Ramsey-type properties for graphs with favorable Turán-type characteristics, such as zero hypercube Turán density. In addition, we prove induced variants of these results, find bounds on $χ_H(\mathbb{R}^n)$ for growing dimensions $n$, and prove a canonical-type result. We conclude with many open problems. One of these is to determine $χ_{C_4}(\mathbb{R}^2)$, for a cycle $C_4$ on four vertices. |
| title | Ramsey problems for graphs in Euclidean spaces and Cartesian powers |
| topic | Combinatorics 05D10, 05C15, 05C35 |
| url | https://arxiv.org/abs/2512.15516 |