6
$\begingroup$

Let $C_d(n)$ be the lattice cube consisting of the $n^d$ points with each of its $d$ coorindates in $\lbrace 1,2,\ldots,n \rbrace$. Define a blocking set for a lattice cube to be a set of points in the cube that meets every axis-parallel line through a lattice point of any facet of the cube. Let $b_d(n)$ be the minimum cardinality of a blocking set for $C_d(n)$.

Q1. What is the function $b_d(n)$?

For $d=2$, selecting the $n$ points on the diagonal through $(1,1)$ and $(n,n)$ suffices to block the $n$ lines through each facet/side of the cube/square; so $C_2(n)=n$. Because a facet consists of $n^{d-1}$ points, and a line orthogonal to the facet through each point must be blocked, $n^{d-1}$ is a lower bound on $b_d(n)$. A more specific version of Q1 is:

Q2. Can the lower bound be achieved? Is $b_d(n) = n^{d-1}$? If the lower bound cannot always be achieved, when can it be achieved?

For $C_3(3)$, the $\mathbb{Z}^3$-cube consisting of $27$ points, here is a blocking set $B$ with $|B|=10=n^2+1$:
        Blocking set

Perhaps these questions have already been explored? If so, I would appreciate references. Thanks!

My interest in the above questions derive from the more geometrical question: What is the "minimal object'' that casts a (hyper)cube-shadow from parallel light rays in the $d$ coordinate directions? I defer this question until I understand the combinatorial version.

Addendum. As per Johan Wästlund and Eoin, indeed the lowerbound is achievable. Here is a 9-point blocking set for $C_3(3)$:
        Blocking set: 9

$\endgroup$
5
  • 1
    $\begingroup$ It is my understanding that the first line contains a typo ($d$ in $\{1,2,...,d\}$ is to be replaced with $n$). $\endgroup$
    – Seva
    Aug 1, 2012 at 19:36
  • $\begingroup$ @Seva: You are right!---Thanks; corrected. $\endgroup$ Aug 1, 2012 at 19:39
  • 1
    $\begingroup$ If I got this right, the set of points whose coordinates add to a number divisible by $n$ will have exactly one point on each such line. Does this answer the question? $\endgroup$ Aug 1, 2012 at 20:15
  • 1
    $\begingroup$ I was thinking about this question some more today, and I realized that your initial 10-point blocking set in $C_3(3)$ is still interesting for the following reason: it is 'irreducible' in the sense that removing any point leaves a non-blocking set. So you might also ask what the size of the largest irreducible blocking set is for $C_d(n)$; to me at least it appears much harder to obtain sharp bounds in this latter case. For $d = n = 3$ it seems to be 13 (obtained by taking the central point of each edge as well as the center of the cube), although I haven't rigorously proved this. $\endgroup$
    – ARupinski
    Aug 3, 2012 at 0:48
  • $\begingroup$ @ARupinski: Very nice question! Yes, the reason I (mistakenly) thought maybe my example was minimal is that it was irreducible. $\endgroup$ Aug 3, 2012 at 1:48

2 Answers 2

5
$\begingroup$

Hi Joseph, I think that the lower bound is always achievable. For example, you can take \begin{equation*} { B = \lbrace (v_1,\ldots ,v_d) \in C_d(n): \sum _{i=1}^d v_i \equiv 0 \mod n \rbrace } \end{equation*} since the modulo sum in this expression takes all $n$ distinct value on any axis parallel line. If we view $C_d(n)$ as the discrete torus, $B$ is just a hyperplane. It would be interesting to know whether all such blocking sets are of this form.

I don't know any references for this specific problem, but there has been interesting work on a similar problem of blocking non-trivial cycles in the discrete torus. Here, we again view $C_d(n)$ as the discrete torus and want to remove a set $B$ which intersects every non-contractible cycle. Maybe the following might be useful:

Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell: Eliminating Cycles in the Discrete Torus. Algorithmica 50(4): 446-454 (2008)

Noga Alon: Economical Elimination of Cycles in the Torus. Combinatorics, Probability & Computing 18(5): 619-627 (2009)

$\endgroup$
3
  • $\begingroup$ @Eoin: You raise an interesting question: Are all blocking sets toric hyperplanes? $\endgroup$ Aug 2, 2012 at 2:26
  • 1
    $\begingroup$ You mean all minimal blocking sets. It's certainly true for $n=2$ (and $n=1$...); it's false for $n>3$, for the trivial reason that there are permutations of $\lbrace 1, \ldots, n \rbrace$ that do not preserve the set of toric hyperplanes, though it might still be true up to permutations. $\endgroup$ Aug 2, 2012 at 2:34
  • $\begingroup$ @Noam: Yes, thanks for clarifying and sharpening that question. $\endgroup$ Aug 2, 2012 at 11:46
2
$\begingroup$

This is somewhat of an expanded comment on Eoin's answer and his follow-up question of whether such sets correspond to hyperplanes in the discrete torus.

In the $C_2(n)$ case minimal blocking sets correspond to permutation of $\{1...n\}$ (consider a permutation matrix; then a minimal blocking set can be formed by choosing the points corresponding to the positions of the 1's in this matrix). Conversely, every minimal blocking set in the $d=2$ case arises this way, so for $n\geq 4$ not every blocking set corresponds to a hyperplane on a torus.

In the $d=3$ case this can be extended to see that every minimal blocking set corresponds to a set of $n$ permutations whose permutation matrix sums to the all 1's matrix (think of stacking the permutation matrices up to form our cube); again it is clear that not all such sets can correspond to hyperplanes if $n \geq 4$.

For $d \geq 4$, one can apply an analogous stacking approach using sets in $C_{d-1}$ to generate all minimal blocking sets although it is not immediately obvious to me how to relate these sets to permutations easily.

For $n = 2$, it is easy to see that there are exactly two minimal blocking sets in any dimension and both always correspond to toric hyperplanes, and it seems that all minimal blocking sets are also toric hyperplanes for $n=3$ in any dimension due to how little room there is in $S_3$ to form such sets (this should follow from induction on the dimension; once one lays down the first $d-1$-dimensional layer and one point in the next layer, this should determine where all the remaining points must go in the last two layers). If anyone can easily formalize this idea for the $n=3$ case (or provide a counterexample) I would love to see it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.