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

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,)=qk\mathcal{E}(q,k,\ell)=\dfrac{q^\ell}{k}

whenever kk divides qq^\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 q81q^\ell\leq81, and is known for =2\ell=2 by Bryant's decomposition result.

Sources & referencesView supporting material

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.