Exact hyperplane covers for subsets of the hypercube

Journal Article (2021)
Author(s)

James Aaronson (University of Oxford)

Carla Groenland (University of Oxford)

Andrzej Grzesik (Jagiellonian University)

Tom Johnston (University of Oxford)

Bartłomiej Kielak (Jagiellonian University)

Affiliation
External organisation
DOI related publication
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

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.