Exact hyperplane covers for subsets of the hypercube
The exact cover of \(B\subseteq \{0, 1\}^n\), denoted by \(\mathrm{ec}(B)\), is a set of hyperplanes in \(\mathbb{R}^n\) whose union intersects \(\{0, 1\}^n\) exactly at \(B\) -- that is, the points in \(\{0,1\}^n\setminus B\) are not covered. If just one point, say \(0\), is removed, then \(\mathrm{ec}(\{0,1\}^n\setminus\{0\})=n\) from work of \textit{N. Alon} and \textit{Z. Füredi} [Eur. J. Comb. 14, No. 2, 79--83 (1993; Zbl 0773.52011)]. In this article, the authors generalize this to up to \(4\) points removed. They show that \(\mathrm{ec}(\{0,1\}^n\setminus S) = n-1\) if \(|S|\in\{2,3\}\), and if \(|S|=4\), then \(\mathrm{ec}(\{0,1\}^n\setminus S)\) is \(n-1\) if the four points of \(S\) are not coplanar, and \(n-2\) otherwise. The authors prove asymptotic bounds concerning the following two numbers: for \(n,k\in\mathbb{N}\), \begin{align*} \mathrm{ec}(n, k) &= \max\{\mathrm{ec}(\{0,1\}^n\setminus S) : S\subseteq \{0,1\}^n, \; |S|=k \}, \\ \mathrm{ec}(n) &= \max\{\mathrm{ec}(B) : B\subseteq \{0,1\}^n \}. \end{align*} They close by posing two problems that would, if answered affirmatively, tighten the bounds they determined.
- 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
- Covering the cube by affine hyperplanes
- Essential covers of the cube by hyperplanes
- Covering all but the low weight vertices of the unit cube
- Covering symmetric sets of the Boolean cube by affine hyperplanes
- Explicit exponential lower bounds for exact hyperplane covers
- On almost \(k\)-covers of hypercubes
- Forbidden \((0,1)\)-vectors in hyperplanes of \(\mathbb R^n\): the unrestricted case
- Partitioning the n-space into collinear sets of orthants
- scientific article; zbMATH DE number 4112541 (Why is no real title available?)
- Essential positive covers of the cube
- A subspace covering problem in the n-cube
- Covering all points except one
- Covering almost all the layers of the hypercube with multiplicities
- The Exact Subset MultiCover problem
- Subspace coverings with multiplicities
- Simple proofs for lattice coverings and sparse tensors
- Nondegenerate hyperplane covers of the hypercube
- Almost covers of finite sets of points
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)
