Random geometric graphs and isometries of normed spaces

DOI10.1090/TRAN/7420zbMATH Open1393.05239arXiv1504.05324OpenAlexW2963936032WikidataQ129673251 ScholiaQ129673251MaRDI QIDQ4580360FDOQ4580360

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

Publication date: 15 August 2018

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Convexity
• Title not available (Why is that?)
• Infinite random geometric graphs
• Brownian local minima, random dense countable sets and random equivalence classes
• Infinite Random Geometric Graphs from the Hexagonal Metric

Cited In (3)

• Step-isometries
• The geometry of random walk isomorphism theorems
• Geometric random graphs on circles

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)