Asymptotically-Tight Bounds on the Number of Cycles in Generalized de Bruijn-Good Graphs
Ueli Maurer
The number of cycles of length $k$ that can be generated by $q$-ary $n$-stage feedback shift-registers is studied. This problem is equivalent to finding the number of cycles of length $k$ in the natural generalization, from binary to $q$-ary digits, of the so-called de Bruijn-Good graphs \cite{brychri,debrui}. The number of cycles of length $k$ in the $q$-ary graph $G^{(q)}_n$ of order $n$ is denoted by $\beta^{(q)}(n,k)$. Known results about $\beta^{(2)}(n,k)$ are summarized and extensive new numerical data is presented. Lower and upper bounds on $\beta^{(q)}(n,k)$ are derived showing that, for large $k$, virtually all $q$-ary cycles of length $k$ are contained in $G^{(q)}_n$ for $n>2\log_q k$, but virtually none of these cycles is contained in $G^{(q)}_n$ for $n<2\log_q k - 2\log_q \log_q k$. More precisely, if $\nu^{(q)}_k$ denotes the total number of $q$-ary length $k$ cycles, then for any function $f(k)$ that grows without bounds as $k\to\infty$ (e.g. $f(k)=\log_{q}\!\log_{q}\!\log_{q}k$), the bounds obtained on $\beta^{(q)}(n,k)$ are asymptotically tight in the sense that they imply \begin{eqnarray} \lim_{k\to\infty}\frac{\beta^{(q)}(n(k),k)}{\nu^{(q)}_k}&=&0 \text{ for } n(k)=\lfloor2\log_q k - 2\log_q \log_q k-f(k)\rfloor, \text{ and} \nonumber\\ \lim_{k\to\infty}\frac{\beta^{(q)}(n(k),k)}{\nu^{(q)}_k}&=&1 \text{ for } n(k)=\lfloor2\log_q k+f(k)\rfloor,\nonumber \end{eqnarray} where $\lfloor.\rfloor$ denotes the integer part of the enclosed number. Finally, some approximations for $\beta^{(q)}(n,k)$ are given that make the global behavior of $\beta^{(q)}(n,k)$ more transparent.
BibTeX Citation
@article{Maurer92c,
author = {Ueli Maurer},
title = {Asymptotically-Tight Bounds on the Number of Cycles in Generalized de {B}ruijn-Good Graphs},
journal = {Discrete Applied Mathematics},
pages = {421--436},
volume = {37},
year = {1992},
month = {7},
}