Spectrum and local weak convergence of sparse random uniform hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916963090956288 |
|---|---|
| author | Adhikari, Kartick Parui, Samiron |
| author_facet | Adhikari, Kartick Parui, Samiron |
| contents | The notion of local weak convergence, or Benjamini--Schramm convergence, was introduced by Benjamini and Schramm. The local weak limit of sparse Erd\H os--Rényi graphs is the Galton--Watson measure with Poisson offspring almost surely. Recently, Adhikari, Kumar, and Saha showed that the line graph of sparse Linial--Meshulam complexes converges to the $d$-block Galton--Watson measure. We study a unified model: weighted line graphs of sparse $k$-uniform random hypergraphs on $n$ vertices. Let $H(n,k,p)$ be the $k$-uniform random hypergraph where each $k$-subset of $[n]$ is included as a hyperedge independently with probability $p$. For a $k$-uniform hypergraph $H=(V,E)$ and $1\le r\le k-1$, define the $r$-set weighted line graph $G_r(H)=(\mathcal V_r,\mathcal E_r,w_H)$ by $$ \mathcal V_r=\bigl[\tbinom{n}{r}\bigr],\quad \mathcal E_r=\bigl\{\{τ_1,τ_2\}:τ_1,τ_2\in\mathcal V_r,\ \exists e\in E\text{ s.t. }τ_1,τ_2\subset e\bigr\}, $$ with weight $w_H(\{τ_1,τ_2\})=\bigl|\{e\in E:τ_1,τ_2\subset e\}\bigr|$. In particular, $G_1(H_n)$ generalizes Erd\H os--Rényi graphs and $G_{k-1}(H_n)$ is the line graph of the Linial--Meshulam complex. We show that if $\tbinom{n-r}{k-r}\to λ$ as $n\to\infty$, then $G_r(H_n)$ converges locally to the $(\tbinom{k}{r}-1)$-block Galton--Watson measure with $\operatorname{Poisson}(λ)$ offspring almost surely. As a consequence, we obtain the limiting spectral distribution of the adjacency matrices of $G_r(H_n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_05102 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spectrum and local weak convergence of sparse random uniform hypergraphs Adhikari, Kartick Parui, Samiron Combinatorics Probability Hypergraphs, Random graphs(graph-theoretic aspects), Weak limit, Random matrices (probabilistic aspects), Convergence of probability measures The notion of local weak convergence, or Benjamini--Schramm convergence, was introduced by Benjamini and Schramm. The local weak limit of sparse Erd\H os--Rényi graphs is the Galton--Watson measure with Poisson offspring almost surely. Recently, Adhikari, Kumar, and Saha showed that the line graph of sparse Linial--Meshulam complexes converges to the $d$-block Galton--Watson measure. We study a unified model: weighted line graphs of sparse $k$-uniform random hypergraphs on $n$ vertices. Let $H(n,k,p)$ be the $k$-uniform random hypergraph where each $k$-subset of $[n]$ is included as a hyperedge independently with probability $p$. For a $k$-uniform hypergraph $H=(V,E)$ and $1\le r\le k-1$, define the $r$-set weighted line graph $G_r(H)=(\mathcal V_r,\mathcal E_r,w_H)$ by $$ \mathcal V_r=\bigl[\tbinom{n}{r}\bigr],\quad \mathcal E_r=\bigl\{\{τ_1,τ_2\}:τ_1,τ_2\in\mathcal V_r,\ \exists e\in E\text{ s.t. }τ_1,τ_2\subset e\bigr\}, $$ with weight $w_H(\{τ_1,τ_2\})=\bigl|\{e\in E:τ_1,τ_2\subset e\}\bigr|$. In particular, $G_1(H_n)$ generalizes Erd\H os--Rényi graphs and $G_{k-1}(H_n)$ is the line graph of the Linial--Meshulam complex. We show that if $\tbinom{n-r}{k-r}\to λ$ as $n\to\infty$, then $G_r(H_n)$ converges locally to the $(\tbinom{k}{r}-1)$-block Galton--Watson measure with $\operatorname{Poisson}(λ)$ offspring almost surely. As a consequence, we obtain the limiting spectral distribution of the adjacency matrices of $G_r(H_n)$. |
| title | Spectrum and local weak convergence of sparse random uniform hypergraphs |
| topic | Combinatorics Probability Hypergraphs, Random graphs(graph-theoretic aspects), Weak limit, Random matrices (probabilistic aspects), Convergence of probability measures |
| url | https://arxiv.org/abs/2509.05102 |