Sets of unit vectors with small subset sums

Abstract

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|\le 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\ge 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.

41 pages

References in corpus (6)

• Equilateral sets in finite-dimensional normed spaces
• The local Steiner problem in finite-dimensional normed spaces
• Upper bounds for edge-antipodal and subequilateral polytopes
• Cardinalities of k-distance sets in Minkowski spaces
• Extremal Problems in Minkowski Space related to Minimal Networks
• Sets of unit vectors with small pairwise sums

Cited by in corpus (2)

• Combinatorial distance geometry in normed spaces
• Large signed subset sums