Paper Info
Title
Covering Symmetric Sets of the Boolean Cube by Affine Hyperplanes
Abstract
Alon and Furedi (European J. Combin., 1993) proved that any family of hyperplanes that covers every point of the Boolean cube {0, l}(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 (SU2) grids. As a central tool for solving our problems, we give a combinatorial characterization of (finite-degree) Zariski (Z-) closures of symmetric sets of the Boolean cube. In fact, we obtain a characterization that concerns, more generally, weight-determined sets of SU2 grids. However, in this generality, our characterization is not of the Z-closures but of a new variant of Z-closures defined exclusively for weight-determined sets, which coincides with the Z-closures in the Boolean cube setting, for symmetric sets. This characterization admits a linear time algorithm, and 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. In the Boolean cube setting, our above characterization can also be derived using a result of Bernasconi and Egidi (Inf. Comput., 1999) that determines the affine Hilbert functions of symmetric sets. However, our proof is independent of this result, works for all SU2 grids, and could be regarded as being more combinatorial. We also introduce another new variant of Z-closures to better understand the difference between the hyperplane and polynomial covering problems over uniform grids. Finally, we conclude by introducing a third variant of our covering problems and conjecturing its solution in the Boolean cube setting.
Year
DOI
Venue
2022
10.37236/10600
ELECTRONIC JOURNAL OF COMBINATORICS
DocType
Volume
Issue
Journal
29
2
ISSN
Citations 
PageRank 
1077-8926
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
S. Venkitesh113.05