Empirical Distributions of Laplacian Matrices of Large Dilute Random Graphs

Tiefeng Jiang

doi:10.1142/S2010326312500049

Empirical Distributions of Laplacian Matrices of Large Dilute Random Graphs

Tiefeng Jiang

Statistics (Twin Cities)

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

We study the spectral properties of the Laplacian matrices and the normalized Laplacian matrices of the Erdös-Rényi random graph G(n, p_n) for large n. Although the graph is simple, we discover some interesting behaviors of the two Laplacian matrices. In fact, under the dilute case, that is, p_n (0, 1) and np_n → ∞, we prove that the empirical distribution of the eigenvalues of the Laplacian matrix converges to a deterministic distribution, which is the free convolution of the semi-circle law and N(0, 1). However, for its normalized version, we prove that the empirical distribution converges to the semi-circle law.

Original language	English (US)
Article number	1250004
Journal	Random Matrices: Theory and Application
Volume	1
Issue number	3
DOIs	https://doi.org/10.1142/S2010326312500049
State	Published - Jul 1 2012

Bibliographical note

Funding Information:
The author thanks Dr. Xue Ding for very helpful discussions on the Theorem 1.1. This research was supported in part by NSF #DMS-0449365.

Publisher Copyright:
© 2012 World Scientific Publishing Company.

Keywords

Laplacian matrix
Random matrix
dilute graph
free convolution
normalized Laplacian matrix
random graph
semi-circle law
spectral distribution

Access

10.1142/S2010326312500049

OpenUrl availability

Full text

Cite this

@article{ca67cb8e00ca4e799d4944098a3acda6,

title = "Empirical Distributions of Laplacian Matrices of Large Dilute Random Graphs",

abstract = "We study the spectral properties of the Laplacian matrices and the normalized Laplacian matrices of the Erd{\"o}s-R{\'e}nyi random graph G(n, pn) for large n. Although the graph is simple, we discover some interesting behaviors of the two Laplacian matrices. In fact, under the dilute case, that is, pn (0, 1) and npn → ∞, we prove that the empirical distribution of the eigenvalues of the Laplacian matrix converges to a deterministic distribution, which is the free convolution of the semi-circle law and N(0, 1). However, for its normalized version, we prove that the empirical distribution converges to the semi-circle law.",

keywords = "Laplacian matrix, Random matrix, dilute graph, free convolution, normalized Laplacian matrix, random graph, semi-circle law, spectral distribution",

author = "Tiefeng Jiang",

note = "Funding Information: The author thanks Dr. Xue Ding for very helpful discussions on the Theorem 1.1. This research was supported in part by NSF #DMS-0449365. Publisher Copyright: {\textcopyright} 2012 World Scientific Publishing Company.",

year = "2012",

month = jul,

day = "1",

doi = "10.1142/S2010326312500049",

language = "English (US)",

volume = "1",

journal = "Random Matrices: Theory and Application",

issn = "2010-3263",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "3",

}

TY - JOUR

T1 - Empirical Distributions of Laplacian Matrices of Large Dilute Random Graphs

AU - Jiang, Tiefeng

N1 - Funding Information: The author thanks Dr. Xue Ding for very helpful discussions on the Theorem 1.1. This research was supported in part by NSF #DMS-0449365. Publisher Copyright: © 2012 World Scientific Publishing Company.

PY - 2012/7/1

Y1 - 2012/7/1

N2 - We study the spectral properties of the Laplacian matrices and the normalized Laplacian matrices of the Erdös-Rényi random graph G(n, pn) for large n. Although the graph is simple, we discover some interesting behaviors of the two Laplacian matrices. In fact, under the dilute case, that is, pn (0, 1) and npn → ∞, we prove that the empirical distribution of the eigenvalues of the Laplacian matrix converges to a deterministic distribution, which is the free convolution of the semi-circle law and N(0, 1). However, for its normalized version, we prove that the empirical distribution converges to the semi-circle law.

AB - We study the spectral properties of the Laplacian matrices and the normalized Laplacian matrices of the Erdös-Rényi random graph G(n, pn) for large n. Although the graph is simple, we discover some interesting behaviors of the two Laplacian matrices. In fact, under the dilute case, that is, pn (0, 1) and npn → ∞, we prove that the empirical distribution of the eigenvalues of the Laplacian matrix converges to a deterministic distribution, which is the free convolution of the semi-circle law and N(0, 1). However, for its normalized version, we prove that the empirical distribution converges to the semi-circle law.

KW - Laplacian matrix

KW - Random matrix

KW - dilute graph

KW - free convolution

KW - normalized Laplacian matrix

KW - random graph

KW - semi-circle law

KW - spectral distribution

UR - http://www.scopus.com/inward/record.url?scp=84989283821&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84989283821&partnerID=8YFLogxK

U2 - 10.1142/S2010326312500049

DO - 10.1142/S2010326312500049

M3 - Article

AN - SCOPUS:84989283821

SN - 2010-3263

VL - 1

JO - Random Matrices: Theory and Application

JF - Random Matrices: Theory and Application

IS - 3

M1 - 1250004

ER -

Empirical Distributions of Laplacian Matrices of Large Dilute Random Graphs

Abstract

Bibliographical note

Keywords

Access

OpenUrl availability

Other files and links

Fingerprint

Cite this