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?

(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.)

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.