4
$\begingroup$

Let $\Gamma$ be a graph. Write $A$ for its adjacency matrix. It is trivial to show that $\mathrm{Tr} A^k$ equals the number of closed walks of length k, that is, the number of $k$-step walks that return to where they started.

Suppose that we show that $\Gamma$ has few closed paths of length $\leq k$. (A path is a walk without repeated vertices; obviously we are allowing (and requiring) the origin vertex to be the ending vertex.) Can we prove an upper bound on $\mathrm{Tr} A^k$ as a result? If not, can we prove something else about the spectrum of $A$, possibly with additional conditions? (We may, for instance, assume that the degree of $\Gamma$ is very small compared to its number of vertices.)

The same questions can be posed if we show that $\Gamma$ has few closed trails of length $\leq k$. A trail is a walk without repeated edges.

$\endgroup$
5
  • 1
    $\begingroup$ Since a closed walk can be broken down to a number of closed paths (for instance a closed walk of length 6 can be 2 closed paths of length 3), don't you get an upper bound for number of walks from the number of paths? $\endgroup$ Jun 22 '20 at 7:54
  • $\begingroup$ That would be the naïve expectation, but I don't see how that happens. $\endgroup$ Jun 22 '20 at 8:01
  • 1
    $\begingroup$ But then 6 can be broken in a finite number of ways $6=4+1+1=3+3=2+2+2=...$ and each decomposition can be bounded by $N^a$ where $N$ is the number of paths at most $6$ and $a$ is the number of summands, can't we get at least some function of $N$ as upper bound? $\endgroup$ Jun 22 '20 at 8:13
  • $\begingroup$ I'm not sure of quite what you have in mind. $\endgroup$ Jun 22 '20 at 11:44
  • 1
    $\begingroup$ Did you try the decomposition into Lyndon words used for understanding the graph zeta function. See for example the article "A Combinatorial Proof of Bass's Evaluations of the Ihara-Selberg Zeta Function for Graphs" by Foata and Zeilberger ams.org/journals/tran/1999-351-06/S0002-9947-99-02234-5 $\endgroup$ Jun 22 '20 at 13:31
4
$\begingroup$

I would put this as a comment but don't have enough (any) reputation...

Closed paths of length $\leq k$ show up when you take the trace of the alternating $k$th power of $A$, which is also equal to $\sum_{ i_1 < i_2 < \cdots < i_k : } \lambda_{i_1} \cdots \lambda_{i_k}$ where $i_j \in |V(\Gamma)|$ and $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_{|V(\Gamma)|}$ are the eigenvalues of the adjacency matrix.

There are always going to be paths of length 2: their contribution to the trace can be expressed in terms of the number of perfect matchings in the graph of different sizes. You might ask that there are no closed paths of length $2 < L \leq k$. I suspect having few closed paths expresses that the eigenvalues have some kind of `symmetry' expressed by a symmetric polynomial of the eigenvalues being small.

A variant of trails show up if you trace the alternating $k$th power of the non-backtracking operator of the graph as follows.

Namely, say that a closed walk is a weak trail if no edge is traversed more than once in each direction that can be given to the edge (so the edge might be traversed once in each direction). The non-backtracking operator acts on functions on directed edges of $\Gamma$. A directed edge $e_1$ is `connected' to $e_2$ if the terminus of $e_1$ is the source of $e_2$ but $e_1$ is not $e_2$ with the opposite orientation; note that this is not symmetric. The non-backtracking operator is the adjacency operator of the directed graph $\Gamma^*$ whose vertices are directed edges of $\Gamma$ and directed edges in $\Gamma^*$ are as above.

Note that closed walks in $\Gamma^*$ are in length-preserving one-to-one correspondence with closed non-backtracking walks in $\Gamma$. Closed paths in $\Gamma^*$ are in length-preserving one-to-one correspondence with closed non-backtracking weak trails in $\Gamma$.

Unfortunately, the non-backtracking operator is not self adjoint in general, but if $\Gamma$ is $d$-regular then one can write a Jordan form of the operator in terms of the eigenvalues of the adjacency operator of $\Gamma$ (see e.g. Section 3.1 of the article link of Lubetzky and Peres).

Because the non-backtracking operator is the adjacency operator of $\Gamma^*$, the previous remarks relating the eigenvalues of $\Gamma$ to closed paths also give a relation between some more complicated spectral information of $\Gamma$ and closed non-backtracking weak trails.

Sorry this doesn't exactly answer the question, it was originally intended as a comment.

$\endgroup$
10
  • $\begingroup$ Thank you! Can you go into a bit more detail on your last comment - on trails? $\endgroup$ Jun 22 '20 at 18:48
  • $\begingroup$ I added some more information: after thinking about it I realized it is not exactly trails that show up but a weaker variant: I added the details anyway. $\endgroup$ Jun 23 '20 at 0:34
  • $\begingroup$ @Michael_Magee What happens if, instead of the alternating $k$th power of $A$, we take the symmetric $k$th power of $A$? I am asking because, on the spectral side, I am working with real orthonormal vectors $v_i$ that satisfy $\alpha_i:=\langle v_i, A v_i\rangle$ large (at least for many $i$) without necessarily being eigenvectors. When I consider $\mathrm{Tr} A^{2k}$, all is fine, since $\mathrm{Tr} A^{2k} \geq \sum_i \alpha_i$ gives me a useful lower bound on $\mathrm{Tr} A^{2k}$. (continued in next comment) $\endgroup$ Jun 23 '20 at 4:02
  • $\begingroup$ @Michael_Magee [cont'd] However, even if we work with $\bigwedge^k A^2$ instead of $\bigwedge^{2 k} A$, we do not necessarily have $\mathrm{Tr} \bigwedge^k A^2 \geq \sum_{i_1<i_2<\dotsc<i_k} \alpha_{i_1}\dotsc \alpha_{i_k}$ (do we?), so I'm in a bit of a pickle. $\endgroup$ Jun 23 '20 at 4:10
  • $\begingroup$ Also, what exactly do you mean when you say that "closed paths of length ≤k show up when you take the trace of the alternating kth power of A"? It's not the case (as I naïvely understood at first) that the trace is simply the number of closed paths of length $k$ (times $-1$), though that's certainly a term. $\endgroup$ Jun 23 '20 at 5:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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