Exact hyperplane covers for subsets of the hypercube

James Aaronson; Carla Groenland; Andrzej Grzesik; Tom Johnston; Bartłomiej Kielak

doi:10.1016/j.disc.2021.112490

Exact hyperplane covers for subsets of the hypercube

James Aaronson
, Carla Groenland
, Andrzej Grzesik
, Tom Johnston
, Bartłomiej Kielak

Research output: Contribution to journal › Article › Academic › peer-review

Abstract

Alon and Füredi (1993) showed that the number of hyperplanes required to cover {0,1}ⁿ∖{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}ⁿ while missing up to four points and give asymptotic bounds in the general case. Several interesting questions are left open.

Original language	English
Article number	112490
Pages (from-to)	1-7
Journal	Discrete Mathematics
Volume	344
Issue number	9
DOIs	https://doi.org/10.1016/j.disc.2021.112490
Publication status	Published - Sept 2021

Bibliographical note

Funding Information:
This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 648509 ).

Publisher Copyright:
© 2021 The Author(s)

Keywords

Exact covers
Hypercube
Hyperplanes
Intersection patterns

Access to Document

10.1016/j.disc.2021.112490Licence: CC BY-NC-ND

1-s2.0-S0012365X2100203X-mainFinal published version, 259 KBLicence: CC BY-NC-ND

Cite this

@article{4506b50a39c8488cb62fa6283344cb45,

title = "Exact hyperplane covers for subsets of the hypercube",

abstract = "Alon and F{\"u}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",

author = "James Aaronson and Carla Groenland and Andrzej Grzesik and Tom Johnston and Bart{\l}omiej Kielak",

note = "Funding Information: This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 648509 ). Publisher Copyright: {\textcopyright} 2021 The Author(s)",

year = "2021",

month = sep,

doi = "10.1016/j.disc.2021.112490",

language = "English",

volume = "344",

pages = "1--7",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier BV",

number = "9",

}

TY - JOUR

T1 - Exact hyperplane covers for subsets of the hypercube

AU - Aaronson, James

AU - Groenland, Carla

AU - Grzesik, Andrzej

AU - Johnston, Tom

AU - Kielak, Bartłomiej

N1 - Funding Information: This work has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 648509 ). Publisher Copyright: © 2021 The Author(s)

PY - 2021/9

Y1 - 2021/9

N2 - 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.

AB - 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.

KW - Exact covers

KW - Hypercube

KW - Hyperplanes

KW - Intersection patterns

UR - https://www.scopus.com/pages/publications/85107454814

U2 - 10.1016/j.disc.2021.112490

DO - 10.1016/j.disc.2021.112490

M3 - Article

SN - 0012-365X

VL - 344

SP - 1

EP - 7

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 9

M1 - 112490

ER -

Exact hyperplane covers for subsets of the hypercube

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this