Geodesic
Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space
Matematičeskie zametki, Tome 106 (2019) no. 1, pp. 24-39.

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

We study distance graphs with exponentially large chromatic number which do not contain cliques of prescribed size in the rational space.
Keywords: distance graph, chromatic number, clique number. 
@article{MZM_2019_106_1_a2,
     author = {Yu. A. Demidovich},
     title = {Distance {Graphs} with {Large} {Chromatic} {Number} and without {Cliques} of {Given} {Size} in the {Rational} {Space}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {24--39},
     publisher = {mathdoc},
     volume = {106},
     number = {1},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2019_106_1_a2/}
}
TY  - JOUR
AU  - Yu. A. Demidovich
TI  - Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space
JO  - Matematičeskie zametki
PY  - 2019
SP  - 24
EP  - 39
VL  - 106
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2019_106_1_a2/
LA  - ru
ID  - MZM_2019_106_1_a2
ER  - 
%0 Journal Article
%A Yu. A. Demidovich
%T Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space
%J Matematičeskie zametki
%D 2019
%P 24-39
%V 106
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2019_106_1_a2/
%G ru
%F MZM_2019_106_1_a2
Yu. A. Demidovich. Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space. Matematičeskie zametki, Tome 106 (2019) no. 1, pp. 24-39. http://geodesic.mathdoc.fr/item/MZM_2019_106_1_a2/

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

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

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

[4] D. R. Woodall, “Distances realized by sets covering the plane”, J. Combin. Theory Ser. A, 1973, no. 14, 187–200 | DOI | MR | Zbl

[5] J. Cibulka, “On the chromatic number of real and rational spaces”, Geombinatorics, 18:2 (2008), 53–66 | MR

[6] K. Chilakamarri, “The unit-distance graph problem: a brief survey and some new results”, Bull. Inst. Combin. Appl., 8 (1993), 39–60 | MR | Zbl

[7] M. Mann, “Hunting unit-distance graphs in rational n-spaces”, Geombinatorics, 13:2 (2003), 49–53 | MR

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

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

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

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

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

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

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

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

[16] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007

[17] A. M. Raigorodskii, Khromaticheskie chisla, MTsNMO, M., 2003

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

[19] P. Frankl, R. M. Wilson, “Intersection theorems with geometric consequences”, Combinatorica, 1:4 (1981), 357–368 | DOI | MR | Zbl

[20] L. A. Székely, “Erdös on unit distances and the Szemerédi–Trotter theorems”, Paul Erdös and his mathematics. II, Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR

[21] A. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosv., ser. 3, 8, Izd-vo MTsNMO, M., 2004, 186–221

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

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

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

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

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

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

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

[29] L. E. Shabanov, A. M. Raigorodskii, “Turanovskie otsenki dlya distantsionnykh grafov”, Dokl. AN, 475:3 (2017), 254–256 | DOI | Zbl

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

[31] O. A. Kostina, “O nizhnikh otsenkakh khromaticheskogo chisla sfery”, Matem. zametki, 105:1 (2019), 18–31 | DOI

[32] A. M. Raigorodskii, “K odnoi teoreme Lovasa o khromaticheskom chisle sfery”, Matem. zametki, 98:3 (2015), 470–471 | DOI | MR | Zbl

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

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

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

[36] R. I. Prosanov, “Kontrprimery k gipoteze Borsuka, imeyuschie bolshoi obkhvat”, Matem. zametki, 105:6 (2019), 890–898

[37] A. A. Sagdeev, A. M. Raigorodskii, “On a Frankl–Wilson theorem and its geometric corollaries”, Acta Math. Univ. Comenian. (N.S.) (to appear)

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

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

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

[41] N. Alon, J. H. Spencer, The Probabilistic Method, Wiley-Interscience, New York, 2000 | MR | Zbl

[42] B. Bollobás, Random Graphs, Cambridge Stud. Adv. Math., 73, Cambridge Univ. Press, Cambridge, 2001 | MR | Zbl

[43] A. M. Raigorodskii, Veroyatnost i algebra v kombinatorike, MTsNMO, M., 2008