Random Geometric Graphs and Isometries of Normed Spaces

Balister, Paul; Bollobás, Béla; Gunderson, Karen; Leader, Imre; Walters, Mark
Given a countable dense subset {\$}S{\$} of a finite-dimensional normed space {\$}X{\$}, and {\$}0{\textless}p{\textless}1{\$}, we form a random graph on {\$}S{\$} by joining, independently and with probability {\$}p{\$}, each pair of points at distance less than {\$}1{\$}. We say that {\$}S{\$} is `Rado' if any two such random graphs are (almost surely) isomorphic. Bonato and Janssen showed that in {\$}l{\_}\backslashinfty{\^{}}d{\$} almost all {\$}S{\$} are Rado. Our main aim in this paper is to show that {\$}l{\_}\backslashinfty{\^{}}d{\$} is the unique normed space with this property: indeed, in every other space almost all sets {\$}S{\$} are non-Rado. We also determine which spaces admit some Rado set: this turns out to be the spaces that have an {\$}l{\_}\backslashinfty{\$} direct summand. These results answer questions of Bonato and Janssen. A key role is played by the determination of which finite-dimensional normed spaces have the property that every bijective step-isometry (meaning that the integer part of distances is preserved) is in fact an isometry. This result may be of independent interest.
Research areas:
Type of Publication:
Hits: 3233

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information