Geodesic
Chromatic Numbers of Distance Graphs without Short Odd Cycles in Rational Spaces
Matematičeskie zametki, Tome 109 (2021) no. 5, pp. 723-733 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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},
     year = {2021},
     volume = {109},
     number = {5},
     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
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
%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