On the independence number of de Bruijn graphs

Abstract

We derive the asymptotic formula $\alpha (k,q)={\lambda }_{k-1}{q}^k+o(q^k)$, where $\alpha (k,q)$ is the independence number of the de Bruijn graph $B(k,q)$, and ${\lambda }_{k-1}$ is a constant arising from a variational problem on the unit $(k-1)$-dimensional cube. When $k=4$, we show the bounds $91/240\le {\lambda }_3\le 11/28$. For odd prime $k$, we analyse the binary case $q=2$ via a phase reduction on rotation orbits. For $k=11,13,17$ this yields compact orbit-marker certificates for optimal constructions. Combined with a lifting theorem by Lichiardopol, these certificates give exact formulas for $\alpha (11,q)$, $\alpha (13,q)$, and $\alpha (17,q)$ for all $q\ge 2$, extending the known cases $k=3,5,7$.

arXiv comment34 pages