Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erd\H{o}s-R\'enyi random graphs

Abstract: We consider an inhomogeneous ErdH{o}s-R'enyi random graph

G_{N}

with vertex set

[N] = 1, d o t s, N

for which the pair of vertices

i, j i n [N]

,

i e q j

, is connected by an edge with probability

r_{N} (f r a c i N, f r a c j N)

, independently of other pairs of vertices. Here,

r_{N} c o l o n, [0, 1]^{2} o (0, 1)

is a symmetric function that plays the role of a reference graphon. Let

l a m b d a_{N}

be the maximal eigenvalue of the Laplacian matrix of

G_{N}

. We show that if

l i m_{N o i n f t y} | r_{N} - r |_{i} n f t y = 0

for some limiting graphon

r c o l o n, [0, 1]^{2} o (0, 1)

, then

l a m b d a_{N} / N

satisfies a downward LDP with rate

and an upward LDP with rate

N

. We identify the associated rate functions

p s i_{r}

and

w i d e h a t {p s i}_{r}

, and derive their basic properties.

This page was built for publication: Large deviation principle for the norm of the Laplacian matrix of inhomogeneous Erd\H{o}s-R\'enyi random graphs