Abstract:A \emph{subcube partition} is a partition of the Boolean cube $\{0,1\}^n$ into subcubes. A subcube partition is irreducible if the only sub-partitions whose union is a subcube are singletons and the entire partition. A subcube partition is tight if it "mentions" all coordinates. We study extremal properties of tight irreducible subcube partitions: minimal size, minimal weight, maximal number of points, maximal size, and maximal minimum dimension. We also consider the existence of homogeneous tight irreducible subcube partitions, in which all subcubes have the same dimensions. We additionally study subcube partitions of $\{0,\dots,q-1\}^n$, and partitions of $\mathbb{F}_2^n$ into affine subspaces, in both cases focusing on the minimal size. Our constructions and computer experiments lead to several conjectures on the extremal values of the aforementioned properties.
From: Yuval Filmus [view email]
[v1]
Fri, 30 Dec 2022 13:16:19 UTC (34 KB)
[v2]
Tue, 17 Jan 2023 16:36:56 UTC (41 KB)
[v3]
Fri, 18 Aug 2023 15:42:53 UTC (41 KB)
[v4]
Tue, 8 Sep 2026 15:12:12 UTC (43 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。