Infinite random geometric graphs

DOI10.1007/S00026-011-0111-8zbMATH Open1235.05101arXiv0908.2590OpenAlexW2163232127MaRDI QIDQ659653FDOQ659653

Authors: Anthony Bonato, Jeannette Janssen 

Publication date: 24 January 2012

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: We introduce a new class of countably infinite random geometric graphs, whose vertices are points in a metric space, and vertices are adjacent independently with probability p if the metric distance between the vertices is below a given threshold. If the vertex set is a countable dense set in R^n equipped with the metric derived from the L_{infty}-norm, then it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR_n, is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR_n. In contrast, we show that infinite random geometric graphs in R^2 with the Euclidean metric are not necessarily isomorphic.

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

Recommendations

• Infinite random graphs and properties of metrics
• Infinite random geometric graphs from the hexagonal metric
• Geometric random graphs on circles
• Geometric random graphs and Rado sets in sequence spaces
• Random geometric graphs and isometries of normed spaces

zbMATH Keywords

metric spacesisometryrandom graphsgeometric graphsadjacency property

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Planar graphs; geometric and topological aspects of graph theory (05C10) Infinite graphs (05C63) Structural characterization of families of graphs (05C75) Isometric theory of Banach spaces (46B04) Metric spaces, metrizability (54E35)

Cites Work

• Random Geometric Graphs
• \(E_{11}\) and M theory
• Title not available (Why is that?)
• Complex graphs and networks
• The random graph
• Asymmetric graphs
• A Geometric Preferential Attachment Model of Networks
• The geometric protean model for on-line social networks
• On random points in the unit disk
• A course on the web graph
• Highly connected random geometric graphs
• Monotone properties of random geometric graphs have sharp thresholds
• Isomorphism and embedding problems for infinite limits of scale-free graphs
• A spatial web graph model with local influence regions
• Line-of-Sight Networks
• Infinite Limits and Adjacency Properties of a Generalized Copying Model

Cited In (8)

• Random geometric graphs and isometries of normed spaces
• Geometric random graphs and Rado sets of continuous functions
• Generating infinite random graphs
• Step-isometries
• Infinite random graphs and properties of metrics
• Infinite random geometric graphs from the hexagonal metric
• Geometric random graphs on circles
• Geometric random graphs and Rado sets in sequence spaces

This page was built for publication: Infinite random geometric graphs

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