Metraipolis › archive › dc_afa02bada182

Band Random Graphs: Connectivity, Geometry, and Transport — arXiv:2610.42107

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.42107
License (as archived): CC0-1.0
Archived: 2026-11-02T07:58:20.228Z
SHA-256 of the archived text: a27b10413798e668135a046adf533586b0968536c6eba638fea0a8933ba8b16b
Stable URL of this page: https://metraipolis.com/documento/dc_afa02bada182

How to cite

Band Random Graphs: Connectivity, Geometry, and Transport — arXiv:2610.42107 — arXiv (en), https://arxiv.org/abs/2610.42107 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_afa02bada182 (Metraipolis archive dc_afa02bada182, sha256 a27b10413798e668135a046adf533586b0968536c6eba638fea0a8933ba8b16b)

BibTeX

@misc{dcafa02bada182,
  title = {Band Random Graphs: Connectivity, Geometry, and Transport — arXiv:2610.42107},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.42107},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_afa02bada182; sha256 a27b10413798e668135a046adf533586b0968536c6eba638fea0a8933ba8b16b},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42107. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Let $G(n,p,m)$ be the random subgraph of the cycle power $C_n^m$ obtained by retaining each edge independently with probability $p$. We study connectivity, component geometry, and random walks throughout the regime $\log n\ll m<n/2$. We prove that $p\sim(\log n)/(2m)$ is a sharp threshold for connectivity. If $n(1-p)^{2m}\to\lambda\in(0,\infty)$, then the number of isolated vertices converges to $\mathrm{Poisson}(\lambda)$, and with high probability every other vertex lies in a single component $C_1$. In particular, the connectivity probability converges to $e^{-\lambda}$. The component $C_1$ contains a cyclic chain of connected sets occupying all but an $o(1)$ fraction of each consecutive block of length $\asymp m$, with $\Theta(m\log n)$ edges between consecutive sets. Its diameter has order $n/m+\log n/\log\log n$ with high probability. For every fixed $c>1$, uniformly over $p\geq c\log n/(2m)$, the lazy-walk spectral gap is asymptotic in probability to that of $C_n^m$. In the same range, the mean hitting time of simple random walk satisfies, uniformly over distinct $x,y$, $$ H_G(x,y)=\frac{2|E(G)|}{d_G(y)} +\frac{r_{xy}(n-r_{xy})}{\kappa_m} +o_{\mathrm{Prob}}\left(n+\frac{n^2}{m^2}\right), $$ where $r_{xy}$ is cyclic distance between vertices $x$ and $y$, $d_G(z)$ is the degree of vertex $z$ and $\kappa_m=(m+1)(2m+1)/6$. Thus, for this random graph model, connectivity has the Erdős--Rényi asymptotics with $2m$ possible neighbours, while distances, relaxation, and hitting times retain the geometry of the underlying cycle.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.PR, nuovi lavori del giorno).
Categorie arXiv: Probability (math.PR) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2610.42107 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:42:15.679Z dalla pagina https://arxiv.org/list/math.PR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).