Small subset sums

DOI10.1016/J.LAA.2016.02.035zbMATH1337.52006OpenAlexW1594024718MaRDI QIDQ269528FDOQ269528

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

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)