Sets of unit vectors with small subset sums

was considered by F"uredi, 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

C B (k, d) = m a x k + 1, 2 d

for all

k, d g e q 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) = m a x k + 1, 2 d

in certain cases. We use a variety of tools from graph theory, convexity and linear algebra in the proofs: in particular the Hajnal-Szemer'edi Theorem, the Brunn-Minkowski inequality, and lower bounds for the rank of a perturbation of the identity matrix.

Review text

Given a finite-dimensional real Banach space \(X\), a family \((x_i)_{i=1}^m\) of vectors in \(X\) is said to satisfy the \(k\)-collapsing condition \((2\leq k\leq m)\) if \(\big\|\sum_{i\in I}x_i\big\|\leq 1\) holds for all \(k\)-elemental subsets \(I\) of \(\{1,\dots,m\}\). The family is said to satisfy the strong balancing condition if \(\sum_{i=1}^mx_i=0\). Such conditions originally arose in the paper of \textit{G. Lawlor} and \textit{F. Morgan} [Pac. J. Math. 166, No. 1, 55--83 (1994; Zbl 0830.49028)] in the context of Steiner trees in finite-dimensional spaces.NEWLINENEWLINEThe author defines \(C_k(X)\) to be the maximal number \(m\) for which a family \((x_i)_{i=1}^m\) in \(X\) exists which satisfies the \(k\)-collapsing condition and \(\| x_i\|\geq 1\) for each \(i\). \(CB_k(X)\) is defined analogously but with the additional requirement that the family also satisfies the strong balancing condition. He further defines \(\overline{C}(k,d)\) (\(\overline{CB}(k,d)\)) to be the maximum of \(C_k(X)\) (\(CB_k(X)\)) over all \(d\)-dimensional real Banach spaces \(X\).NEWLINENEWLINEThe author proves that \(\overline{CB}(k,d)=\max\{k+1,2d\}\) for all \(k,d\geq 2\).NEWLINENEWLINEThe case of \(\overline{C}(k,d)\) turns out to be much more difficult. The author proves several results bounding \(\overline{C}(k,d)\) from above and below for different ranges of values of \(k\) and \(d\).NEWLINENEWLINEIn the proofs, he uses various results from different fields, such as the Brunn-Minkowski inequality, the Hajnal-Szemerédi theorem on equitable graph colourings, Carathéodory's theorem, and a lemma from linear algebra on a lower bound for the rank of a matrix.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Sets of unit vectors with small subset sums

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796088)