Abstract
Let \(n\geqslant 1\) be a number. Let \({\Gamma }_n\) be the graph on \(\mathbb {R}^n\) connecting points of rational Euclidean distance. It is consistent with choiceless set theory \(\textrm{ZF}\,{+}\,\textrm{DC}\) that \({\Gamma }_n\) has countable chromatic number, yet the chromatic number of \(\Gamma _{n+1}\) is uncountable.
Similar content being viewed by others
References
Bochnak, J., Coste, M., Roy, M.-F.: Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 36. Springer, Berlin (1998)
Erdős, P., Hajnal, A.: On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. 17, 61–99 (1966)
Erdős, P., Komjáth, P.: Countable decompositions of \(\mathbb{R} ^2\) and \(\mathbb{R} ^3\). Discrete Comput. Geom. 5(4), 325–331 (1990)
Jech, T.: Set Theory Springer. Monographs in Mathematics, 3rd edn. Springer, Berlin (2003)
Komjáth, P.: A decomposition theorem for \(\mathbb{R} ^n\). Proc. Amer. Math. Soc. 120(3), 921–927 (1994)
Larson, P.B., Zapletal, J.: Geometric Set Theory. Mathematical Surveys and Monographs, vol. 248. American Mathematical Society, Providence (2020)
Marker, D.: Model Theory: An Introduction. Graduate Texts in Mathematics, vol. 217. Springer, New York (2002)
Schmerl, J.H.: Avoidable algebraic subsets of Euclidean space. Trans. Amer. Math. Soc. 352(6), 2479–2489 (2000)
Shelah, S.: Can you take Solovay’s inaccessible away? Israel J. Math. 48(1), 1–47 (1984)
Zapletal, J.: Coloring the distance graphs in three dimensions (2021). arXiv:2103.02757
Zapletal, J.: Krull dimension in set theory. Ann. Pure Appl. Logic 174(9), 103299 (2023)
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
The author was supported in part by the Czech Academy of Sciences (RVO 67985840) and grant EXPRO 20-31529X of GA ČR during the preparation of this manuscript.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Zapletal, J. Coloring the distance graphs. European Journal of Mathematics 9, 66 (2023). https://doi.org/10.1007/s40879-023-00665-6
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s40879-023-00665-6