Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdős-Rényi random graphs

2023/07/05 by Hazra, Rajat Subhra, Hollander, Frank den, Markering, Maarten
#FOS: Mathematics #Functional Analysis (math.FA) #Probability (math.PR)

paper · doi:10.48550/arxiv.2307.02324

Abstract

We consider an inhomogeneous Erdős-Rényi random graph G_N with vertex set [N] = \1,…,N\ for which the pair of vertices i,j ∈ [N], i≠ j, is connected by an edge with probability r_N(\tfraciN,\tfracjN), independently of other pairs of vertices. Here, r_N\colon [0,1]² → (0,1) is a symmetric function that plays the role of a reference graphon. Let λ_N be the maximal eigenvalue of the Laplacian matrix of G_N. We show that if lim_N→∞ ‖r_N-r‖_∞ = 0 for some limiting graphon r\colon [0,1]² → (0,1), then λ_N/N satisfies a downward LDP with rate \binomN2 and an upward LDP with rate N. We identify the associated rate functions ψ_r and \widehatψ_r, and derive their basic properties.

Related

• Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs
• Spectra of Adjacency and Laplacian Matrices of Inhomogeneous Erdős-Rényi Random Graphs
• A large deviation principle for the Erdős-Rényi uniform random graph
• Large deviations of the empirical spectral measure of supercritical sparse Wigner matrices
• A sample-path large deviation principle for dynamic Erdős-Rényi random graphs