On the independence number of de Bruijn graphs
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.14671
curl -X POST /api/v1/records/arxiv/2604.14671/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.14671/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'