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.

Improve this question
$\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$
    – Hailong Dao
    Commented Jun 22, 2020 at 7:54
  • $\begingroup$ That would be the naïve expectation, but I don't see how that happens. $\endgroup$
    – H A Helfgott
    Commented Jun 22, 2020 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$
    – Hailong Dao
    Commented Jun 22, 2020 at 8:13
  • $\begingroup$ I'm not sure of quite what you have in mind. $\endgroup$
    – H A Helfgott
    Commented Jun 22, 2020 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$
    – Abdelmalek Abdesselam
    Commented Jun 22, 2020 at 13:31

1 Answer 1

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

Improve this answer
$\endgroup$
10
  • $\begingroup$ Thank you! Can you go into a bit more detail on your last comment - on trails? $\endgroup$
    – H A Helfgott
    Commented Jun 22, 2020 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$
    – Michael Magee
    Commented Jun 23, 2020 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$
    – H A Helfgott
    Commented Jun 23, 2020 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$
    – H A Helfgott
    Commented Jun 23, 2020 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$
    – H A Helfgott
    Commented Jun 23, 2020 at 5:38

You must log in to answer this question.

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