Let $G$ be a $d$-regular graph on $n$ vertices. I'm interested in upper bounds on the number of cycles of length $k$ that hold for any such $G$. The regime I'm interested in is:
- $d$ is fixed, and $n$ is tending to infinity,
- $k$ is growing as a function of $n$. I'm most interested in the case when $k\gg \sqrt{n}$.
Here's an example of such a result: for $k=n$ (i.e we're counting Hamilton cycles), the number of $k$ cycles on $G$ is at most $(d!)^{n/d}$. This follows from Bregman's bound on the permanent of a 0-1 matrix (see discussion on p. 93 of https://people.math.ethz.ch/~sudakovb/hamiltonian-decomposition.pdf). I would like to know of results of this flavor, where $k$ is a bit less than $n$.
Thanks for any help!
