Coloring the distance graphs. (English) Zbl 07722176
Summary: 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 \(\mathrm{ZF} + \mathrm{DC}\) that \(\Gamma_n\) has countable chromatic number, yet the chromatic number of \(\Gamma_{n+1}\) is uncountable.
MSC:
03E35 | Consistency and independence results |
14P99 | Real algebraic and real-analytic geometry |
05C15 | Coloring of graphs and hypergraphs |
References:
[1] | Bochnak, J.; Coste, M.; Roy, M-F, Real Algebraic Geometry. Ergebnisse der Mathematik und ihrer Grenzgebiete (1998), Berlin: Springer, Berlin · Zbl 0912.14023 · doi:10.1007/978-3-662-03718-8 |
[2] | Erdős, P.; Hajnal, A., On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar., 17, 61-99 (1966) · Zbl 0151.33701 · doi:10.1007/BF02020444 |
[3] | Erdős, P.; Komjáth, P., Countable decompositions of \(\mathbb{R}^2\) and \(\mathbb{R}^3\), Discrete Comput. Geom., 5, 4, 325-331 (1990) · Zbl 0723.52005 · doi:10.1007/BF02187793 |
[4] | Jech, T., Set Theory Springer. Monographs in Mathematics (2003), Berlin: Springer, Berlin · Zbl 1007.03002 |
[5] | Komjáth, P., A decomposition theorem for \(\mathbb{R}^n\), Proc. Amer. Math. Soc., 120, 3, 921-927 (1994) · Zbl 0805.04002 |
[6] | Larson, PB; Zapletal, J., Geometric Set Theory. Mathematical Surveys and Monographs (2020), Providence: American Mathematical Society, Providence · Zbl 07269808 · doi:10.1090/surv/248 |
[7] | Marker, D., Model Theory: An Introduction. Graduate Texts in Mathematics (2002), New York: Springer, New York · Zbl 1003.03034 |
[8] | Schmerl, JH, Avoidable algebraic subsets of Euclidean space, Trans. Amer. Math. Soc., 352, 6, 2479-2489 (2000) · Zbl 0948.03045 · doi:10.1090/S0002-9947-99-02331-4 |
[9] | Shelah, S., Can you take Solovay’s inaccessible away?, Israel J. Math., 48, 1, 1-47 (1984) · Zbl 0596.03055 · doi:10.1007/BF02760522 |
[10] | Zapletal, J.: Coloring the distance graphs in three dimensions (2021). arXiv:2103.02757 |
[11] | Zapletal, J., Krull dimension in set theory, Ann. Pure Appl. Logic, 174, 9 (2023) · Zbl 07719409 · doi:10.1016/j.apal.2023.103299 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.