Sets of unit vectors with small subset sums

We say that a family ${x_i|i\in[m]}$ of vectors in a Banach space $X$ satisfies the $k$-collapsing condition if $|\sum_{i\in I}x_i|\leq 1$ for all $k$-element subsets $I\subseteq{1,2,...,m}$. Let $C(k,d)$ denote the maximum cardinality of a $k$-collapsing family of unit vectors in a $d$\dimensional Banach space, where the maximum is taken over all spaces of dimension $d$. Similarly, let $CB(k,d)$ denote the maximum cardinality if we require in addition that $\sum_{i=1}^m x_i=o$. The case $k=2$ was considered by Füredi, Lagarias and Morgan (1991). These conditions originate in a theorem of Lawlor and Morgan (1994) on geometric shortest networks in smooth finite-dimensional Banach spaces. We show that $CB(k,d)=\max{k+1,2d}$ for all $k,d\geq 2$. The behaviour of $C(k,d)$ is not as simple, and we derive various upper and lower bounds for various ranges of $k$ and $d$. These include the exact values $C(k,d)=\max{k+1,2d}$ in certain cases. We use a variety of tools from graph theory, convexity and linear algebra in the proofs: in particular the Hajnal-Szemerédi Theorem, the Brunn-Minkowski inequality, and lower bounds for the rank of a perturbation of the identity matrix.

No reviews yet.

No comments yet.