Partition problems in high dimensional boxes

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

doi:10.1016/j.jcta.2019.02.011

Partition problems in high dimensional boxes

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

Research output: Contribution to journal › Article › peer-review

4 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 language	English (US)
Pages (from-to)	315-336
Number of pages	22
Journal	Journal of Combinatorial Theory. Series A
Volume	166
DOIs	https://doi.org/10.1016/j.jcta.2019.02.011
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

Access to Document

10.1016/j.jcta.2019.02.011

Cite this

@article{04ddffcf103842f4b10bdc72c397844b,

title = "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{\'c}evi{\'c} 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.",

keywords = "High dimensional boxes, Linear programming, Partition problems",

author = "Matija Bucic and Bernard Lidick{\'y} and Jason Long and Wagner, \{Adam Zsolt\}",

note = "Publisher Copyright: {\textcopyright} 2019 Elsevier Inc.",

year = "2019",

month = aug,

doi = "10.1016/j.jcta.2019.02.011",

language = "English (US)",

volume = "166",

pages = "315--336",

journal = "Journal of Combinatorial Theory. Series A",

issn = "0097-3165",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Partition problems in high dimensional boxes

AU - Bucic, Matija

AU - Lidický, Bernard

AU - Long, Jason

AU - Wagner, Adam Zsolt

PY - 2019/8

Y1 - 2019/8

N2 - 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.

AB - 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.

KW - High dimensional boxes

KW - Linear programming

KW - Partition problems

UR - https://www.scopus.com/pages/publications/85063227003

UR - https://www.scopus.com/pages/publications/85063227003#tab=citedBy

U2 - 10.1016/j.jcta.2019.02.011

DO - 10.1016/j.jcta.2019.02.011

M3 - Article

AN - SCOPUS:85063227003

SN - 0097-3165

VL - 166

SP - 315

EP - 336

JO - Journal of Combinatorial Theory. Series A

JF - Journal of Combinatorial Theory. Series A

ER -

Partition problems in high dimensional boxes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this