Covering symmetric sets of the Boolean cube by affine hyperplanes
From MaRDI portal
(Redirected from Publication:2138580)
Abstract: Alon and F"uredi (European J. Combin., 1993) proved that any family of hyperplanes that covers every point of the Boolean cube except one must contain at least hyperplanes. We obtain two extensions of this result, in characteristic zero, for hyperplane covers of symmetric sets of the Boolean cube (subsets that are closed under permutations of coordinates), as well as for `polynomial covers' of `weight-determined' sets of `strictly unimodal uniform' (SU) grids. As a main tool for solving our problems, we give a combinatorial characterization of (finite-degree) Zariski (Z-) closures of symmetric sets of the Boolean cube -- the Z-closure of a symmetric set is symmetric. In fact, we obtain a characterization that concerns, more generally, weight-determined sets of SU grids. However, in this generality, our characterization is not of the Z-closures -- unlike over the Boolean cube, the Z-closure of a weight-determined set need not be weight-determined. We introduce a new closure operator exclusively for weight-determined sets -- the `(finite-degree) Z*-closure' -- defined to be the maximal weight-determined set in the Z-closure. (This coincides with the Z-closure over the Boolean cube, for symmetric sets.) We obtain a combinatorial characterization of the finite-degree Z*-closures of weight-determined sets of an SU grid. This characterization may also be of independent interest. Indeed, as further applications, we (i) give an alternate proof of a lemma by Alon et al. (IEEE Trans. Inform. Theory, 1988), and (ii) characterize the `certifying degrees' of weight-determined sets. Over the Boolean cube, our above characterization can also be derived using a result of Bernasconi and Egidi (Inf. Comput., 1999). However, our proof is independent of this result, works for all SU grids, and could be regarded as being more combinatorial.
Recommendations
Cites work
- scientific article; zbMATH DE number 3103212 (Why is no real title available?)
- A combinatorial proof of strict unimodality for q-binomial coefficients
- A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
- Algebraic immunity for cryptographically significant Boolean functions: analysis and construction
- Alon's nullstellensatz for multisets
- Balancing sets of vectors
- Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
- Combinatorial Nullstellensatz
- Covering all points except one
- Covering finite fields with cosets of subspaces
- Covering the cube by affine hyperplanes
- Essential covers of the cube by hyperplanes
- Essential positive covers of the cube
- Generalized Hamming weights for linear codes
- Generalized Hamming weights of q-ary Reed-Muller codes
- Hilbert function and complexity lower bounds for symmetric Boolean functions
- Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
- Ideals, Varieties, and Algorithms
- Intersection sets in AG(n,q) and a characterization of the hyperbolic quadric in PG(3,q)
- On almost \(k\)-covers of hypercubes
- On intersection sets in Desarguesian affine spaces
- Partitions of vector spaces
- Punctured combinatorial Nullstellensätze
- Random low-degree polynomials are hard to approximate
- Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
- The blocking number of an affine space
Cited in
(4)
This page was built for publication: Covering symmetric sets of the Boolean cube by affine hyperplanes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2138580)
