Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdős-Rényi random graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912178425036800 |
|---|---|
| author | Hazra, Rajat Subhra Hollander, Frank den Markering, Maarten |
| author_facet | Hazra, Rajat Subhra Hollander, Frank den Markering, Maarten |
| contents | We consider an inhomogeneous Erdős-Rényi random graph $G_N$ with vertex set $[N] = \{1,\dots,N\}$ for which the pair of vertices $i,j \in [N]$, $i\neq j$, is connected by an edge with probability $r_N(\tfrac{i}{N},\tfrac{j}{N})$, independently of other pairs of vertices. Here, $r_N\colon\,[0,1]^2 \to (0,1)$ is a symmetric function that plays the role of a reference graphon. Let $λ_N$ be the maximal eigenvalue of the Laplacian matrix of $G_N$. We show that if $\lim_{N\to\infty} \|r_N-r\|_\infty = 0$ for some limiting graphon $r\colon\,[0,1]^2 \to (0,1)$, then $λ_N/N$ satisfies a downward LDP with rate $\binom{N}{2}$ and an upward LDP with rate $N$. We identify the associated rate functions $ψ_r$ and $\widehatψ_r$, and derive their basic properties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_02324 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdős-Rényi random graphs Hazra, Rajat Subhra Hollander, Frank den Markering, Maarten Probability Functional Analysis We consider an inhomogeneous Erdős-Rényi random graph $G_N$ with vertex set $[N] = \{1,\dots,N\}$ for which the pair of vertices $i,j \in [N]$, $i\neq j$, is connected by an edge with probability $r_N(\tfrac{i}{N},\tfrac{j}{N})$, independently of other pairs of vertices. Here, $r_N\colon\,[0,1]^2 \to (0,1)$ is a symmetric function that plays the role of a reference graphon. Let $λ_N$ be the maximal eigenvalue of the Laplacian matrix of $G_N$. We show that if $\lim_{N\to\infty} \|r_N-r\|_\infty = 0$ for some limiting graphon $r\colon\,[0,1]^2 \to (0,1)$, then $λ_N/N$ satisfies a downward LDP with rate $\binom{N}{2}$ and an upward LDP with rate $N$. We identify the associated rate functions $ψ_r$ and $\widehatψ_r$, and derive their basic properties. |
| title | Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdős-Rényi random graphs |
| topic | Probability Functional Analysis |
| url | https://arxiv.org/abs/2307.02324 |