Large deviation principle for the maximal eigenvalue of inhomogeneous Erdős-Rényi random graphs

2020/08/19 by Chakrabarty, Arijit, Hazra, Rajat Subhra, Hollander, Frank den +1
#FOS: Mathematics #FOS: Physical sciences #Mathematical Physics (math-ph) #Probability (math.PR)

paper · doi:10.48550/arxiv.2008.08367

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(\tfraciN,\tfracjN), independently of other pairs of vertices. Here, r\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 adjacency matrix of G_N. It is known that λ_N/N satisfies a large deviation principle as N → ∞. The associated rate function ψ_r is given by a variational formula that involves the rate function I_r of a large deviation principle on graphon space. We analyse this variational formula in order to identify the properties of ψ_r, specially when the reference graphon is of rank 1.

Related

• Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erdős-Rényi random graphs
• A large deviation principle for the Erdős-Rényi uniform random graph
• A sample-path large deviation principle for dynamic Erdős-Rényi random graphs
• Large deviations for the largest eigenvalue of Gaussian networks with constant average degree
• The large deviation principle for the Erdős-Rényi random graph