Geodesic
On rational analogs of Nelson--Hadwiger's and Borsuk's problems
Čebyševskij sbornik, Tome 19 (2018) no. 3, pp. 270-281.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we consider affine-rational analogs of Nelson–Hadwiger problem on finding the chromatic number of the rational space and Borsuk's problem on partitioning into parts of smaller diameter. New lower bounds are proved. In particular, bounds on the minimum dimension of a counterexample to Borsuk's conjecture are found.
Keywords: Chromatic number, unit-distance graphs, Borsuk's problem. 
@article{CHEB_2018_19_3_a21,
     author = {A. Sokolov and A. M. Raigorodskiy},
     title = {On rational analogs of {Nelson--Hadwiger's} and {Borsuk's} problems},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {270--281},
     publisher = {mathdoc},
     volume = {19},
     number = {3},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a21/}
}
TY  - JOUR
AU  - A. Sokolov
AU  - A. M. Raigorodskiy
TI  - On rational analogs of Nelson--Hadwiger's and Borsuk's problems
JO  - Čebyševskij sbornik
PY  - 2018
SP  - 270
EP  - 281
VL  - 19
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a21/
LA  - ru
ID  - CHEB_2018_19_3_a21
ER  - 
%0 Journal Article
%A A. Sokolov
%A A. M. Raigorodskiy
%T On rational analogs of Nelson--Hadwiger's and Borsuk's problems
%J Čebyševskij sbornik
%D 2018
%P 270-281
%V 19
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a21/
%G ru
%F CHEB_2018_19_3_a21
A. Sokolov; A. M. Raigorodskiy. On rational analogs of Nelson--Hadwiger's and Borsuk's problems. Čebyševskij sbornik, Tome 19 (2018) no. 3, pp. 270-281. http://geodesic.mathdoc.fr/item/CHEB_2018_19_3_a21/

[1] A.M. Raigorodskii, “Coloring Distance Graphs and Graphs of Diameters”, Thirty Essays on Geometric Graph Theory, ed. J. Pach, Springer, 2013, 429–460 | MR | Zbl

[2] P.K. Agarwal, J. Pach, Combinatorial geometry, John Wiley and Sons Inc., New York, 1995 | MR | Zbl

[3] V. Klee, S. Wagon, Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991 | MR | Zbl

[4] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005 | MR | Zbl

[5] L.A. Székely, “Erdős on unit distances and the Szemerédi – Trotter theorems”, Paul Erdős and his Mathematics, Bolyai Series, 11, J. Bolyai Math. Soc., Springer, Budapest, 2002, 649–666 | MR | Zbl

[6] A. Soifer, The Mathematical Coloring Book, Springer, 2009 | MR | Zbl

[7] A. de Grey, The chromatic number of the plane is at least 5, April 2018, arXiv: 1804.02385 | MR

[8] A.M. Raigorodskii, “The Borsuk problem and the chromatic numbers of some metric spaces”, Russian Math. Surveys, 56:1 (2001), 103–139 | MR | Zbl

[9] A.M. Raigorodskii, “The Erdős–Hadwiger problem and the chromatic numbers of finite geometric graphs”, Sbornik Math., 196:1 (2005), 115–146 | MR | Zbl

[10] A.M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemporary Mathematics, 625, AMS, 2014, 93–109 | MR | Zbl

[11] A.M. Raigorodskii, “Combinatorial geometry and coding theory”, Fundamenta Informatica, 145 (2016), 359–369 | MR | Zbl

[12] L.I. Bogoliubsky, A.M. Raigorodskii, “A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics $ l_1, l_2 $”, Math. Notes., 105:2 (2019), 180–203 | MR | MR

[13] D.A. Zakharov, A.M. Raigorodskii, “Clique-chromatic numbers of graphs of intersections”, Math. Notes., 105:1 (2019), 137–139 | MR | Zbl

[14] E.A. Shishunov, A.M. Raigorodskii, “On the independence numbers of some distance graphs with vertices in $ \{-1,0,1\}^n $”, Doklady Math., 99:2 (2019), 165–166 | MR | Zbl

[15] O. A. Kostina, “On Lower Bounds for the Chromatic Number of Spheres”, Math. Notes, 105:1 (2019), 16–27 | MR | Zbl

