zbMATH — the first resource for mathematics

On the realization of random graphs as distance graphs in spaces of fixed dimension. (English. Russian original) Zbl 1253.05129
Dokl. Math. 79, No. 1, 63-65 (2009); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 424, No. 3, 315-317 (2009).
This paper considers the size of the largest subgraph of an Erdős-Rényi random graph that is isomorphic to a distance graph of a certain dimension and given chromatic number. It was shown for any density that this number is bounded by a quantity that is proportional to \(\ln n / \ln (1/(1-p))\) (the coefficient is exponential on the dimension of the space and \(n\) is the number of vertices). The main result of this paper states that \(\ln n / \ln (1/(1-p))\) is also a lower bound when the density of the random graph grows as a polynomial in \(n\) and it is not too close to 1.

05C80 Random graphs (graph-theoretic aspects)
05C15 Coloring of graphs and hypergraphs
05C62 Graph representations (geometric and intersection representations, etc.)
60C05 Combinatorial probability
Full Text: DOI
[1] A. M. Raigorodskii, Dokl. Math. 72, 516–518 (2005) [Dokl. Akad. Nauk 403, 169–171 (2005)].
[2] A. M. Raigorodskii, Usp. Mat. Nauk, No. 4, 195–196 (2006).
[3] A. M. Raigorodskii, Fundam. Prikl. Mat. 11(6), 131–141 (2005).
[4] S. V. Nagaeva, Dokl. Math. 77, 13–16 (2008) [Dokl. Akad. Nauk 418, 19–22 (2008)]. · Zbl 1194.05026 · doi:10.1134/S1064562408010043
[5] S. V. Nagaeva and A. M. Raigorodskii, in Advances in Science and Technology: Modern Mathematics (VINITI, Moscow, 2008) [in Russian].
[6] A. M. Raigorodskii, Usp. Mat. Nauk 56(1), 107–146 (2001). · doi:10.4213/rm358
[7] A. M. Raigorodskii, Linear Algebraic Method in Combinatorics (MTsNMO, Moscow, 2007) [in Russian]. · Zbl 1341.05247
[8] A. M. Raigorodskii, Chromatic Numbers (MTsNMO, Moscow, 2003) [in Russian].
[9] P. Brass, W. Moser, and J. Pach, Research Problems in Discrete Geometry (Springer-Verlag, Berlin, 2005).
[10] F. Harary, Graph Theory (Addison-Wesley, Reading, Mass., 1969; Mir, Moscow, 1973).
[11] B. Bollobas, Random Graphs (Cambridge Univ. Press, Cambridge, 2001). · Zbl 0489.05050
[12] N. Alon and J. Spencer, The Probabilistic Method (Wiley, New York, 2002; Binom, Moscow, 2007). · Zbl 1333.05001
[13] A. M. Raigorodskii, Probability and Algebra in Combinatorics (MTsNMO, Moscow, 2008) [in Russian].
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.