Linear d-polychromatic Q_d-1-colorings of the hypercube

Abstract: Let

n g e d g e e l l g e 1

be integers, and denote the

n

-dimensional hypercube by

Q_{n}

. A coloring of the

e l l

-dimensional subcubes

Q_{e} l l

in

Q_{n}

is called a

Q_{e} l l

-coloring. Such a coloring is

d

-polychromatic if every

Q_{d}

in the

Q_{n}

contains a

Q_{e} l l

of every color. In this paper we consider a specific class of

Q_{e} l l

-colorings that are called linear. Given

e l l

and

d

, let

p_{l i n}^{e} l l (d)

be the largest number of colors such that there is a

d

-polychromatic linear

Q_{e} l l

-coloring of

Q_{n}

for all

n g e d

. We prove that for all

d g e 3

,

p_{l i n}^{d - 1} (d) = 2

. In addition, using a computer search, we determine

p_{l i n}^{e} l l (d)

for some specific values of

e l l

and

d

, in some cases improving on previously known lower bounds.

Recommendations

Cites Work

Cited In (6)

This page was built for publication: Linear \(d\)-polychromatic \(Q_{d-1}\)-colorings of the hypercube