Sets of unit vectors with small subset sums

Abstract:

We say that a family $\{\mathbfit {x}_i \,\vert \, i\in [m]\}$ of vectors in a Banach space $X$ satisfies the $k$-collapsing condition if $\|\sum _{i\in I}\mathbfit {x}_i\|\leq 1$ for all $k$-element subsets $I\subseteq \{1,2,\dots ,m\}$. Let $\overline {\mathcal {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 $\overline {\mathcal {CB}}(k,d)$ denote the maximum cardinality if we require in addition that $\sum _{i=1}^m\mathbfit {x}_i=\mathbfit {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 $\overline {\mathcal {CB}}(k,d)=\max \{k+1,2d\}$ for all $k,d\geq 2$. The behaviour of $\overline {\mathcal {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 $\overline {\mathcal {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.