Geodesic
Counterexamples to Borsuk's Conjecture with Large Girth
Matematičeskie zametki, Tome 105 (2019) no. 6, pp. 890-898.

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

Borsuk's celebrated conjecture, which has been disproved, can be stated as follows: in $\mathbb R^n$, there exist no diameter graphs with chromatic number larger than $n+1$. In this paper, we prove the existence of counterexamples to Borsuk's conjecture which, in addition, have large girth. This study is in the spirit of O'Donnell and Kupavskii, who studied the existence of distance graphs with large girth. We consider both cases of strict and nonstrict diameter graphs. We also prove the existence of counterexamples with large girth to a statement of Lovász concerning distance graphs on the sphere.
Keywords: distance graph, Borsuk's problem. 
@article{MZM_2019_105_6_a6,
     author = {R. I. Prosanov},
     title = {Counterexamples to {Borsuk's} {Conjecture} with {Large} {Girth}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {890--898},
     publisher = {mathdoc},
     volume = {105},
     number = {6},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2019_105_6_a6/}
}
TY  - JOUR
AU  - R. I. Prosanov
TI  - Counterexamples to Borsuk's Conjecture with Large Girth
JO  - Matematičeskie zametki
PY  - 2019
SP  - 890
EP  - 898
VL  - 105
IS  - 6
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2019_105_6_a6/
LA  - ru
ID  - MZM_2019_105_6_a6
ER  - 
%0 Journal Article
%A R. I. Prosanov
%T Counterexamples to Borsuk's Conjecture with Large Girth
%J Matematičeskie zametki
%D 2019
%P 890-898
%V 105
%N 6
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2019_105_6_a6/
%G ru
%F MZM_2019_105_6_a6
R. I. Prosanov. Counterexamples to Borsuk's Conjecture with Large Girth. Matematičeskie zametki, Tome 105 (2019) no. 6, pp. 890-898. http://geodesic.mathdoc.fr/item/MZM_2019_105_6_a6/

[1] K. Borsuk, “Drei Sätze über die $n$-dimensionale euklidische Sphäre”, Fundam. Math., 20 (1933), 177–190 | DOI

[2] J. Kahn, G. Kalai, “A counterexample to Borsuk's conjecture”, Bull. Amer. Math. Soc. (N.S.), 29:1 (1993), 60–62 | DOI | MR | Zbl

[3] P. Brass, W. Moser, J. Pach, Research Problems in Discrete Geometry, Springer-Verlag, New York, 2005 | MR | Zbl

[4] V. G. Boltyanski, H. Martini, P. S. Soltan, Excursions into Combinatorial Geometry, Springer-Verlag, Berlin, 1997 | MR | Zbl

[5] A. M. Raigorodskii, “Problema Borsuka i khromaticheskie chisla nekotorykh metricheskikh prostranstv”, UMN, 56:1 (337) (2001), 107–146 | DOI | MR | Zbl

[6] A. M. Raigorodskii, “Vokrug gipotezy Borsuka”, Geometriya i mekhanika, SMFN, 23, RUDN, M., 2007, 147–164 | MR | Zbl

[7] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, Surveys in Contemporary Mathematics, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2007, 202–248 | MR

[8] A. M. Raigorodskii, “Combinatorial geometry and coding theory”, Fund. Inform., 145:3 (2016), 359–369 | MR | Zbl

[9] A. Soifer, The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, Springer-Verlag, New York, 2008 | MR

[10] A. M. Raigorodskii, “Coloring distance graphs and graphs of diameters”, Thirty Essays on Geometric Graph Theory, Springer-Verlag, New York, 2013, 429–460 | MR | Zbl

[11] A. M. Raigorodskii, “Cliques and cycles in distance graphs and graphs of diameters”, Discrete Geometry and Algebraic Combinatorics, Contemp. Math., 625, Amer. Math. Soc., Providence, RI, 2014, 93–109 | MR | Zbl

[12] A. M. Raigorodskii, D. D. Cherkashin, “O khromaticheskikh chislakh prostranstv maloi razmernosti”, Dokl. AN, 472:1 (2017), 11–12 | Zbl

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

[14] L. I. Bogolyubskii, A. M. Raigorodskii, “Ob izmerimom khromaticheskom chisle prostranstva razmernosti $n\le 24$”, Dokl. AN, 465:6 (2015), 647–650 | DOI

[15] L. I. Bogolyubskii, A. M. Raigorodskii, “Zamechanie o nizhnikh otsenkakh khromaticheskikh chisel prostranstv maloi razmernosti s metrikami $\ell_1$ i $\ell_2$”, Matem. zametki, 105:2 (2019), 187–213 | DOI

[16] A. Ya. Kanel-Belov, V. A. Voronov, D. D. Cherkashin, “O khromaticheskom chisle ploskosti”, Algebra i analiz, 29:5 (2017), 68–89 | MR

[17] N. G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wetensch. Proc. Ser. A, 54 (1951), 369–373 | DOI | MR

[18] A. D. N. J. de Grey, “The chromatic number of the plane is at least 5”, Geombinatorics, 28:1 (2018), 18–31 | MR | Zbl

[19] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva”, UMN, 55:2 (332) (2000), 147–148 | DOI | MR | Zbl

[20] D. G. Larman, C. A. Rogers, “The realization of distances within sets in Euclidean space”, Mathematika, 19 (1972), 1–24 | DOI | MR | Zbl

[21] R. Prosanov, A New Proof of the Larman–Rogers Upper Bound for the Chromatic Number of the Euclidean Space, 2016, arXiv: 1610.02846

[22] P. Erdős, “Graph theory and probability”, Canad. J. Math., 11 (1959), 34–38 | DOI | MR | Zbl

[23] L. Lovász, “On chromatic number of finite set-systems”, Acta Math. Acad. Sci. Hungar., 19 (1968), 59–67 | DOI | MR | Zbl

[24] P. O'Donnell, “Arbitrary girth, $4$-chromatic unit distance graphs in the plane I. Graph description”, Geombinatorics, 9:3 (2000), 145–152 | MR

[25] P. O'Donnell, “Arbitrary girth, $4$-chromatic unit distance graphs in the plane II. Graph embedding”, Geombinatorics, 9:4 (2000), 180–193 | MR | Zbl

[26] A. B. Kupavskii, “Distance graphs with large chromatic number and arbitrary girth”, Mosc. J. Comb. Number Theory, 2:2 (2012), 52–62 | MR | Zbl

[27] A. B. Kupavskii, “Yavnye i veroyatnostnye konstruktsii distantsionnykh grafov s malenkim klikovym i bolshim khromaticheskim chislami”, Izv. RAN. Ser. matem., 78:1 (2014), 65–98 | DOI | MR | Zbl

[28] Yu. A. Demidovich, “Nizhnyaya otsenka khromaticheskogo chisla ratsionalnogo prostranstva s metrikoi $l_u$ s odnim zapreschennym rasstoyaniem”, Matem. zametki, 102:4 (2017), 532–548 | DOI | MR | Zbl

[29] A. B. Kupavskii, A. Polyanskii, “Proof of Schur's conjecture in $\mathbb R^D$”, Combinatorica, 37:6 (2017), 1181–1205 | DOI | MR | Zbl

[30] L. Lovász, “Self-dual polytopes and the chromatic number of distance graphs on the sphere”, Acta Sci. Math. (Szeged), 45:1-4 (1983), 317–323 | MR | Zbl

[31] A. M. Raigorodskii, “On the chromatic numbers of spheres in $\mathbb R^n$”, Combinatorica, 32:1 (2012), 111–123 | DOI | MR | Zbl

[32] O. A. Kostina, A. M. Raigorodskii, “O nizhnikh otsenkakh khromaticheskogo chisla sfery”, Dokl. AN, 463:6 (2015), 639–641 | DOI | Zbl

[33] A. A. Sagdeev, “O teoreme Frankla–Redla”, Izv. RAN. Ser. matem., 82:6 (2018), 128–157 | DOI | Zbl

[34] A. M. Raigorodskii, A. A. Sagdeev, “O khromaticheskom chisle prostranstva s zapreschennym pravilnym simpleksom”, Dokl. AN, 472:2 (2017), 127–129 | DOI | Zbl

[35] A. A. Sagdeev, “O nizhnikh otsenkakh khromaticheskikh chisel distantsionnykh grafov s bolshim obkhvatom”, Matem. zametki, 101:3 (2017), 430–445 | DOI | MR | Zbl

[36] R. I. Prosanov, A. M. Raigorodskii, A. A. Sagdeev, “Uluchsheniya teoremy Frankla–Redlya i geometricheskie sledstviya”, Dokl. AN, 475:2 (2017), 137–139 | DOI | Zbl

[37] A. A. Sagdeev, “On a Frankl–Rödl theorem and its geometric corollaries”, Electron. Notes in Discrete Math., 61 (2017), 1033–1037 | DOI | Zbl

[38] A. A. Sagdeev, “O khromaticheskom chisle prostranstva s zapreschennym pravilnym simpleksom”, Matem. zametki, 102:4 (2017), 579–585 | DOI | MR | Zbl

[39] A. A. Sagdeev, “Uluchshennaya teorema Frankla–Redlya i nekotorye ee geometricheskie sledstviya”, Probl. peredachi inform., 54:2 (2018), 45–72

[40] A. A. Sagdeev, “Eksponentsialno ramseevskie mnozhestva”, Probl. peredachi inform., 54:4 (2018), 82–109

[41] R. C. Baker, G. Harman, J. Pintz, “The difference between consecutive primes. II”, Proc. London Math. Soc. (3), 83:3 (2001), 532–562 | DOI | MR | Zbl

[42] A. B Kupavskii, A. M. Raigorodskii, “Counterexamples to Borsuk's conjecture on spheres of small radii”, Mosc. J. Comb. Number Theory, 2:4 (2012), 27–48 | MR | Zbl