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. 
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/
@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},
     year = {2019},
     volume = {106},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/MZM_2019_106_1_a2/
%G ru
%F 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