An improved bound for the Manickam-Miklós-Singhi conjecture (Q649004): Difference between revisions
From MaRDI portal
Revision as of 17:32, 4 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved bound for the Manickam-Miklós-Singhi conjecture |
scientific article |
Statements
An improved bound for the Manickam-Miklós-Singhi conjecture (English)
0 references
29 November 2011
0 references
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\).
0 references
\(k\)-subsets
0 references
non-negative sums
0 references