H. Aydinian, V. M. Blinovsky, “A remark on the problem of nonnegative <nobr>$k$</nobr>-subset sums”, Probl. Peredachi Inf., 2012, Volume 48, Issue 4,Pages <nobr>56

This article is cited in 3 papers

Large Systems

A remark on the problem of nonnegative $k$-subset sums

H. Aydinian^a, V. M. Blinovsky^ab

^a Department of Mathematics, University of Bielefeld, Germany
^b Kharkevich Institute for Information Transmission Problems, Russian Academy of Sciences, Moscow

Abstract: Given a set of $n$ real numbers with a nonnegative sum, consider the family of all its $k$-element subsets with nonnegative sums. How small can the size of this family be? We show that this problem is closely related to a problem raised by Ahlswede and Khachatrian in [1]. The latter, in a special case, is nothing else but the problem of determining a minimal number $c_n(k)$ such that any $k$-uniform hypergraph on $n$ vertices having $c_n(k)+1$ edges has a perfect fractional matching. We show that results obtained in [1] can be applied for the former problem. Moreover, we conjecture that these problems have in general the same solution.

UDC: 621.391.1+519.1

Received: 20.06.2012
Revised: 31.07.2012