Login
Publications by the same author
plus in the repository
plus in Google Scholar
Bibliografische Daten exportieren		  

Irreducible Subcube Partitions

DOI zum Zitieren der Version auf EPub Bayreuth: https://doi.org/10.15495/EPub_UBT_00006837
URN to cite this document: urn:nbn:de:bvb:703-epub-6837-0

Title data

Filmus, Yuval ; Hirsch, Edward ; Ihringer, Ferdinand ; Kurz, Sascha ; Riazanov, Artur ; Smal, Alexander ; Vinyals, Marc:
Irreducible Subcube Partitions.
Bayreuth , 2023 . - 38 S.

This is the latest version of this item.

[thumbnail of Irreducible Subcube Partitions.pdf]
Format: PDF
Name: Irreducible Subcube Partitions.pdf
Version: Published Version
Available under License Creative Commons BY 4.0: Attribution
Download (705kB)

Abstract

A 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,...,q-1}^n, and partitions of GF(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.

Further data

Item Type: Preprint, postprint
Keywords: hitting formulas; partitions; hypercubes; Boolean
DDC Subjects: 000 Computer Science, information, general works > 004 Computer science
500 Science > 510 Mathematics
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics > Chair Mathematical Economics
Faculties
Language: English
Originates at UBT: Yes
URN: urn:nbn:de:bvb:703-epub-6837-0
Date Deposited: 24 Jan 2023 07:06
Last Modified: 24 Jan 2023 07:34
URI: https://epub.uni-bayreuth.de/id/eprint/6837

Available Versions of this Item