Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $B = \{0,1\}^n$ denote the boolean cube containing all $2^n$ binary vectors of size $n$. Let $D_v^s$ be a $d$ dimensional subcube of $B$ where the $d$-coordinates given by $s$ ($s \in [n]^d$) are free (i.e they take all $2^d$ values) and the rest $n-d$ coordinates are fixed to the binary vector $v$ (where $v \in \{0,1\}^{n-d}$). Thus $|D_v^s| = 2^d$.

Let $D_{v1}^{s1}, D_{v2}^{s2} \ldots D_{vk}^{sk}$ be $k$ different subcubes of $B$ where $k= {{n}\choose{d}}$ and $s1 \ldots sk$ are all possible subsets of $n$ of size $d$. Consider the union $U = \cup{D_{vi}^{si}} \ \ \forall i = 1 \rightarrow k$.

I am looking for conditions on the fixed variables $v_1 \ldots v_k$ such that this union has minimum cardinality. (i.e has minimum number of vectors)

Any thoughts on how to go about solving this?

share|cite|improve this question
The minimum cardinality is $\sum_{i=0}^{d} {{n}\choose{i}}$. For instance, the minimum is always attained when $v1 \ldots vk$ are all set to the same value. Also the minimum is attained by considering hamming balls for any fixed vector in $\{0,1\}^n$ of radius $d$. But this does not exhaust all possible ways of getting to the minimum. – Arun Sep 10 '12 at 6:50
I think where it says "$d$-coordinates" you mean "$d$ coordinates"? – joriki Sep 17 '12 at 9:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.