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
More Info
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.