4
$\begingroup$

Given a graph $G(V,E)$ and a partition $\{V_1,\dots V_n\}$ of the nodes set $V$, the adjacency and Laplacian spectra of the quotient graph $Q(G)$ interlaces the adjacent and the Laplacian spectra of the parent graph $G$. Besides, if the partition in equitable the interlacing is tight

This is a well known result.

Now, suppose I have a directed graph $D(V,E)$ and a partition $\{V_1,\dots V_n\}$ of the nodes set. Suppose also that the quotient graph $Q(D)$ is undirected. Under what conditions the interlacing and inclusion results for the adjacency and/or Laplacian spectra are still valid?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ For a directed $8$-cycle the adjacency eigenvalues are complex numbers on the unit circle. Whatever the definition of interlacing should be in this case, it wouldn't allow the eigenvalues $\pm 2$ of an undirected $4$-cycle. $\endgroup$
    – Aaron Meyerowitz
    Sep 28, 2016 at 18:22
  • 1
    $\begingroup$ I know it is not general, I'm asking if there is some result in the literature on the condition under which the interlacing results apply, meaning also that the spectra of the parent graph are real (despite the fact that it is directed) $\endgroup$
    – emcozzo
    Sep 29, 2016 at 8:17

1 Answer 1

Reset to default
1
$\begingroup$

Here are some comments.

  • Perhaps you want to start with the question of conditions on a square $0,1$ matrix which assure that the spectrum is real, since you say that is a precondition for the stronger thing you want to make sense.

  • You probably want to assume the graph is strongly connected and aperiodic ( the directed cycles are not all of length $mk$ for some $m \gt 1.)$

  • Certainly the largest eigenvalue is real and is especially interesting. To avoid the issue of complex eigenvalues, start with the question of when the quotient graph has smaller Peron eigenvalue.

  • The example I gave (which fails the aperiodic requirement I suggest below) also fails this condition. If you consider a matrix where the $i,j$ entry is the probability of moving from vertex $i$ to vertex $j$ then the problem may go away.

  • Undirected multigraphs (with loops) should preserve what you want with the right definition of quotient. Perhaps that is a useful pointer.

  • I strongly suggest looking into the work of Fan Chung.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I really don't want to restrict to 0,1 matrices, since I want to consider Laplacian matrices. I don't understand point 3 $\endgroup$
    – emcozzo
    Oct 3, 2016 at 13:54

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.