An improved bound for the Manickam-Miklós-Singhi conjecture

DOI10.1016/J.EJC.2011.07.006MaRDI QIDQ649004zbMATH OpenOpenAlexWikidataFDO

Authors Mykhaylo Tyomkyn

Publication date 29 November 2011

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-subsetsnon-negative sums

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Other combinatorial number theory (11B75)

Abstract: We show that for $n>k(4elogk{)}^k$ every set $x_1,\mathrm{...},x_n$ of $n$ real numbers with $su{m}_{i=0}^n{x}_{i}geq0$ has at least $$ $k$-element subsets of a non-negative sum. This is a substantial improvement on the best previously known bound of $n>(k-1)(k^k+k^2)+k$, proved by Manickam and Mikl'os cite{MM} in 1987.

Review text

Let us denote by \(\mathcal X\) the set of arbitrary \(n\) real numbers whose sum is non-negative. The following question naturally arises: At least how many subsets of \(\mathcal X\) have a non-negative sum? The answer is \(2^{n-1}\), and it is easy to see that this bound is tight. As a continuation of this topic it is worth observing what happens if only sets of fixed size are observed. Namely, what is the minimal number of non-negative \(k\)-wise sums? This is still an open question examined by many mathematicians among the author of this paper. Let \(A(n,k)\) be the minimal number of non-negative \(k\)-sums for all possible \(\mathcal{X} \in \mathbb{R}^{(n)}\). \textit{N. Manickam} and \textit{D. Miklós} [in: Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 385--392 (1988; Zbl 0726.11014)] and, in a little bit different way, \textit{N. Manickam} and \textit{N. M. Singhi} [J. Comb. Theory, Ser. A 46, No. 1, 91--103 (1988; Zbl 0645.05023)] made the following conjecture: For all \(n \geq 4k\) we have \(A(n,k)= \binom{n-1}{k-1}\). Manickam and Miklós provided a number of results in order to back up this conjecture. For example that it holds for \(k=2 \text{ and } 3\) or that for every \(k\) there exists a positive integer \(n_k\) such that for all \(n \geq n_k\) we have \(A(n,k)= \binom{n-1}{k-1}\). Let us denote by \(f(k)\) the minimal such \(n_k\). The aim of Tyomkyn is to give a new upper bound for \(f(k),\) since the best known bound was \((k-1)(k^{k}+k^{2})+k\) (proved by Manickam and Miklós), which is far from \(4k.\) In this paper in order to illustrate a new method it is shown that if \(n \geq 3k^{k+1}+k^3\), then the number of non-negative \(k\)-wise sums of \(\mathcal X\) is at least \(\binom{n-1}{k-1}\). With the help of this new technique, as the main result it is proved that \(f(k) \leq k^2(4e \log k)^k\), in other words, \(A(n,k)= \binom{n-1}{k-1}\), if \(n > k^2(4e \log k)^k\).

Recommendations

• A linear bound on the Manickam-Miklós-Singhi conjecture
• A note on the Manickam-Miklós-Singhi conjecture
• On a conjecture of Manickam and Singhi
• New results related to a conjecture of Manickam and Singhi
• An improved bound in Vizing's conjecture
• A linear programming approach to the Manickam-Miklós-Singhi conjecture
• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• An improved lower bound related to the Furstenberg-Sárközy theorem
• An improved upper bound for the Erdős-Szekeres conjecture
• Improved bounds on a generalization of Tuza's conjecture

Cites work

• A method to count the positive 3-subsets in a set of real numbers with non-negative sum
• First distribution invariants and EKR theorems
• scientific article; zbMATH DE number 4198073 (Why is no real title available?)
• scientific article; zbMATH DE number 4106864 (Why is no real title available?)
• scientific article; zbMATH DE number 3478938 (Why is no real title available?)
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• New results related to a conjecture of Manickam and Singhi
• On a conjecture of Manickam and Singhi
• On a problem concerning the weight functions
• The first distribution invariant of the Johnson-scheme

Cited in

(17)

• On a conjecture of Manickam and Singhi
• A remark on the problem of nonnegative k-subset sums
• On the number of nonnegative sums for semi-partitions
• A generalization of Alon-Aydinian-Huang theorem
• On the number of nonnegative sums for certain function
• A linear bound on the Manickam-Miklós-Singhi conjecture
• The adjacency matrix of a graph as a data table: a geometric perspective
• A linear programming approach to the Manickam-Miklós-Singhi conjecture
• New results related to a conjecture of Manickam and Singhi
• A note on the Manickam-Miklós-Singhi conjecture
• Positive sum systems
• The minimum number of nonnegative edges in hypergraphs
• Nonnegative \(k\)-sums, fractional covers, and probability of small deviations
• Solution of a problem on non-negative subset sums
• The Manickam-Miklós-Singhi conjectures for sets and vector spaces
• On the number of nonnegative sums
• A class of lattices and Boolean functions related to the Manickam-Miklös-Singhi conjecture

This page was built for publication: An improved bound for the Manickam-Miklós-Singhi conjecture

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