Exact hyperplane covers for subsets of the hypercube
Publication date
2021-09
Authors
Aaronson, James
Groenland, Carla
Grzesik, Andrzej
Johnston, Tom
Kielak, Bartłomiej
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
cc_by_nc_nd
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.
Keywords
Exact covers, Hypercube, Hyperplanes, Intersection patterns, Theoretical Computer Science, Discrete Mathematics and Combinatorics
Citation
Aaronson, J, Groenland, C, Grzesik, A, Johnston, T & Kielak, B 2021, 'Exact hyperplane covers for subsets of the hypercube', Discrete Mathematics, vol. 344, no. 9, 112490, pp. 1-7. https://doi.org/10.1016/j.disc.2021.112490