Exact hyperplane covers for subsets of bricks

Abstract

none

Let h_1, h_2, ..., h_n be n positive integers, and V=V(h_1, h_2, ..., h_n) be a set of lattice points (y_1, y_2, ..., y_n) such that 0≤ y_i≤ h_i. Given S⊆V=V(h_1, h_2, ..., h_n), the exact cover of VS is a collection of hyperplanes whose union intersects V(h_1, h_2, ..., h_n) exactly in VS. That is, the points from S are not covered. The exact cover number of VS, denoted by ec(VS), is the minimum size of an exact cover of VS. Alon and Füredi (1993) proved that ec({0, 1}^n{0})=n and if S⊆V=V(h_1, h_2, ..., h_n) with |S|=1, then ec(VS)= Σ(from i=1 to n)h_i. Aaronson et al. (2021) showed that if |S|=2, 3, then ec({0, 1}^nS)=n-1. If |S|=4, thenec({0, 1}^nS)=n-1 if there is a hyperplane Q with |Q∩S|=3, and ec({0, 1}^nS)=n-2 otherwise.In this paper, we combine the problems mentioned above, and study the problem of covering V(h_1, h_2, ..., h_n) while missing two, three, or four points. Let S be a subset of V=V(h_1, h_2, ..., h_n) with |S|=2,3,4. Our main results are as follows. If |S|=2, then ec(VS)= Σ(from i=1 to n)h_i-1. If |S|=3 and the dimension n=2, then ec(VS)=h_1+h_2-2 if the three points in S are coaxial, and ec(VS)=h_1+h_2-1 otherwise. If |S|=3 and the three points in S are not collinear, then ec(VS)= Σ(from i=1 ton)h_i-1. If |S|=3 and the three points in S are coaxial, then ec(VS)= Σ(from i=1 to n)h_i-2. For the case of missing three collinear points and missing four points, we have partial results. Some cases have matching upper and lower bounds, but some still have gaps.