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.
Original language | English (US) |
---|---|
Pages (from-to) | 315-336 |
Number of pages | 22 |
Journal | Journal of Combinatorial Theory. Series A |
Volume | 166 |
DOIs | |
State | Published - Aug 2019 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
Keywords
- High dimensional boxes
- Linear programming
- Partition problems