3
$\begingroup$

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<n+1$ 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?

$\endgroup$
2
  • $\begingroup$ 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$? $\endgroup$ Jul 26, 2019 at 12:07
  • $\begingroup$ 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},..$ $\endgroup$
    – pgiacome
    Jul 26, 2019 at 13:27

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ thanks this was precisely what I was asking. $\endgroup$
    – pgiacome
    Jul 26, 2019 at 13:27
  • $\begingroup$ @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. $\endgroup$ Jul 26, 2019 at 15:48
  • $\begingroup$ @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. $\endgroup$
    – pgiacome
    Jul 26, 2019 at 18:36
  • $\begingroup$ incidentally, interlacing plays important role in the recent mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf $\endgroup$ Jul 26, 2019 at 22:00
  • $\begingroup$ @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. $\endgroup$ Jul 26, 2019 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.