{"id":"arxiv/2604.14671","url":"https://arxiv.org/abs/2604.14671","tags":["math.CO","cs.IT"],"score":0,"title":"On the independence number of de Bruijn graphs","domain":"math.CO","source":"arxiv","authors":["Pietro Majer","Matteo Novaga"],"reviews":0,"subject":"math.CO","summary":"We derive the asymptotic formula $α(k,q)=λ_{k-1}q^k+o(q^k)$, where $α(k,q)$ is the independence number of the de Bruijn graph $B(k,q)$, and $λ_{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 λ_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 $α(11,q)$, $α(13,q)$, and…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-16","reactions":{}}