Small subset sums

DOI10.1016/J.LAA.2016.02.035MaRDI QIDQ269528zbMATH OpenOpenAlexFDO

Authors Gergely Ambrus, Imre Bárány, V. S. Grinberg

Publication date 18 April 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.04027

zbMATH Keywords

normed spacesSteinitz theoremvector sums

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Convexity and finite-dimensional Banach spaces (including special norms, zonoids, etc.) (aspects of convex geometry) (52A21)

Abstract: Let ||.|| be a norm in R^d whose unit ball is B. Assume that Vsubset B is a finite set of cardinality n, with sum_{v in V} v=0. We show that for every integer k with 0 le k le n, there exists a subset U of V consisting of k elements such that | sum_{v in U} v | le lceil d/2 ceil. We also prove that this bound is sharp in general. We improve the estimate to O(sqrt d) for the Euclidean and the max norms. An application on vector sums in the plane is also given.

Recommendations

• LARGE SIGNED SUBSET SUMS
• Sums of finite subsets in \(\mathbb{R}^d\)
• Solution of the Littlewood-Offord problem in high dimensions
• The number of distinct subset sums of a finite set of vectors
• Dominating subsets under projections

Cites work

• scientific article; zbMATH DE number 4086369 (Why is no real title available?)
• scientific article; zbMATH DE number 3708084 (Why is no real title available?)
• scientific article; zbMATH DE number 699467 (Why is no real title available?)
• Balancing vectors in the max norm
• EXTREMAL PROPERTIES OF ORTHOGONAL PARALLELEPIPEDS AND THEIR APPLICATIONS TO THE GEOMETRY OF BANACH SPACES
• Helly type theorems for the sum of vectors in a normed plane
• On a geometric problem of Erdoes, Sarkoezy, and Szemeredi concerning vector sums
• On some combinatorial questions in finite-dimensional spaces
• On the Power of Linear Dependencies
• Six Standard Deviations Suffice
• Value of the Steinitz constant

Cited in

(15)

• scientific article; zbMATH DE number 1975224 (Why is no real title available?)
• The number of distinct subset sums of a finite set of vectors
• Approximation of zonoids by zonotopes
• Sets of unit vectors with small subset sums
• Additive colourful Carathéodory type results with an application to radii
• Zero-sum subsequences in bounded-sum \(\{-1,1\}\)-sequences
• On series of signed vectors and their rearrangements
• LARGE SIGNED SUBSET SUMS
• Sequences with small subsum sets
• scientific article; zbMATH DE number 17611 (Why is no real title available?)
• Finding a subset of nonnegative vectors with a coordinatewise large sum
• Balanced partitions of vector sequences
• On the optimality of a theorem of Elton on \(\ell_1^n\) subsystems.
• Very small sets
• A colorful Steinitz lemma with application to block-structured integer programs

This page was built for publication: Small subset sums

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