We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=\rho$, and the vertex labels of the second...
Dong Huang, An-Kang Jiao, Shuang-Ping Li et al.· 0 citations
We study testing a random geometric graph with a fixed kernel against an Erd\H{o}s-R\'enyi graph with the same edge density. Under the null hypothesis, the graph has $n$ vertices and independent edges with probability $p$. Under the alternative hypothesis, latent points $X_1,\ldots,X_n$ are independent and uniform on $...
Let $T_n$ be the number of triangles in the Erd\H{o}s-R\'enyi random graph $G(n,p)$ with $n^{-1/2}\ll p\ll1$ and fix $\eta\in(0,1)$. We study the large deviation rate of the lower tail event $T_n\le\eta\mathbb{E}[T_n]$, and the typical structure of $G(n,p)$ conditioned on this event. By earlier work [16,19,21,49], both...
A correspondence between the subgraph-count and automorphism factors in the Fourier expansion and counts of isomorphism triples is uncovered, and the low-degree assumption rules out short cycles, while noise destroys the remaining long cycles.
Xuan Chen, Shuangping Li· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.