Linear $d$-polychromatic $Q_{d-1}$-colorings of the Hypercube

Abstract

Let $n\ge d\ge \ell \ge 1$ be integers, and denote the $n$-dimensional hypercube by $Q_n$. A coloring of the $\ell$-dimensional subcubes $Q_{\ell }$ in $Q_n$ is called a $Q_{\ell }$-coloring. Such a coloring is $d$-polychromatic if every $Q_d$ in the $Q_n$ contains a $Q_{\ell }$ of every color. In this paper we consider a specific class of $Q_{\ell }$-colorings that are called linear. Given $\ell$ and $d$, let $p_{lin}^{\ell }(d)$ be the largest number of colors such that there is a $d$-polychromatic linear $Q_{\ell }$-coloring of $Q_n$ for all $n\ge d$. We prove that for all $d\ge 3$, $p_{lin}^{d-1}(d)=2$. In addition, using a computer search, we determine $p_{lin}^{\ell }(d)$ for some specific values of $\ell$ and $d$, in some cases improving on previously known lower bounds.