Exact hyperplane covers for subsets of the hypercube

DOI10.1016/J.DISC.2021.112490MaRDI QIDQ2037567zbMATH OpenOpenAlexFDO

Authors James Aaronson, Carla Groenland, A. Grzesik, Tom Johnston, Bartłomiej Kielak

Publication date 8 July 2021

Published in Discrete Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2010.00315

zbMATH Keywords

hypercubehyperplanesintersection patternsexact covers

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Extremal combinatorics (05D99)

Abstract: Alon and F"{u}redi (1993) showed that the number of hyperplanes required to cover ${0,1}^{n}setminus0$ 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.

Recommendations

• An extremal problem of orthants containing at most one point besides the origin
• An upper bound on the number of planar K-sets
• General position subsets and independent hyperplanes in d-space
• Covering lattice points by subspaces and counting point-hyperplane incidences
• Petruska's question on planar convex sets
• Covering lattice points by subspaces and counting point-hyperplane incidences
• Point sets with many \(k\)-sets
• A parameterized algorithm for the hyperplane-cover problem
• Covering planar sets of constant width by three sets of smaller diameters
• A closed \((n+1)\)-convex set in \({\mathbb{R}}^ 2\) is a union of \(n^ 6\) convex sets

Cites work

• Covering the cube by affine hyperplanes
• On almost \(k\)-covers of hypercubes
• Polynomial threshold functions, hyperplane arrangements, and random tensors
• Turán’s Theorem in the Hypercube

Cited in

(15)

• Partitioning the \(n\)-space into collinear sets of orthants
• Covering symmetric sets of the Boolean cube by affine hyperplanes
• Covering the cube by affine hyperplanes
• On almost \(k\)-covers of hypercubes
• Forbidden \((0,1)\)-vectors in hyperplanes of \(\mathbb R^n\): the unrestricted case
• Covering all points except one
• Essential covers of the cube by hyperplanes
• scientific article; zbMATH DE number 4112541 (Why is no real title available?)
• Subspace coverings with multiplicities
• Explicit exponential lower bounds for exact hyperplane covers
• Covering almost all the layers of the hypercube with multiplicities
• The Exact Subset MultiCover problem
• Covering all but the low weight vertices of the unit cube
• A subspace covering problem in the n-cube
• Essential positive covers of the cube

This page was built for publication: Exact hyperplane covers for subsets of the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2037567)