On the realization of random graphs as distance graphs in spaces of fixed dimension (Q1760937)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the realization of random graphs as distance graphs in spaces of fixed dimension |
scientific article |
Statements
On the realization of random graphs as distance graphs in spaces of fixed dimension (English)
0 references
15 November 2012
0 references
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.
0 references
distance graphs
0 references
random graphs
0 references
largest distance graphs
0 references