On the realization of random graphs as distance graphs in spaces of fixed dimension (Q1760937)

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.