Random geometric graphs and isometries of normed spaces

DOI10.1090/TRAN/7420MaRDI QIDQ4580360zbMATHOpenAlexWikidataFDO

Authors Béla Bollobás, Karen Gunderson, Imre Leader, Mark Walters, Paul Balister

Publication date 15 August 2018

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.05324

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Isometric theory of Banach spaces (46B04)

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 $l_{i}nft{y}^d$ almost all $S$ are Rado. Our main aim in this paper is to show that $l_{i}nft{y}^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_{i}nfty$ 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.

Recommendations

• Geometric random graphs and Rado sets in sequence spaces
• Geometric random graphs and Rado sets of continuous functions
• On the normalized Laplacian spectra of random geometric graphs
• Random graphs, geometry and asymptotic structure
• Geodesics and almost geodesic cycles in random regular graphs
• The geometry of random walk isomorphism theorems
• The Nelson-Erdős-Hadwiger problem and embeddings of random graphs into geometric ones
• Limit theory for isolated and extreme points in hyperbolic random geometric graphs
• On the spectrum of dense random geometric graphs

Cites work

• scientific article; zbMATH DE number 3563703 (Why is no real title available?)
• scientific article; zbMATH DE number 3004170 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1880674 (Why is no real title available?)
• Brownian local minima, random dense countable sets and random equivalence classes
• Convexity. An analytic viewpoint
• Descriptive set theory
• Graph theory
• Infinite random geometric graphs
• Infinite random geometric graphs from the hexagonal metric

Cited in

(8)

• Geometric random graphs and Rado sets of continuous functions
• Step-isometries
• Infinite random graphs and properties of metrics
• Geometric random graphs on circles
• Geometric random graphs and Rado sets in sequence spaces
• Infinite random geometric graphs from the hexagonal metric
• Infinite random geometric graphs
• The geometry of random walk isomorphism theorems

This page was built for publication: Random geometric graphs and isometries of normed spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4580360)