= Separated block decomposition for vector subset sums
For Euclidean vectors $x_i$ of length at least one, their labeled subset sums can be partitioned into pairwise distance-at-least-one blocks, with $\binom nr-\binom n{r-1}$ blocks of size $n-2r+1$. To extend a separated block by a vector $x$, choose its member $y$ minimizing inner product with $x$. The translated block together with $y$ remains separated, since $(z+x-y)\cdot x\geq\|x\|^2$. The untransformed block with $y$ removed remains separated too. Block sizes change from $\ell$ to $\ell+1,\ell-1$, the same recurrence as a <symmetric chain decomposition of a Boolean lattice>. There are exactly $\binom n{\lfloor n/2\rfloor}$ nonempty blocks.
Back to article page
