# 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

## 1 Answer

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.

There are lots of references on interlacing and graphs to check for what you might need. This one lists some.

Incidentally, interlacing plays important role in the recent proof of Sensitivity Conjecture by Huang.

• thanks this was precisely what I was asking. – pgiacome Jul 26 '19 at 13:27
• @pjicome Given your answer to my comment above, interlacing will not be of much use I fear. It is a very weak property for the eigenvalues of very large graph to be interlaced by those of a small subgraph. The main useful observation is that the largest eigenvalue increases and the smallest decreases. – Brendan McKay Jul 26 '19 at 15:48
• @dpasechick I need a general property because I would like to study not a general random graph but I am interested in a particular graph a generalization of the the so called apollonian network sciencedirect.com/science/article/pii/S0378437105004450 in this case very time we add a new vertex the corresponding matrices become the previous one plus an extra column where we have a fixed number of 1s. – pgiacome Jul 26 '19 at 18:36
• incidentally, interlacing plays important role in the recent mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf – Dima Pasechnik Jul 26 '19 at 22:00
• @BrendanMcKay there an insanely clever trick replaces some entries 1 in the adjacency matrix on n-dimensional hypercube with -1s, to obtain a matrix proportional to an involuntary one. So the eigenvalues are all the same in absolute value, and one can say more about eigenvalues of principal submatrices. – Dima Pasechnik Jul 26 '19 at 22:05