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.
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- High dimensional boxes
- Linear programming
- Partition problems