Article ID Journal Published Year Pages File Type
10331875 Information Processing Letters 2015 11 Pages PDF
Abstract
Consider sets S of hypercubes of side 2 in the discrete n-dimensional torus of side 4 with the property that every possible hypercube of side 2 has a nonempty intersection with some hypercube in S. The problem of minimizing the size of S is studied in two settings, depending on whether intersections between hypercubes in S are allowed or not. If intersections are not allowed, then one is asking for the smallest size of a non-extensible packing S; this size is denoted by f(n). If intersections are allowed, then the structure S is called a blocking set. The smallest size of a blocking set S is denoted by h(n). By computer-aided techniques, it is shown that f(5)=12, f(6)=16, h(6)=15 and h(7)≤23. Also, non-extensible packings as well as blocking sets of certain small sizes are classified for n≤6. There is a direct connection between these problems and a covering problem originating from the football pools.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,