Large deviation principle for the maximal eigenvalue of inhomogeneous Erdos-Renyi random graphs

Abstract

We consider an inhomogeneous Erdos-Renyi random graph G(N) with vertex set [N] = {1, . . . , N} for which the pair of vertices i, j is an element of [N], i not equal j, is connected by an edge with probability r (i/N + j/N), independently of other pairs of vertices. Here, r : [0, 1](2) -> (0, 1) is a symmetric function that plays the role of a reference graphon. Let lambda(N) be the maximal eigenvalue of the adjacency matrix of G(N). It is known that lambda(N)/N satisfies a large deviation principle as N -> infinity. The associated rate function psi(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 psi(r) , specially when the reference graphon is of rank 1.