Partition problems in high dimensional boxes

Matija Bucic, Bernard Lidický, Jason Long, Adam Zsolt Wagner

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish (US)
Pages (from-to)315-336
Number of pages22
JournalJournal of Combinatorial Theory. Series A
Volume166
DOIs
StatePublished - Aug 2019
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Partition problems in high dimensional boxes'. Together they form a unique fingerprint.

Cite this