On the Second Eigenvalue of Random Bipartite Biregular Graphs

Yizhe Zhu ()
Additional contact information
Yizhe Zhu: University of California Irvine

Journal of Theoretical Probability, 2023, vol. 36, issue 2, 1269-1303

Abstract: Abstract We consider the spectral gap of a uniformly chosen random $$(d_1,d_2)$$ ( d 1 , d 2 ) -biregular bipartite graph G with $$|V_1|=n, |V_2|=m$$ | V 1 | = n , | V 2 | = m , where $$d_1,d_2$$ d 1 , d 2 could possibly grow with n and m. Let A be the adjacency matrix of G. Under the assumption that $$d_1\ge d_2$$ d 1 ≥ d 2 and $$d_2=O(n^{2/3}),$$ d 2 = O ( n 2 / 3 ) , we show that $$\lambda _2(A)=O(\sqrt{d_1})$$ λ 2 ( A ) = O ( d 1 ) with high probability. As a corollary, combining the results from (Tikhomirov and Yousse in Ann Probab 47(1):362–419, 2019), we show that the second singular value of a uniform random d-regular digraph is $$O(\sqrt{d})$$ O ( d ) for $$1\le d\le n/2$$ 1 ≤ d ≤ n / 2 with high probability. Assuming $$d_2$$ d 2 is fixed and $$d_1=O(n^2)$$ d 1 = O ( n 2 ) , we further prove that for a random $$(d_1,d_2)$$ ( d 1 , d 2 ) -biregular bipartite graph, $$|\lambda _i^2(A)-d_1|=O(\sqrt{d_1})$$ | λ i 2 ( A ) - d 1 | = O ( d 1 ) for all $$2\le i\le n+m-1$$ 2 ≤ i ≤ n + m - 1 with high probability. The proofs of the two results are based on the size biased coupling method introduced in Cook et al. (Ann Probab 46(1):72–125, 2018) for random d-regular graphs and several new switching operations we define for random bipartite biregular graphs.

Keywords: Random bipartite biregular graph; Spectral gap; Switching; Size biased coupling; Primary 60C05; 60B20; Secondary 05C50 (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10959-022-01190-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jotpro:v:36:y:2023:i:2:d:10.1007_s10959-022-01190-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10959

DOI: 10.1007/s10959-022-01190-0

Access Statistics for this article

Journal of Theoretical Probability is currently edited by Andrea Monica

More articles in Journal of Theoretical Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().