Generalized Gray codes with prescribed ends (Q512653): Difference between revisions

An \(n\)-bit Gray code is a sequence of all \(n\)-bit vectors such that consecutive vectors differ in a single bit. Given any two \(n\)-bit vectors \(\alpha\) and \(\beta\), there is a Gray code starting in \(\alpha\) and ending in \(\beta\) if and only if the Hamming distance \(d(\alpha,\beta)\) is odd; see [\textit{I. Havel}, Čas. Pěstování Mat. 109, 135--152 (1984; Zbl 0544.05057)] \textit{R. Caha} and \textit{V. Koubek} [Discrete Math. 307, 2053--2066 (2007; Zbl 1125.05054)] generalised this fact by defining any set of \(2k\) distinct \(n\)-bit vectors \(\alpha_1,\beta_1,\ldots,\alpha_k,\beta_k\) to be \textit{connectable} if there are \(k\) sequences of distinct \(n\)-bit vectors that partition the set of all \(n\)-bit vectors such that, for each \(i=1,\ldots,k\), the \(i\)th sequence leads from \(\alpha_i\) to \(\beta_i\) and its consecutive vectors differ in a single bit. Caha and Koubek proved that, for \(k\leq n/2\), each such set of \(k\) vectors is connectable exactly when \(d(\alpha_i,\beta_i)\) is odd for each \(i=1,\ldots,k\). The present authors improve this result by proving that it is also true more generally when \(k\leq n-1\). This is a best possible bound and improves previous partial improvements in the literature.