Structure of the convex hull of $n$-dimensional 0/1 vectors with exactly $k$ 1s.

86 Views Asked by At

Let integers $1 \le k \le n$, let $I_{n,k}$ be the subset of binary vectors $v \in \{0,1\}^n$ such that $\sum_{i=1} v_i = k$, and let $\Delta_{n,k}$ be its convex hull.

It is clear that $\Delta_{n,n} = \{1_n\}$ and $\Delta_{n,1} = \Delta_n$ the standard $(n-1)$-dimensional probability simplex.

Question. What is the structure of $\Delta_{n,k}$ for arbitrary $1 < k < n$ ?

By "structure", I mean: dimension, properties, geometry, etc.

1

There are 1 best solutions below

0
On BEST ANSWER

The support vectors are the vertices of the $n$-cube $[0,1]^n$. If you orient that cube with the origin at the bottom and $(1,1,...,1)$ vertically above it. All the vertices with $\sum_i v_i = k$ will be at the same horizontal level., so $\Delta_{n,k}$ will be the intersection of a horizontal hyperplane with that solid hypercube. In general, this will be an $n-1$ dimensional object, except for the degenerate cases $\Delta_{n,0}$ and $\Delta_{n,n}$ (I don't know why you excluded the first but included the second.

The intersections are just simplicies in the hyperplane.