Abstract
In this paper, we consider the following problem: what is the minimum number of affine hyperplanes in ℝn, such that all the vertices of \(\overrightarrow 0\) are covered at least k times, and \({\left\{{0,1} \right\}^n}\backslash \left\{{\overrightarrow 0} \right\}\) is uncovered? The k = 1 case is the well-known Alon-Füredi theorem which says a minimum of n affine hyperplanes is required, which follows from the Combinatorial Nullstellensatz.
We develop an analogue of the Lubell-Yamamoto-Meshalkin inequality for subset sums, and completely solve the fractional version of this problem, which also provides an asymptotic answer to the integral version for fixed n and k → ∞. We also use a Punctured Combinatorial Nullstellensatz developed by Ball and Serra, to show that a minimum of n + 3 affine hyperplanes is needed for k = 3, and pose a conjecture for arbitrary k and large n.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
N. Alon: Combinatorial Nullstellensatz, Combinatorics, Probability and Computing8 (1999), 7–29.
N. Alon and Z. Füredi: Covering the cube by affine hyperplanes, Eur. J. Comb.14 (1993), 79–83.
S. Ball and O. Serra: Punctured combinatorial Nullstellensätze, Combinatorica29 (2009), 511–522.
A. Blokhuis, A. Brouwer and T. Szőnyi: Covering all points except one, Journal of Algebraic Combinatorics32 (2010), 59–66.
B. Bollobás: On generalized graphs, Acta Mathematica Academiae Scientiarum Hungaricae16 (3–4) (1965) 447–452.
A. Brouwer and A. Schrijver: The blocking number of an affine space, J. Comb. Theory, Ser. A24 (1978), 251–253.
R. Jamison: Covering finite fields with cosets of subspaces, J. Comb. Theory, Ser. A22 (1977), 253–266.
D. Lubell: A short proof of Sperner’s lemma, J. Comb. Theory1 (1966), 299.
L. Meshalkin: Generalization of Sperner%’s theorem on the number of subsets of a finite set, Theory of Probability and Its Applications8 (1963), 203–204.
K. Yamamoto: Logarithmic order of free distributive lattice, Journal of the Mathematical Society of Japan6 (1954), 343–353.
Acknowledgement
We would like to thank Noga Alon for sharing the Ramsey-type proof mentioned above, and the anonymous referees for their extremely helpful comments and suggestions on improving the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Research supported in part by a George W. Woodruff Fellowship.
Research supported in part by the Collaboration Grants from the Simons Foundation.