Infinite random geometric graphs

DOI10.1007/S00026-011-0111-8MaRDI QIDQ659653zbMATH OpenOpenAlexFDO

Authors Anthony Bonato, Jeannette Janssen

Publication date 24 January 2012

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

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

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)

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.

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

Cites work

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

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)