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
Exact covers Hypercube Hyperplanes Intersection patterns
More Info
expand_more

Published Date

2021

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Affiliation

External organisation

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.