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?

Improve this question
$\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$
    – Brendan McKay
    Commented 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$
    – Piero Giacomelli
    Commented Jul 26, 2019 at 13:27

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ thanks this was precisely what I was asking. $\endgroup$
    – Piero Giacomelli
    Commented 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$
    – Brendan McKay
    Commented 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$
    – Piero Giacomelli
    Commented Jul 26, 2019 at 18:36
  • $\begingroup$ incidentally, interlacing plays important role in the recent mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf $\endgroup$
    – Dima Pasechnik
    Commented 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$
    – Dima Pasechnik
    Commented Jul 26, 2019 at 22:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .