Back to Search Start Over

Exact hyperplane covers for subsets of the hypercube

Authors :
Aaronson, James
Groenland, Carla
Grzesik, Andrzej
Johnston, Tom
Kielak, Bartłomiej
Publication Year :
2020

Abstract

Alon and F\"{u}redi (1993) showed that the number of hyperplanes required to cover $\{0,1\}^n\setminus \{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.<br />Comment: Small fixes and updated code

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2010.00315
Document Type :
Working Paper
Full Text :
https://doi.org/10.1016/j.disc.2021.112490