[16] F.A. Pushnyakov, “On the number of edges in induced subgraphs of some distance graphs”, Math. Notes, 105:4 (2019) | MR | Zbl

[17] Yu. A. Demidovich, “Distance graphs in rational spaces with large chromatic number and without cliques of given size”, Math. Notes, 106:1 (2019) | MR | Zbl

[18] A.M. Raigorodskii, A.B. Kupavskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, Electronic Notes in Discrete Mathematics, 34 (2009), 435–439 | MR | Zbl

[19] A. Ya. Kanel-Belov, V. A. Voronov, D. D. Cherkashin, “On the chromatic number of infinitesimal plane layer”, St. Petersburg Math. J., 29:5 (2018), 761–775 | MR | Zbl

[20] D.D. Cherkashin, A.M. Raigorodskii, “On the chromatic numbers of small-dimensional spaces”, Doklady Math., 95:1 (2017), 5–6 | MR | MR | Zbl

[21] D. Cherkashin, A. Kulikov, A. Raigorodskii, “On the chromatic numbers of small-dimensional Euclidean spaces”, Discrete and Applied Math., 243 (2018), 125–131 | MR | Zbl

[22] M. Benda, M. Perles, “Colorings of metric spaces”, Geombinatorics, 9 (2000), 113–126 | MR | Zbl

[23] A.M. Raigorodskii, “On the chromatic number of a space with $ l_q $-norm”, Russian Math. Surveys, 59:5 (2004), 973–975 | MR | Zbl

[24] A.M. Raigorodskii, I.M. Shitova, “On the chromatic numbers of real and rational spaces with several real or rational forbidden distances”, Sbornik Math., 199:4 (2008), 579–612 | MR | Zbl

[25] E.I. Ponomarenko, A.M. Raigorodskii, “New lower bound on the chromatic number of the rational space”, Russian Math. Surveys, 68:5 (2013), 960–962 | MR | Zbl

[26] E.I. Ponomarenko, A.M. Raigorodskii, “New lower bound on the chromatic number of the rational space with one or two forbidden distances”, Math. Notes, 97:2 (2015), 255–261

[27] Yu. A. Demidovich, “Lower Bound for the Chromatic Number of a Rational Space with Metric $l_1$ and with One Forbidden Distance”, Math. Notes, 102:4 (2017), 492–507 | MR | Zbl

[28] E.I. Ponomarenko, A.M. Raigorodskii, “On the chromatic number of the space $ {\mathbb Q}^n $”, Proceedings of Moscow Institute of Physics and Technology, 4:1 (2012), 127–130

[29] A. Sokolov, “On the Chromatic Numbers of Rational Spaces”, Math. Notes, 103 (2018), 1–2 | MR | Zbl

[30] V.G. Boltyanski, H. Martini, P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997 | MR | Zbl

[31] A.M. Raigorodskii, “Around Borsuk's conjecture”, J. of Math. Sci., 154:4 (2008), 604–623 | MR | Zbl

[32] A.M. Raigorodskii, “Three lectures on the Borsuk partition problem”, London Mathematical Society Lecture Note Series, 347, 2007, 202–248 | MR

[33] A.M. Raigorodskii, “The Borsuk and Grünbaum problems for lattice polytopes”, Izvestiya Math., 69:3 (2005), 513–537 | MR | Zbl

[34] A.M. Raigorodskii, A.B. Kupavskii, E.I. Ponomarenko, “On some analogs of Borsuk's problem in the space $\mathbb Q^n$”, Proceedings of of Moscow Institute of Physics and Technology, 4:1 (2012), 81–90

[35] K.B. Chilakamarri, “Unit-distance graphs in rational $n$-spaces”, Discrete Math., 69 (1988), 213–218 | MR | Zbl

[36] C. Elsholtz, W. Klotz, “Maximal Dimension of Unit Simplices”, Discrete Comput Geom., 34 (2005), 167–177 | MR | Zbl

[37] A. Bondarenko, “On Borsuk's Conjecture for Two-Distance Sets”, Discrete Comput Geom., 51 (2014), 509–515 | MR | Zbl

[38] N.G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54:5 (1951), 371–373 | MR | Zbl