Partition problems in high dimensional boxes

DOI10.1016/J.JCTA.2019.02.011MaRDI QIDQ2000653zbMATHOpenAlexWikidataFDO

Authors Bernard Lidický, Jason Long, Adam Zsolt Wagner, Matija Bucić

Publication date 28 June 2019

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.11278

zbMATH Keywords

linear programmingpartition problemshigh dimensional boxes

Mathematics Subject Classification ID

Linear programming (90C05) Partitions of sets (05A18) Discrete geometry (52C99)

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.

Recommendations

• On partitions of discrete boxes
• Minimal partitions of a box into boxes
• scientific article; zbMATH DE number 487006
• Brick partition problems in three dimensions
• scientific article; zbMATH DE number 4175876

Cites work

• scientific article; zbMATH DE number 431514 (Why is no real title available?)
• Decomposing the complete \(r\)-graph
• Finite algebras of finite complexity
• Kleitman and combinatorics
• Minimal partitions of a box into boxes
• On Partitions of a Rectangle into Rectangles with Restricted Number of Cross Sections
• On partitions of discrete boxes
• Polyboxes, cube tilings and rigidity

Cited in

(11)

• Erdős-Szekeres theorem for multidimensional arrays
• On the number of high‐dimensional partitions
• scientific article; zbMATH DE number 797058 (Why is no real title available?)
• Box-bisection for solving second-degree systems and the problem of clustering
• Minimal partitions of a box into boxes
• Polychromatic Colorings of n-Dimensional Guillotine-Partitions
• scientific article; zbMATH DE number 487006 (Why is no real title available?)
• On partitions of two-dimensional discrete boxes
• On partitions of discrete boxes
• Box-respecting colorings of \(n\)-dimensional guillotine-partitions
• Brick partition problems in three dimensions

Describes a project that uses

Uses Software

• Gurobi

This page was built for publication: Partition problems in high dimensional boxes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000653)