×

zbMATH — the first resource for mathematics

Colorings of spaces, and random graphs. (English. Russian original) Zbl 1146.05043
J. Math. Sci., New York 146, No. 2, 5723-5730 (2007); translation from Fundam. Prikl. Mat. 11, No. 6, 131-141 (2005).
Summary: This work deals with some problems on the embeddings of finite geometric graphs into the random ones. In particular, we study here applications of the random graph theory to the Nelson-Erdös-Hadwiger problem on coloring spaces.
MSC:
05C80 Random graphs (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] N. Alon and J. Spencer, The Probabilistic Method, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, New York (2000).
[2] B. Bollobás, ”Martingales, isoperimetric inequalities, and random graphs,” in: A. Hajnal, L. Lovász, and V. T. Sós, eds., Proceedings, Eger (1987), Colloq. Math. Soc. János Bolyai, Vol. 52, North-Holland, Amsterdam (1987), pp. 113–139.
[3] B. Bollobás, ”The chromatic number of random graphs,” Combinatorica, 8, 49–56 (1988). · Zbl 0666.05033 · doi:10.1007/BF02122551
[4] B. Bollobás, Random Graphs, Cambridge Univ. Press, Cambridge (2001).
[5] N. G. de Bruijn and P. Erdös, ”A colour problem for infinite graphs and a problem in the theory of relations,” Proc. Konink. Nederl. Akad. Wetensch., Ser. A, 54, No. 5, 371–373 (1951). · Zbl 0044.38203
[6] D. Coulson, ”A 15-colouring of 3-space omitting distance one,” Discrete Math., 256, 83–90 (2002). · Zbl 1007.05052 · doi:10.1016/S0012-365X(01)00183-2
[7] R. Diestel, Graph Theory, Springer (1997).
[8] P. Erdös and A. Rényi, ”On random graphs. I,” Publ. Math. Debrecen, 6, 290–297 (1959). · Zbl 0092.15705
[9] P. Erdös and A. Rényi, ”On the evolution of random graphs,” Publ. Math. Inst. Hung. Acad. Sci. Ser. A, 5, 17–61 (1960). · Zbl 0103.16301
[10] P. Erdös and A. Rényi, ”On the evolution of random graphs. II,” Bull. Inst. Int. Stat., 38, 343–347 (1961). · Zbl 0106.12006
[11] F. Harary, Graph Theory, Addison-Wesley, Reading (1969).
[12] H. Hadwiger, ”Ein Überdeckungssatz für den Euklidischen Raum,” Portugal. Math., 4, 140–144 (1944). · Zbl 0060.40610
[13] H. Hadwiger, ”Ungelöste Probleme N 40,” Elem. Math., 16, 103–104 (1961).
[14] S. Janson, ”New versions of Suen’s correlation inequality,” Random Structures Algorithms, 13, 467–483 (1998). · Zbl 0964.60011 · doi:10.1002/(SICI)1098-2418(199810/12)13:3/4<467::AID-RSA15>3.0.CO;2-W
[15] V. F. Kolchin, Random Graphs [in Russian], Fizmatlit, Moscow (2002). · Zbl 0918.05001
[16] D. G. Larman and C. A. Rogers, ”The realization of distances within sets in Euclidean space,” Mathematika, 19, 1–24 (1972). · Zbl 0246.05020 · doi:10.1112/S0025579300004903
[17] L. Moser and W. Moser, ”Solution to problem 10,” Can. Math. Bull., 4, 187–189 (1961). · Zbl 0111.09401
[18] O. Nechushtan, ”On the space chromatic number,” Discrete Math., 256, 499–507 (2002). · Zbl 1009.05058 · doi:10.1016/S0012-365X(00)00406-4
[19] A. M. Raigorodskii, ”On the chromatic number of the space,” Russian Math. Surveys, 55, No. 2, 147–148 (2000). · Zbl 0966.05029 · doi:10.1070/RM2000v055n02ABEH000281
[20] A. M. Raigorodskii, ”The Borsuk problem and the chromatic numbers of some metric spaces,” Russian Math. Surveys, 56, 103–139 (2001). · Zbl 1008.54018 · doi:10.1070/RM2001v056n01ABEH000358
[21] A. M. Raigorodskii, ”The Erdös-Hadwiger problem and the chromatic numbers of finite geometric graphs,” Dokl. Ross. Akad. Nauk, 392, No. 3, 313–317 (2003). · Zbl 1125.05041
[22] A. M. Raigorodskii, ”The Nelson-Erdös-Hadwiger problem, and the embeddings of random graphs into the geometric one,” Dokl. Ross. Akad. Nauk, 403, No. 2 (2005). · Zbl 1154.05023
[23] A. M. Raigorodskii, The Chromatic Numbers of Metric Spaces [in Russian], Proc. Math. Inst. NAN Belarus (2005). · Zbl 1070.05044
[24] A. M. Raigorodskii, ”The Erdös-Hadwiger problem and the chromatic numbers of finite geometric graphs,” Mat. Sb., 196, No. 1, 123–156 (2005). · Zbl 1070.05044
[25] A. Soifer, ”Chromatic number of the plane: A historical essay,” Geombinatorics, 1, No. 3, 13–15 (1991). · Zbl 0853.05038
[26] A. Soifer, Mathematical Coloring Book, Center for Excellence in Mathematical Education (1997).
[27] L. A. Székely, ”Erdös on unit distances and the Szemerédi-Trotter theorems,” in: Paul Erdös and His Mathematics. II. Based on the conference, Budapest, Hungary, July 4–11, Bolyai Soc. Math. Stud., Vol. 11, Springer, Berlin (2002), pp. 649–666. · Zbl 1035.05037
[28] M. Talagrand, ”Concentration of measures and isoperimetric inequalities in product spaces,” Publ. Math. IHES, 81, 73–205 (1996). · Zbl 0864.60013
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.