Small subset sums

DOI10.1016/J.LAA.2016.02.035zbMATH Open1337.52006arXiv1502.04027OpenAlexW1594024718MaRDI 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)

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.

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

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

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)

Cites Work

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

Cited In (15)

• Title not available (Why is that?)
• The number of distinct subset sums of a finite set of vectors
• Sets of unit vectors with small subset sums
• Approximation of zonoids by zonotopes
• 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
• Finding a subset of nonnegative vectors with a coordinatewise large sum
• Title not available (Why is that?)
• Balanced partitions of vector sequences
• On the optimality of a theorem of Elton on \(\ell_1^n\) subsystems.
• A colorful Steinitz lemma with application to block-structured integer programs
• Very small 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)