On the realization of random graphs as distance graphs in spaces of fixed dimension
type: Item
instance of: scholarly article
title: On the realization of random graphs as distance graphs in spaces of fixed dimension
zbMATH Open document ID: 1253.05129
DOI: 10.1134/S1064562409010189
author: S. V. Nagaeva
author: Andrei M. Raigorodskii
published in: Doklady Mathematics
publication date: 2012-11-15T00:00:00Z
review text: 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.
reviewed by: Nikolaos Fountoulakis
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C62
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 6106386
zbMATH Keywords: distance graphs
zbMATH Keywords: random graphs
zbMATH Keywords: largest distance graphs
MaRDI profile type: Publication
cites work: Embeddability of finite distance graphs with a large chromatic number in random graphs
cites work: On Ramsey Type Problems in Combinatorial Geometry
cites work: Q3950588
cites work: The probabilistic method
full work available at URL: s1064562409010189
OpenAlex ID: W1988932234
description: scientific article; zbMATH DE number 6106386