On sum-free subsequences
HTML articles powered by AMS MathViewer
- by S. L. G. Choi, J. Komlós and E. Szemerédi PDF
- Trans. Amer. Math. Soc. 212 (1975), 307-313 Request permission
Abstract:
A subsequence of a sequence of n distinct integers is said to be sum-free if no integer in it is the sum of distinct integers in it. Let $f(n)$ denote the largest quantity so that every sequence of n distinct integers has a sum-free subsequence consisting of $f(n)$ integers. In this paper we strengthen previous results by Erdös, Choi and Cantor by proving \[ (n \log n/\log \log n)^{1/2} \ll f(n) \ll n (\log n)^{-1}. \]References
- P. Erdős, Extremal problems in number theory, Proc. Sympos. Pure Math., Vol. VIII, Amer. Math. Soc., Providence, R.I., 1965, pp. 181–189. MR 0174539
- S. L. G. Choi, The largest sum-free subsequence from a sequence of $n$ numbers, Proc. Amer. Math. Soc. 39 (1973), 42–44. MR 313216, DOI 10.1090/S0002-9939-1973-0313216-3 D. Cantor (to appear).
- S. L. G. Choi, On sequences not containing a large sum-free subsequence, Proc. Amer. Math. Soc. 41 (1973), 415–418. MR 325563, DOI 10.1090/S0002-9939-1973-0325563-X
- V. Chvátal and J. Komlós, Some combinatorial theorems on monotonicity, Canad. Math. Bull. 14 (1971), 151–157. MR 337676, DOI 10.4153/CMB-1971-028-8
Additional Information
- © Copyright 1975 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 212 (1975), 307-313
- MSC: Primary 10L05
- DOI: https://doi.org/10.1090/S0002-9947-1975-0376594-1
- MathSciNet review: 0376594