Geodesic
Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces
Matematičeskie zametki, Tome 109 (2021) no. 5, pp. 723-733.

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

We prove the existence in rational spaces of distance graphs without short odd cycles whose chromatic number increases exponentially with the dimension of the space.
Keywords: chromatic number, linear-algebraic method, distance graph, graph girth. 
@article{MZM_2021_109_5_a5,
     author = {Yu. A. Demidovich and M. E. Zhukovskii},
     title = {Chromatic {Numbers} of {Distance} {Graphs} without {Short} {Odd} {Cycles} in {Rational} {Spaces}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {723--733},
     publisher = {mathdoc},
     volume = {109},
     number = {5},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2021_109_5_a5/}
}
TY  - JOUR
AU  - Yu. A. Demidovich
AU  - M. E. Zhukovskii
TI  - Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces
JO  - Matematičeskie zametki
PY  - 2021
SP  - 723
EP  - 733
VL  - 109
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2021_109_5_a5/
LA  - ru
ID  - MZM_2021_109_5_a5
ER  - 
%0 Journal Article
%A Yu. A. Demidovich
%A M. E. Zhukovskii
%T Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces
%J Matematičeskie zametki
%D 2021
%P 723-733
%V 109
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2021_109_5_a5/
%G ru
%F MZM_2021_109_5_a5
Yu. A. Demidovich; M. E. Zhukovskii. Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces. Matematičeskie zametki, Tome 109 (2021) no. 5, pp. 723-733. http://geodesic.mathdoc.fr/item/MZM_2021_109_5_a5/

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

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

[3] 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 | DOI | MR | Zbl

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

[5] Yu. A. Demidovich, “Distantsionnye grafy v ratsionalnom prostranstve s bolshim khromaticheskim chislom i bez klik zadannogo razmera”, Matem. zametki, 106:1 (2019), 24–39 | DOI | Zbl

[6] A. M. Raigorodskii, “O khromaticheskom chisle prostranstva s metrikoi $l_q$”, UMN, 59:5 (359) (2004), 161–162 | DOI | MR | Zbl

[7] E. I. Ponomarenko, A. M. Raigorodskii, “Novaya nizhnyaya otsenka khromaticheskogo chisla ratsionalnogo prostranstva”, UMN, 68:5 (413) (2013), 183–184 | DOI | MR | Zbl

[8] E. I. Ponomarenko, A. M. Raigorodskii, “Novaya nizhnyaya otsenka khromaticheskogo chisla ratsionalnogo prostranstva s odnim i dvumya zapreschennymi rasstoyaniyami”, Matem. zametki, 97:2 (2015), 255–261 | DOI | MR | Zbl

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

[10] 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

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

[12] E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distantsionnye grafy, imeyuschie bolshoe khromaticheskoe chislo i ne soderzhaschie klik ili tsiklov zadannogo razmera”, Matem. sb., 204:4 (2013), 49–78 | DOI | MR | Zbl

[13] 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

[14] A. M. Raigorodskii, “O distantsionnykh grafakh, imeyuschikh bolshoe khromaticheskoe chislo, no ne soderzhaschikh bolshikh simpleksov”, UMN, 62:6 (378) (2007), 187–188 | DOI | MR | Zbl

[15] A. M. Raigorodskii, O. I. Rubanov, “On the clique and the chromatic numbers of high-dimensional distance graphs”, Number Theory and Applications, Hindustan Book Agency, New Delhi, 2009, 149–155 | MR | Zbl

[16] A. M. Raigorodskii, O. I. Rubanov, “O grafakh rasstoyanii s bolshim khromaticheskim chislom i bez bolshikh klik”, Matem. zametki, 87:3 (2010), 417–428 | DOI | MR | Zbl

[17] A. A. Sagdeev, “Ob odnoi teoreme Frankla–Uilsona”, Probl. peredachi inform., 55:4 (2019), 86–106 | DOI | MR | Zbl

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

[19] A. B. Kupavskii, A. A. Sagdeev, “Teoriya Ramseya v prostranstve s chebyshevskoi metrikoi”, UMN, 75:5 (455) (2020), 191–192 | DOI | Zbl

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

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

[22] A. V. Berdnikov, “Otsenka khromaticheskogo chisla evklidova prostranstva s neskolkimi zapreschennymi rasstoyaniyami”, Matem. zametki, 99:5 (2016), 783–787 | DOI | MR | Zbl

[23] L. E. Shabanov, A. M. Raigorodskii, “Turán type results for distance graphs”, Discrete Comput. Geom., 56:3 (2016), 814–832 | DOI | MR | Zbl

[24] F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v osobykh podgrafakh nekotorogo distantsionnogo grafa”, Matem. zametki, 107:2 (2020), 286–298 | DOI | Zbl

[25] 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

[26] A. A. Sokolov, A. M. Raigorodskii, “O ratsionalnykh analogakh problem Nelsona–Khadvigera i Borsuka”, Chebyshevskii sb., 19:3 (2018), 270–281 | DOI | Zbl

[27] A. M. Raigorodskii, M. M. Koshelev, “Novye otsenki kliko-khromaticheskikh chisel grafov Dzhonsona”, Dokl. AN, 490:1 (2020), 78–80 | DOI

[28] M. M. Ipatov, M. M. Koshelev, A. M. Raigorodskii, “Modulyarnost nekotorykh distantsionnykh grafov”, Dokl. AN, 490:1 (2020), 71–73 | DOI

[29] A. M. Raigorodskii, M. M. Koshelev, “New bounds on clique-chromatic numbers of Johnson graphs”, Discrete Appl. Math., 283 (2020), 724–729 | DOI | MR | Zbl

[30] A. A. Sagdeev, A. M. Raigorodskii, “On a Frankl–Wilson theorem and its geometric corollaries”, Acta Math. Univ. Comenian. (N.S.), 88:3 (2019), 1029–1033 | MR

[31] D. A. Zakharov, A. M. Raigorodskii, “Kliko-khromaticheskie chisla grafov peresechenii”, Matem. zametki, 105:1 (2019), 142–144 | DOI | Zbl

[32] A. M. Raigorodskii, E. D. Shishunov, “O chislakh nezavisimosti nekotorykh distantsionnykh grafov s vershinami v $\{-1,0,1\}^n$”, Dokl. AN, 488:5 (2019), 269–271 | DOI

[33] N. Frankl, A. Kupavskii, K. J. Swanepoel, “Embedding graphs in Euclidean space”, J. Combin. Theory Ser. A, 171 (2020), 105146 | DOI | MR | Zbl