Complexity of counting cycles using zeons

Nilpotent adjacency matrix methods are employed to count $k$ ‐cycles in simple graphs on $n$ vertices for any $k=n$ . The worst‐case time complexity of counting $k$ ‐cycles in an $n$ ‐vertex simple graph is shown to be $\mathcal{O}\left(n^{\alpha +1}{2}^n\right)$ , where $\alpha =3$ is the exponent representing the complexity of matrix multiplication. When $k$ is fixed, the counting of all $k$ ‐cycles in an $n$ ‐vertex graph is of time complexity $\mathcal{O}\left(n^{\alpha +k‐1}\right)$ . Letting $\Omega =\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ , the average‐case time complexity of counting $k$ ‐cycles in an $n$ ‐vertex, $e$ ‐edge graph where $e\le q(\frac{\Omega }{k}-1)$ for fixed $0<q<1$ is found to be $\mathcal{O}\left(n^4{(1+q)}^n\right)$ . The storage complexity of the approach detailed herein is $\mathcal{O}\left(n^2{2}^n\right)$ . For reference, experimental results detailing computation times (in seconds) are included alongside similar computations performed with algorithms based on the approaches of Bax and Tarjan.