Spectrum of sparse random graphs and related problems희소 랜덤 그래프의 스펙트럼과 관련 문제들

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 132
  • Download : 0
DC FieldValueLanguage
dc.contributor.advisorJung, Paul-
dc.contributor.advisor폴정-
dc.contributor.authorLee, Jaehun-
dc.date.accessioned2023-06-22T19:33:53Z-
dc.date.available2023-06-22T19:33:53Z-
dc.date.issued2022-
dc.identifier.urihttp://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=1007829&flag=dissertationen_US
dc.identifier.urihttp://hdl.handle.net/10203/308573-
dc.description학위논문(박사) - 한국과학기술원 : 수리과학과, 2022.8,[iv, 136 p. :]-
dc.description.abstractWe consider the normalized adjacency matrix $H$ of Erd\H{o}s-R\'{e}nyi graphs $\mathcal{G}(N,p)$ and assume $N^{\epsilon} < pN < N^{1-\epsilon}$. When $pN < N^{1/3-\epsilon}$, it was recently shown that leading order fluctuations of extreme eigenvalues of $H$ are given by a single random variable associated with the total degree of the graph (Huang-Landon-Yau, 2020-
dc.description.abstractHe-Knowles, 2021). We construct a sequence of random correction terms to capture higher (sub-leading) order fluctuations of extreme eigenvalues of $H$. Using these random correction terms, we prove a local law up to a (randomly) shifted edge and recover the rigidity of extreme eigenvalues under some random corrections in the sparse regime $pN > N^{\epsilon}$. In another direction, we investigate the noise sensitivity of the top eigenvector of $H$. Let $v$ be the top eigenvector of $H$. We resample $k$ uniformly randomly chosen entries of the matrix and obtain another realization of the random matrix with top eigenvector $v^{[k]}$. Building on recent results on sparse random matrices and a noise sensitivity analysis previously developed for Wigner matrices, we prove that, if $pN\geq N^{2/9}$, with high probability, when $k \ll N^{5/3}$, the vectors $v$ and $v^{[k]}$ are almost collinear and, on the contrary, when $k\gg N^{5/3}$, the vectors $v$ and $v^{[k]}$ are almost orthogonal.-
dc.languageeng-
dc.publisher한국과학기술원-
dc.subjectsparse random graphs▼aErdos-Renyi graph▼arandom matrix theory▼anoise sensitivity-
dc.subject희소 랜덤 그래프▼a에르되시-레니 그래프▼a랜덤 행렬 이론▼a노이즈 민감도-
dc.titleSpectrum of sparse random graphs and related problems-
dc.title.alternative희소 랜덤 그래프의 스펙트럼과 관련 문제들-
dc.typeThesis(Ph.D)-
dc.identifier.CNRN325007-
dc.description.department한국과학기술원 :수리과학과,-
dc.contributor.alternativeauthor이재훈-
Appears in Collection
MA-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0