Covering symmetric sets of the Boolean cube by affine hyperplanes

DOI10.37236/10600zbMATH Open1489.52014arXiv2107.10385OpenAlexW4229041703MaRDI QIDQ2138580FDOQ2138580

Authors: S. Venkitesh 

Publication date: 12 May 2022

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: Alon and F"uredi (European J. Combin., 1993) proved that any family of hyperplanes that covers every point of the Boolean cube ${0,1}^n$ except one must contain at least $n$ 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${}^2$) 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${}^2$ 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${}^2$ 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${}^2$ grids, and could be regarded as being more combinatorial.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Exact hyperplane covers for subsets of the hypercube
• Covering almost all the layers of the hypercube with multiplicities
• Covering the cube by affine hyperplanes
• On almost \(k\)-covers of hypercubes
• Essential positive covers of the cube

zbMATH Keywords

Boolean cubehyperplane coverspolynomial covers

Mathematics Subject Classification ID

Packing and covering in (n) dimensions (aspects of discrete geometry) (52C17) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial geometries and geometric closure systems (51D20)

Cites Work

• Ideals, Varieties, and Algorithms
• Title not available (Why is that?)
• Algebraic immunity for cryptographically significant Boolean functions: analysis and construction
• Generalized Hamming weights for linear codes
• Covering finite fields with cosets of subspaces
• The blocking number of an affine space
• Combinatorial Nullstellensatz
• Generalized Hamming weights of q-ary Reed-Muller codes
• On intersection sets in Desarguesian affine spaces
• A combinatorial proof of strict unimodality for \(q\)-binomial coefficients
• Covering the cube by affine hyperplanes
• Alon's nullstellensatz for multisets
• Punctured combinatorial Nullstellensätze
• Essential covers of the cube by hyperplanes
• Essential positive covers of the cube
• A complex-number Fourier technique for lower bounds on the mod-\(m\) degree
• Covering all points except one
• Random low-degree polynomials are hard to approximate
• Set Systems with Restricted Cross-Intersections and the Minimum Rank ofInclusion Matrices
• Balancing sets of vectors
• Partitions of vector spaces
• Intersection sets in AG(\(n,q\)) and a characterization of the hyperbolic quadric in PG\((3,q\))
• On almost \(k\)-covers of hypercubes
• Hilbert functions and the finite degree Zariski closure in finite field combinatorial geometry
• Hilbert function and complexity lower bounds for symmetric Boolean functions
• Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression

Cited In (4)

• Covering the cube by affine hyperplanes
• Essential covers of the cube by hyperplanes
• Covering almost all the layers of the hypercube with multiplicities
• Essential positive covers of the cube

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)