Geodesic
Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth
Matematičeskie zametki, Tome 101 (2017) no. 3, pp. 430-445.

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

We obtain some specific exponential lower bounds for the chromatic numbers of distance graphs with large girth.
Keywords: chromatic number, distance graph, Frankl–Rödl theorem. 
@article{MZM_2017_101_3_a9,
     author = {A. Sagdeev},
     title = {Lower {Bounds} for the {Chromatic} {Numbers} of {Distance} {Graphs} with {Large} {Girth}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {430--445},
     publisher = {mathdoc},
     volume = {101},
     number = {3},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2017_101_3_a9/}
}
TY  - JOUR
AU  - A. Sagdeev
TI  - Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth
JO  - Matematičeskie zametki
PY  - 2017
SP  - 430
EP  - 445
VL  - 101
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MZM_2017_101_3_a9/
LA  - ru
ID  - MZM_2017_101_3_a9
ER  - 
%0 Journal Article
%A A. Sagdeev
%T Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth
%J Matematičeskie zametki
%D 2017
%P 430-445
%V 101
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_2017_101_3_a9/
%G ru
%F MZM_2017_101_3_a9
A. Sagdeev. Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth. Matematičeskie zametki, Tome 101 (2017) no. 3, pp. 430-445. http://geodesic.mathdoc.fr/item/MZM_2017_101_3_a9/

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

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

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

[4] N. G. de Bruijn, P. Erdős, “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wet., Proc., Ser. A, 54:5 (1951), 371–373 | Zbl

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

[6] P. Erdős, “Unsolved problems”, Congres Numerantium, XV, Utilitas Math., Winnipeg, Man., 1976, 678–696 | MR

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

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

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

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

[11] A. M. Raigorodskii, O. I. Rubanov, “Small clique and large chromatic number”, European Conference on Combinatorics, Graph Theory and Applications, Electron. Notes Discrete Math., 34, Elsevier Sci. B. V., Amsterdam, 2009, 441–445 | DOI | MR | Zbl

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

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

[14] A. B. Kupavskii, A. M. Raigorodskii, “O distantsionnykh grafakh s bolshim khromaticheskim i malym klikovym chislami”, Dokl. AN, 444:5 (2012), 483–487 | MR | Zbl

[15] A. E. Zvonarev, A. M. Raigorodskii, “O distantsionnykh grafakh s bolshim khromaticheskim i malym klikovym chislami”, Tr. MFTI, 4:1 (2012), 122–126

[16] A. B. Kupavskii, A. M. Raigorodskii, “O prepyatstviyakh k realizatsii distantsionnykh grafov s bolshim khromaticheskim chislom na sferakh malogo radiusa”, Matem. sb., 204:10 (2013), 47–90 | DOI | MR | Zbl

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

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

[19] N. Alon, A. Kupavskii, “Two notions of unit distance graphs”, J. Combin. Theory Ser. A, 125 (2014), 1–17 | DOI | MR | Zbl

[20] P. K. Agarwal, J. Pach, Combinatorial Geometry, John Wiley and Sons, New York, 1995 | MR | Zbl

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

[22] A. Soifer, The Mathematical Coloring Book. Mathematics of Coloring and the Colorful Life of Its Creators, Springer-Verlag, Berlin, 2009 | MR | Zbl

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

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

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

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

[27] P. Frankl, V. Rödl, “Forbidden intersections”, Trans. of Amer. Math. Soc., 300:1 (1987), 259–286 | DOI | MR | Zbl

[28] A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “Uluchshenie teoremy Frankla–Redlya o chisle reber gipergrafa s zapretami na peresecheniya”, Dokl. AN, 457:2 (2014), 144–146 | DOI | MR | Zbl

[29] A. E. Zvonarev, A. M. Raigorodskii, D. V. Samirov, A. A. Kharlamova, “O khromaticheskom chisle prostranstva s zapreschennym ravnostoronnim treugolnikom”, Matem. sb., 205:9 (2014), 97–120 | DOI | MR | Zbl

[30] A. E. Zvonarev, A. M. Raigorodskii, “Uluchsheniya teoremy Frankla–Redlya o chisle reber gipergrafa s zapreschennym peresecheniem i ikh sledstviya v zadache o khromaticheskom chisle prostranstva s zapreschennym ravnostoronnim treugolnikom”, Geometriya, topologiya i prilozheniya, Tr. MIAN, 288, MAIK, M., 2015, 109–119 | DOI | MR | Zbl