# Eigenvalues of random graphs

At time $$t=0$$, let $$G_n(V,E)$$ be a graph with $$n$$ vertices and $$m < n$$ edges. Then there exists a unique symmetric adjacency matrix $$A_n$$ associated with $$G_n(V,E)$$, defined as follows: $$a_{ij} = 1$$ if there exists an edge between the vertex $$i$$ and vertex $$j$$, zero otherwise.

The spectrum, i.e., the set of eigenvalues of $$A_n$$ is not empty.

Then we consider at time $$t=1$$ a new vertex is added to the graph $$G_n$$ with probability $$p$$, $$m edges connect the new vertex to the previous ones.

So the new adjacency matrix $$A_{n+1}$$ associated with the new graph $$G_{n+1}$$ has a new symmetric column/row where at least one entry is $$1$$ and in case all are ones.

Let us consider the sequence of matrices $$G_n$$ as $$n$$ tends to infinity. Can we say something on the associated sequence of eigenvalues?

Is there any reference on the subject?

• You start with fixed $n$ and then want $n\to\infty$. It is strange. Am I correct to guess that actually you want $n$ fixed and then to make a sequence $G_{n+t}$ for $t=1,2,\ldots$ and ask about $t\to\infty$? – Brendan McKay Jul 26 '19 at 12:07
• yes your guess is correct in fact you start with a graph of n vertex at $t=0$ at $t=1$ you add a new vertex so the graph $G_n$ becomes $G_{n+1}$ and so on so my question is on the eigenvalues of the associated adjacency matrix related to the sequence $G_n,G_{n+1},G_{n+2},..$ – pgiacome Jul 26 '19 at 13:27

The eigenvalues of $$A_k$$ interlace the eigenvalues of $$A_{k+t}$$, see e.g. Corollary 2.2 of a classical “Interlacing eigenvalues and graphs” by W.Haemers, which however mostly deals with various “regular” cases.