Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Sets of unit vectors with small subset sums


Author: Konrad J. Swanepoel
Journal: Trans. Amer. Math. Soc. 368 (2016), 7153-7188
MSC (2010): Primary 52A37; Secondary 05C15, 15A03, 15A45, 46B20, 49Q10, 52A21, 52A40, 52A41
DOI: https://doi.org/10.1090/tran/6601
Published electronically: January 20, 2016
MathSciNet review: 3471088
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We say that a family $ \{\mathbold {x}_i \,\vert \, i\in [m]\}$ of vectors in a Banach space $ X$ satisfies the $ k$-collapsing condition if $ \Vert\sum _{i\in I}\mathbold {x}_i\Vert\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\mathbold {x}_i=\mathbold {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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 52A37, 05C15, 15A03, 15A45, 46B20, 49Q10, 52A21, 52A40, 52A41

Retrieve articles in all journals with MSC (2010): 52A37, 05C15, 15A03, 15A45, 46B20, 49Q10, 52A21, 52A40, 52A41


Additional Information

Konrad J. Swanepoel
Affiliation: Department of Mathematics, London School of Economics and Political Science, Houghton Street, London WC2A 2AE, United Kingdom
Email: k.swanepoel@lse.ac.uk

DOI: https://doi.org/10.1090/tran/6601
Received by editor(s): February 9, 2014
Received by editor(s) in revised form: September 10, 2014
Published electronically: January 20, 2016
Additional Notes: An extended version of this paper is available at arXiv:1210.0366
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society