Partition problems in high dimensional boxes

Abstract

Alon, Bohman, Holzman and Kleitman proved that any partition of a $d$-dimensional discrete box into proper sub-boxes must consist of at least $2^d$ sub-boxes. Recently, Leader, Milićević and Tan considered the question of how many odd-sized proper boxes are needed to partition a $d$-dimensional box of odd size, and they asked whether the trivial construction consisting of $3^d$ boxes is best possible. We show that approximately $2.93^d$ boxes are enough, and consider some natural generalisations.

19 pages, 10 figures

Cited by in corpus (3)

• Erdős-Szekeres theorem for multidimensional arrays
• Brick partition problems in three dimensions
• On 2-colored graphs and partitions of boxes