On Almost k -Covers of Hypercubes
- PDF / 386,577 Bytes
- 16 Pages / 442.205 x 665.008 pts Page_size
- 6 Downloads / 186 Views
Bolyai Society – Springer-Verlag
Combinatorica 16pp. DOI: 10.1007/s00493-019-4221-y
ON ALMOST k-COVERS OF HYPERCUBES ALEXANDER CLIFTON∗ , HAO HUANG† Received May 10, 2019 Revised October 29, 2019 In this paper, we consider the following problem: what is the minimum number of affine hyperplanes in Rn , such that all the vertices of {0, 1}n \ {~0} are covered at least k times, and ~0 is uncovered? The k = 1 case is the well-known Alon–F¨ uredi 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.
1. Introduction Alon’s Combinatorial Nullstellensatz [1] is one of the most powerful algebraic tools in modern combinatorics. It can be used to prove the following elegant result of Alon and F¨ uredi [2]: any set of affine hyperplanes that covers all the vertices of the n-cube Qn = {0, 1}n but one contains at least n affine hyperplanes. There are many generalizations and analogues of this theorem: for rectangular boxes [2], Desarguesian affine and projective planes [6,7], quadratic surfaces and Hermitian varieties in P G(n, q) [4]. The common theme of these results is: in many point-line (point-surface) geometries, to ∗ †
Mathematics Subject Classification (2010): 52C17, 05B40 Research supported in part by a George W. Woodruff Fellowship. Research supported in part by the Collaboration Grants from the Simons Foundation.
2
ALEXANDER CLIFTON, HAO HUANG
cover all the points except one, many more lines are needed than to cover all points. In this paper, we consider the following generalization of the Alon–F¨ uredi theorem. Let f (n, k) be the minimum number of affine hyperplanes needed to cover every vertex of Qn at least k times (except for ~0 = (0, . . . , 0) which is not covered at all). For convenience, from now on we call such a cover an almost k-cover of the n-cube. The Alon–F¨ uredi theorem gives f (n, 1) = n since the affine hyperplanes xi = 1, for i = 1, . . . , n cover Qn \ {~0}. Their result also leads to f (n, 2) = n + 1. The lower bound follows from observing that when removing one hyperplane from an almost 2-cover, the remaining hyperplanes form an almost 1-cover. On the other hand, the n affine hyperplanes xi = 1, together with x1 + · · · + xn = 1 cover every vertex of Qn \ {~0} at least twice. These observations immediately lead to a lower bound f (n, k) ≥ n+k−1 by removing k−1 affine hyperplanes, and an upper bound f (n, k) ≤ n+ k2 by considering the Pnfollowing almost k-cover: xi = 1 for i = 1, . . . , n, together with k−t copies of i=1 xi = t, for t = 1, . . . , k−1. In this construction, every binary vect
Data Loading...
