Covering the hypercube with a bounded number of disjoint snakes (Q1343173)

For any integer \(d\geq 2\), \(S(d)\) is the maximum length of an induced cycle -- called a snake -- in the graph of the \(d\)-dimensional cube, \(I[d]\); the vertex-set of \(I[d]\) is endowed in the obvious way with the structure of an additive group \({\mathbf Z}^ d_ 2= ({\mathbf Z}/2{\mathbf Z})^ d\). ``An extensive literature has evolved concerning the problem of estimating \(S(d)\),'' for which the author presents known bounds. The present paper is concerned with resolving a problem posed by P. Erdős, of deciding whether there exists an integer \(k\) such that, for every \(d\geq 2\), the vertices of \(I[d]\) can be covered by at most \(k\) snakes; and, if that is the case, whether it an be done in such a way that the snakes are vertex-disjoint. Theorem 1: For every \(n\geq 2\) there is a subgroup \({\mathfrak H}_ n\subset I[n]\) and a snake \(C_ n\subset I[n]\), such that \(|{\mathfrak H}_ n|\leq 16\), and that \(C_ n\) contains exactly one element of every coset of \({\mathfrak H}_ n\). The following corollary solves Erdős' problem. Corollary 1: For every \(n\geq 2\) the vertices of \(I[n]\) can be covered using at most 16 pairwise vertex-disjoint snakes. Theorem 2: Let \(k_ 0\), \(k_ 1\), \(k_ 2\) respectively be the smallest integers such that, for every \(n\geq 2\), the graph \(I[n]\) can be vertex covered by at most \(k_ 0\) snakes, by at most \(k_ 1\) pairwise vertex- disjoint snakes, and by at most \(k_ 2\) pairwise vertex-disjoint snakes of equal length, respectively; let \(k_ 3\) be the smallest integer such that, for every \(n\geq 2\), there exist a subgroup \({\mathfrak C}_ n\) and a snake \(C_ n\) in \(I[n]\), such that \(|{\mathfrak H}_ n| \leq k_ 3\), where \(C_ n\) contains exactly one element of every coset of \({\mathfrak H}_ n\). Then \(3\leq k_ 0\leq k_ 1\leq k_ 2\leq k_ 3\leq 16\) and \(k_ 2, k_ 3\in \{4,8,16\}\). ``The question of determining the exact values of \(k_ 0\), \(k_ 1\), \(k_ 2\), \(k_ 3\) remains open''.