Sets of unit vectors with small subset sums
type: Item
instance of: scholarly article
title: Sets of unit vectors with small subset sums
zbMATH Open document ID: 1355.46020
author: Konrad J. Swanepoel
published in: Transactions of the American Mathematical Society
publication date: 2016-03-23T00:00:00Z
full work available at URL: https://arxiv.org/abs/1210.0366
full work available at URL: lse.ac.uk storage LIBRARY Secondary libfile shared repository Content Swanepoel, K Swanepoel Set Unit Vectors Swanepoel Set Unit Vectors 2014.pdf
Mathematics Subject Classification ID: 46B20
Mathematics Subject Classification ID: 52A21
Mathematics Subject Classification ID: 52A40
Mathematics Subject Classification ID: 52A41
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 15A03
Mathematics Subject Classification ID: 15A45
zbMATH DE Number: 6559887
zbMATH Keywords: finite-dimensional Banach spaces
zbMATH Keywords: collapsing condition
zbMATH Keywords: strong balancing condition
zbMATH Keywords: graph colourings
zbMATH Keywords: Brunn-Minkowski inequality
zbMATH Keywords: matrices
zbMATH Keywords: rank
MaRDI profile type: Publication
OpenAlex ID: W2256839718
arXiv ID: 1210.0366
cites work: Problems and results in extremal combinatorics. I.
cites work: Perturbed Identity Matrices Have High Rank: Proof and Applications
cites work: On (ε,k)‐min‐wise independent permutations
cites work: Equilateral sets in \(l_p^n\)
cites work: Automorphisms of the extended affine root system and modular property for the flat theta invariants
cites work: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes
cites work: On the Steiner Problem
cites work: Some structural properties of low-rank matrices related to computational complexity
cites work: Q5673381
cites work: Deterministic constructions of compressed sensing matrices
cites work: Q4114435
cites work: Q4011312
cites work: OPTIMAL SMOOTHING FOR CONVEX POLYTOPES
cites work: Q5620621
cites work: Q5791470
cites work: Q4069280
cites work: Inequalities for the Distribution of the Length of Random Vector Sums
cites work: Sums of vectors and Turan's problem for 3-graphs
cites work: ?Best? estimations on the distribution of the length of sums of two random vectors
cites work: Q3746576
cites work: Q4657583
cites work: A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
cites work: Paired calibrations applied to soap films, immiscible fluids, and surfaces or networks minimizing other norms
cites work: The geometry of Minkowski spaces -- a survey. I
cites work: A Remark on Stirling's Formula
cites work: Lower bounds for local versions of dimension reductions
cites work: Q3939810
cites work: One class of extremal geometric constants and their applications
cites work: Extremal problems in Minkowski space related to minimal networks
cites work: Vertex degrees of Steiner minimal trees in \(\ell_p^d\) and other smooth Minkowski spaces
cites work: Sets of unit vectors with small pairwise sums
cites work: Q4676063
cites work: The local Steiner problem in finite-dimensional normed spaces
cites work: Upper bounds for edge-anitpodal and subequilateral polytopes
DOI: 10.1090/TRAN/6601
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.
reviewed by: Jan-David Hardtke
description: scientific article; zbMATH DE number 6559887