Optimal-colouring conjecture for fixed-length de Bruijn cycle decompositions

About 11 years old · traced to

Let E(q,k,ℓ)\mathcal{E}(q,k,\ell) denote the maximum number of eBugs in an ℓ\ell-valid colouring with qq colours and kk LEDs per eBug. An optimal colouring is one attaining the upper bound E(q,k,ℓ)≤qℓ/k\mathcal{E}(q,k,\ell)\leq q^\ell/k; necessarily k>ℓk>\ell. Optimal-colouring conjecture.

E(q,k,ℓ)=qℓk\mathcal{E}(q,k,\ell)=\dfrac{q^\ell}{k}

whenever kk divides qℓq^\ell and k>ℓk>\ell. This characterises when optimal colourings exist and would resolve the exact determination problem in these divisibility cases; the conjecture was confirmed computationally for all q,ℓq,\ell with qℓ≤81q^\ell\leq81, and is known for ℓ=2\ell=2 by Bryant's decomposition result.

References

Primary source

Tony Grubman, Y. Ahmet Şekercioğlu and David R. Wood, “Partitioning de Bruijn Graphs into Fixed-Length Cycles for Robot Identification and Tracking”, arXiv:1502.02199 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.