5
$\begingroup$

Let $G$ be a finite undirected graph. A closed walk in $G$ is a walk from any vertex of $G$ to itself. It is relatively straightforward to show that the total number of closed walks of length $k$ in $G$ is: $$ \lambda_1^k + \lambda_2^k + \cdots + \lambda_n^k,$$ where $\lambda_1,\ldots,\lambda_n$ are the eigenvalues of the adjaceny matrix of $G$, with mutliplicity.

Often this is thought of as a way to count walks using linear algebra, but in principle it is possible to apply this result "in the other direction" and compute the eigenvalues of the adjacency matrix of $G$ by counting closed walks via some other (e.g., direct combinatorial) argument.

For example, it is possible to find the eigenvalues of the adjacency matrix of the hypercube graph this way (see Stanley, "Enumerative Combinatorics," Vol. 1, 2nd Edition, Chapter 4 Exercise 68; see also Number of closed walks on an $n$-cube). Even simpler would be the case of the complete bipartite graph (ibid. Exercise 69). And for the complete graph this is almost trivial.

Question: Are there some other nice examples of (families of) graphs whose adjacency matrix eigenvalues can be computed via combinatorial walk counting? Especially, are there any graphs where this is the only known way to find a formula for the adjacency matrix eigenvalues?

Improve this question
$\endgroup$
4
  • $\begingroup$ I would imagine that you can count the number of closed walks on a k-partite graph too, similar to a bipartite graph. Is there a version for infinite graphs - if so, the Rado graph seems doable too. $\endgroup$
    – Asvin
    Commented Sep 7, 2020 at 22:07
  • $\begingroup$ @Asvin: Perhaps you can make sense of closed walk counting for infinite graphs using some kind of normalization procedure, but naively even for $k=0$ we get $\infty$-many walks. $\endgroup$
    – Sam Hopkins
    Commented Sep 7, 2020 at 23:01
  • $\begingroup$ Alternatively, you could make asymptotic statements: As the number of vertices goes to infinity, the number of closed walks of a random graph approaches something with probability one and so the eigenvalues also approach something with probability one... Of course, I think it isn't too hard to calculate the eigenvalues directly in either of these examples. $\endgroup$
    – Asvin
    Commented Sep 7, 2020 at 23:04
  • 3
    $\begingroup$ Exercises 1.6, 1.7, 1.8, and 1.10 of my book Algebraic Combinatorics, second ed., can be done by combinatorial reasoning, though there are also linear algebraic proofs. $\endgroup$
    – Richard Stanley
    Commented Sep 7, 2020 at 23:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .