Exact hyperplane covers for subsets of the hypercube
Journal Article
(2021)
Authors
James Aaronson (University of Oxford)
C.E. Groenland (University of Oxford)
Andrzej Grzesik (Jagiellonian University)
Tom Johnston (University of Oxford)
Bartłomiej Kielak (Jagiellonian University)
Affiliation
External organisation
To reference this document use:
https://doi.org/10.1016/j.disc.2021.112490
TU Delft Repository resolver:
https://resolver.tudelft.nl/49ac868a-073c-4df3-9a11-6c18885ab8c4
More Info
expand_more
expand_more
Publication Year
2021
Language
English
Affiliation
External organisation
Issue number
9
Volume number
344
DOI:
https://doi.org/10.1016/j.disc.2021.112490
Abstract
Alon and Füredi (1993) showed that the number of hyperplanes required to cover {0,1}n∖{0} without covering 0 is n. We initiate the study of such exact hyperplane covers of the hypercube for other subsets of the hypercube. In particular, we provide exact solutions for covering {0,1}n while missing up to four points and give asymptotic bounds in the general case. Several interesting questions are left open.
No files available
Metadata only record. There are no files for this record.