Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Random geometric graphs and isometries of normed spaces


Authors: Paul Balister, Béla Bollobás, Karen Gunderson, Imre Leader and Mark Walters
Journal: Trans. Amer. Math. Soc. 370 (2018), 7361-7389
MSC (2010): Primary 05C63, 05C80, 46B04
DOI: https://doi.org/10.1090/tran/7420
Published electronically: June 20, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Given a countable dense subset $ S$ of a finite-dimensional normed space $ X$, and $ 0<p<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 $ \ell _\infty ^d$ almost all $ S$ are Rado. Our main aim in this paper is to show that $ \ell _\infty ^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 $ \ell _\infty $ 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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05C63, 05C80, 46B04

Retrieve articles in all journals with MSC (2010): 05C63, 05C80, 46B04


Additional Information

Paul Balister
Affiliation: Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee
Email: pbalistr@memphis.edu

Béla Bollobás
Affiliation: Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK—and—Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee—and—London Institute for Mathematical Sciences, 35a South St., Mayfair, London W1K 2XF, United Kingdom
Email: bollobas@dpmms.cam.ac.uk

Karen Gunderson
Affiliation: Department of Mathematics, University of Manitoba, Winnipeg, Manitoba R3T 2N2, Canada
Email: karen.gunderson@umanitoba.ca

Imre Leader
Affiliation: Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, United Kingdom
Email: I.Leader@dpmms.cam.ac.uk

Mark Walters
Affiliation: School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
Email: m.walters@qmul.ac.uk

DOI: https://doi.org/10.1090/tran/7420
Received by editor(s): April 21, 2015
Received by editor(s) in revised form: March 25, 2017
Published electronically: June 20, 2018
Additional Notes: The first and second author are partially supported by NSF grant DMS 1301614 and MULTIPLEX no. 317532.
While the research took place, the third author was employed by the Heilbronn Institute for Mathematical Research, University of Bristol, Bristol, United Kingdom
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society