Skip to content
DraconiticResearch
Search Sources API
190,860 studies31 sourcesUpdated 21 min ago
PreprintCC BY 4.0arXiv

Delocalized region of bipartite Erdős-Rényi graphs

  • Johannes Alt
  • Serafina Wald
Open at sourcePDFDOICite

Abstract

We consider bipartite Erdős-Rényi graphs 𝔾(n, p, d/√(np)) with two parts of sizes n and p, respectively, and edge probability d/√(pn). We show that for d > b* log (n+p) all eigenvectors of its adjacency matrix, with eigenvalues away from zero, are delocalized with high probability. The threshold b* is an explicit function of the size ratio n/p and optimal for eigenvector delocalization near the spectral edges. Our results extend to bulk eigenvectors down to the optimal threshold d≥ 𝒟√(log (n+p)) for a constant 𝒟 ≥ 1. In the supercritical scale d ≫ log (n+p) we show that all eigenvectors are delocalized. Our results also hold for sparse rectangular random matrices with independent entries.

Related

  1. The spectral edge of sparse directed Erdös-Rényi graphs
    Simon Coste, Yizhe Zhu
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsProbabilityarXiv
  2. Bernoulli flow for Erdős-Rényi graphs
    Joscha Henheik, Antti Knowles
    arXivPreprintCC BY 4.0Full textMathematical physicsProbabilityarXiv
  3. Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
    Dávid Ferenczi, Alexander Grigoriev
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsProbabilityarXiv
  4. Non-Adaptive Learning of Sparse Erdős--Rényi Graphs via Affine Splitting
    Hoang Ta
    arXivPreprintCC BY 4.0Full textProbabilityarXiv
  5. Majority Dynamics on Resampled Sparse Erdős--Rényi Graphs: Gaussian Winner Selection in Collaborative Agent Networks
    Ioana Dumitriu, Muchen Ju, Hai-Xiao Wang
    arXivPreprintCC BY-NC-ND 4.0Full textCombinatorics & discrete mathematicsProbabilityarXiv

Cite

BibTeXRIS
BibTeX
@misc{alt2026delocalized,
  title = {{Delocalized region of bipartite Erdős-Rényi graphs}},
  author = {Johannes Alt and Serafina Wald},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.42088},
  eprint = {2610.42088},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.42088},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Delocalized region of bipartite Erdős-Rényi graphs
AU  - Johannes Alt
AU  - Serafina Wald
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.42088
UR  - https://arxiv.org/abs/2610.42088
AB  - We consider bipartite Erdős-Rényi graphs 𝔾(n, p, d/√(np)) with two parts of sizes n and p, respectively, and edge probability d/√(pn). We show that for d > b_* log (n+p) all eigenvectors of its adjacency matrix, with eigenvalues away from zero, are delocalized with high probability. The threshold b_* is an explicit function of the size ratio n/p and optimal for eigenvector delocalization near the spectral edges. Our results extend to bulk eigenvectors down to the optimal threshold d≥ 𝒟√(log (n+p)) for a constant 𝒟 ≥ 1. In the supercritical scale d ≫ log (n+p) we show that all eigenvectors are delocalized. Our results also hold for sparse rectangular random matrices with independent entries.
ER  -