Random geometric graphs and isometries of normed spaces
HTML articles powered by AMS MathViewer
- by Paul Balister, Béla Bollobás, Karen Gunderson, Imre Leader and Mark Walters PDF
- Trans. Amer. Math. Soc. 370 (2018), 7361-7389 Request permission
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
- Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290, DOI 10.1007/978-1-4612-0619-4
- Anthony Bonato and Jeannette Janssen, Infinite random geometric graphs, Ann. Comb. 15 (2011), no. 4, 597–617. MR 2854782, DOI 10.1007/s00026-011-0111-8
- Anthony Bonato and Jeannette Janssen, Infinite random geometric graphs from the hexagonal metric, Combinatorial algorithms, Lecture Notes in Comput. Sci., vol. 7643, Springer, Heidelberg, 2012, pp. 6–19. MR 3056370, DOI 10.1007/978-3-642-35926-2_{2}
- A. Bonato and J. Janssen. Properties of metrics and infinite geometric graphs. ArXiv e-prints, Oct. 2013.
- P. L. Clark. Geometry of numbers with applications to number theory, http://math.uga.edu/~pete/geometryofnumbers.pdf.
- Reinhard Diestel, Graph theory, 4th ed., Graduate Texts in Mathematics, vol. 173, Springer, Heidelberg, 2010. MR 2744811, DOI 10.1007/978-3-642-14279-6
- Richard J. Fleming and James E. Jamison, Isometries on Banach spaces: function spaces, Chapman & Hall/CRC Monographs and Surveys in Pure and Applied Mathematics, vol. 129, Chapman & Hall/CRC, Boca Raton, FL, 2003. MR 1957004
- Joram Lindenstrauss and Lior Tzafriri, Classical Banach spaces. I, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 92, Springer-Verlag, Berlin-New York, 1977. Sequence spaces. MR 0500056, DOI 10.1007/978-3-642-66557-8
- S. Mazur and S. M. Ulam. Sur les transformations isometriques d’espaces vectoriels normés, C. R. Acad. Sci. Paris, 194 (1932), 946–948.
- Yiannis N. Moschovakis, Descriptive set theory, 2nd ed., Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, RI, 2009. MR 2526093, DOI 10.1090/surv/155
- Barry Simon, Convexity, Cambridge Tracts in Mathematics, vol. 187, Cambridge University Press, Cambridge, 2011. An analytic viewpoint. MR 2814377, DOI 10.1017/CBO9780511910135
- Boris Tsirelson, Brownian local minima, random dense countable sets and random equivalence classes, Electron. J. Probab. 11 (2006), no. 7, 162–198. MR 2217814, DOI 10.1214/EJP.v11-309
Additional Information
- Paul Balister
- Affiliation: Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee
- MR Author ID: 340031
- 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
- MR Author ID: 866638
- Email: karen.gunderson@umanitoba.ca
- Imre Leader
- Affiliation: Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, United Kingdom
- MR Author ID: 111480
- Email: I.Leader@dpmms.cam.ac.uk
- Mark Walters
- Affiliation: School of Mathematical Sciences, Queen Mary University of London, London E1 4NS, United Kingdom
- MR Author ID: 660251
- Email: m.walters@qmul.ac.uk
- 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 - © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 370 (2018), 7361-7389
- MSC (2010): Primary 05C63, 05C80, 46B04
- DOI: https://doi.org/10.1090/tran/7420
- MathSciNet review: 3841851