Sub-tree counts on hyperbolic random geometric graphs. (13th December 2022)

• Record Type: Journal Article
• Authors: Owada, Takashi; Yogeshwaran, D.
• Is Part Of: Advances in applied probability. Volume 54:Number 4(2022)
• Page Start: 1032
• Page End: 1069
• Publication Date: 2022-12-13
• Subjects: Hyperbolic spaces -- random geometric graphs -- Poisson point process -- sub-tree counts -- central limit theorem -- Malliavin–Stein method; 60F05 -- 60D05 -- 05C80 -- 51M10; Probabilities -- Periodicals; Stochastic models -- Periodicals; Electronic journals; Periodicals; 519.2
• DOI: 10.1017/apr.2022.1
• Languages: English
• ISSNs: 0001-8678

Abstract

Abstract: The hyperbolic random geometric graph was introduced by Krioukov et al. ( Phys. Rev. E 82, 2010). Among many equivalent models for the hyperbolic space, we study the d -dimensional Poincaré ball ( $d\ge 2$ ), with a general connectivity radius. While many phase transitions are known for the expectation asymptotics of certain subgraph counts, very little is known about the second-order results. Two of the distinguishing characteristics of geometric graphs on the hyperbolic space are the presence of tree-like hierarchical structures and the power-law behaviour of the degree distribution. We aim to reveal such characteristics in detail by investigating the behaviour of sub-tree counts. We show multiple phase transitions for expectation and variance in the resulting hyperbolic geometric graph. In particular, the expectation and variance of the sub-tree counts exhibit an intricate dependence on the degree sequence of the tree under consideration. Additionally, unlike the thermodynamic regime of the Euclidean random geometric graph, the expectation and variance may exhibit different growth rates, which is indicative of power-law behaviour. Finally, we also prove a normal approximation for sub-tree counts using the Malliavin–Stein method of Last et al. ( Prob. Theory Relat. Fields 165, 2016), along with the Palm calculus for Poisson point processes.