Spectrum of the Laplacian on G(n, p) and G(n, M)

Question

A random graph in $G(n, p)$ model is a graph on $n$ vertices in which for each of the $n\choose{2}$ edges we independently flip a coin, then take the edge with probability $p$ or remove it with $1 - p$.

A random graph in $G(n, m)$ model is a graph on $n$ vertices in which a subset of edges of a fixed size $m$ is chosen at random.

We expect $G(n, p)$ and $G(n, m)$ for $m = p {n\choose{2}}$ to look asymptotically the same, because the number of edges in $G(n, p)$ is highly concentrated around the mean.

The (normalized) Laplacian $L$ on a graph is an operator (matrix) which has entries:

$L(v, v) = 1$

$L(v, w) = - \frac{1}{\sqrt{deg(v)deg(w)}}$

where $v \neq w$ are vertices of the the graph.

We are interested in $\lambda_{2}$, that is, the smallest nonzero eigenvalue of $L$. Suppose we know that, for $p = p(n)$ growing sufficiently fast (papers by Chung et al. show that, for example, $p \geq \frac{\log^2 n}{n}$), $\lambda_{2}$ for a random graph in $G(n, p)$ model is close to 1 with high probability (i. e. approaching 1).

Does it follow immediately that also in $G(n, m)$ we have $\lambda_{2} \to 1$ with high probability? It is known in random graph theory that such implications hold for monotone properties (that is, properties which still hold after adding an edge to the graph), however, the second eigenvalue is not monotone (although it is probably "monotone on average", so I expect the statement above is true for $G(n, m)$).

Answer 1

I'm not sure if there's a way to get it directly from the $G(n,p)$ Laplacian results, but I think it's feasible to get there by way of the adjacency matrix and a coupling argument if $m$ is sufficiently large (say at least $n \log^3 n$). I've sketched an argument which should hopefully work below. The key aspect we use is the following lemma.

Lemma: Let $d_n \rightarrow \infty$, and let $G_n$ be a sequence of graphs whose maximum and minimum degree are both $(1+o(1))d_n$. Then $\lambda_2(G_n) \rightarrow 1$ if and only all eigenvalues of the adjacency matrix of $G_n$ but the largest are $o(d_n)$.

This Lemma should be standard (though I don't have a reference), but is not hard to prove: The idea is that $AD^{-1}$ can be written as $\frac{1}{d_n}A(I-(I-\frac{1}{d_n}D))^{-1},$ and by assumption $I-\frac{1}{d_n}D$ has small spectral norm.

Let $m$ and $p$ be related by $m=p\binom{n}{2}$, and let $H_1$ be a random graph from $G(n,p)$ conditioned on having between $m$ and $m+\sqrt{m}$ edges. Let $H_2$ be a random subgraph of $H_1$ having $m$ edges (note that $H_2$ has uniform distribution on $G(n,m)$). Since $m$ is sufficiently large, $H_2$ satisfies the hypothesis of the lemma. So it suffices to bound the second eigenvalue of $H_2$'s adjacency matrix.

By the results of Chung et al. along with the lemma, the second largest eigenvalue of $H_1$ is $o(m/n)$ (since we're conditioning on an event of positive probability, the results of Chung still hold even after conditioning). We're therefore done if we show that the spectral norm of $H_1-H_2$ is also almost surely $o(m/n)$.

For any $1 \leq k \leq \sqrt{m}$, the distribution of $H_1-H_2$ conditioned on $k$ edges being removed is the same as that of $G(n,k)$. We can bound the spectral norm of $G(n,k)$ by its maximum degree (whose distribution should also be well-known, though again I don't have a reference), at which point we may as well take $k=\sqrt{m}$. Using the negative correlation between edges in $G(n,k)$, we see that the probability a vertex has degree at least $d$ is at most $$n \binom{n}{d} \left(\frac{2k}{n^2}\right)^{d} \leq n \left(\frac{2e\sqrt{m}}{dn}\right)^d$$ which tends to $0$ for $d=\frac{m}{n \log n}$ (recall that by assumption $d \geq \log^2 n$).

Answer 2

You might find this paper and the references therein useful:

Amin Coja-Oghlan, On the Laplacian eigenvalues of $G_{n,p}$, Combin. Probab. Comput., 16 (2007). MR 2008j:05212.

They discuss the classical model as well as Chung and Lu's model which is quite interesting.