1. RANDOM GEOMETRIC GRAPHS AND ISOMETRIES OF NORMED SPACES.
- Author
-
BALISTER, PAUL, BOLLOBÁS, BÉLA, GUNDERSON, KAREN, LEADER, IMRE, and WALTERS, MARK
- Subjects
RANDOM variables ,GEOMETRIC analysis ,GRAPH theory ,ISOCHORIC processes ,NORMED rings ,ESTIMATION theory - 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 ℓ
∞ d almost all S are Rado. Our main aim in this paper is to show that ℓ∞ 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 ℓ∞ 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. [ABSTRACT FROM AUTHOR]- Published
- 2018
- Full Text
- View/download PDF