MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 added 4 characters in body

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 contractible 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)

1

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 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)