research-article

A Note on the Erdös Distinct Subset Sums Problem

Authors: Quentin Dubroff, Jacob Fox, Max Wenqiang XuAuthors Info & Claims

SIAM Journal on Discrete Mathematics, Volume 35, Issue 1

Pages 322 - 324

Published: 01 January 2021 Publication History

Abstract

We present two short proofs giving the best known asymptotic lower bound for the maximum element in a set of $n$ positive integers with distinct subset sums.

References

[1]

I. Aliev, Siegel's lemma and sum-distinct sets, Discrete Comput. Geom., 39 (2008), pp. 59--66.

Google Scholar

[2]

N. Alon and J. H. Spencer, The Probabilistic Method, 4th ed., Wiley, Hoboken, NJ, 2016.

Google Scholar

[3]

J. Bae, On subset-sum-distinct sequences, in Analytic Number Theory, vol. 1, Progr. Math. 138, Birkhäuser, Boston, 1996, pp. 31--37.

Google Scholar

[4]

T. Bohman, A construction for sets of integers with distinct subset sums, Electron. J. Combin., 5 (1998), Research Paper 3.

Google Scholar

[5]

N. D. Elkies, An improved lower bound on the greatest element of a sum-distinct set of fixed order, J. Combin. Theory Ser. A, 41 (1986), pp. 89--94.

Google Scholar

[6]

P. Erdös, Problems and results in additive number theory, in Colloque sur la Théorie des Nombres, Bruxelles, 1955, George Thone, Liège; Masson and Cie, Paris, 1956, pp. 127--137.

Google Scholar

[7]

R. K. Guy, Sets of integers whose subsets have distinct sums, in Theory and Practice of Combinatorics, North-Holland Math. Stud. 60, Ann. Discrete Math. 12, North-Holland, Amsterdam, 1982, pp. 141--154.

Google Scholar

[8]

R. K. Guy, Unsolved Problems in Intuitive Mathematics, vol. I, Number Theory, Springer-Verlag, 1981, Problem C8.

Google Scholar

[9]

L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory, 1 (1966), pp. 385--393.

Google Scholar

[10]

I. G. Shevtsova, An improvement of convergence rate estimates in the Lyapunov theorem, Dokl. Math., 82 (2010), pp. 862--864.

Google Scholar

[11]

D. J. Kleitman, Extremal hypergraph problems, in Surveys in combinatorics, Proc. Seventh British Combinatorial Conf., Cambridge, 1979, London Math. Soc. Lecture Note Ser. 38, Cambridge Univ. Press, Cambridge-New York, 1979, pp. 44--65.

Google Scholar

[12]

I. Leader, Discrete isoperimetric inequalities, in Probabilistic combinatorics and its applications (San Francisco, CA, 1991), Proc. Sympos. Appl. Math. 44, AMS Short Course Lecture Notes, Amer. Math. Soc., Providence, RI, 1991, pp. 57--80.

Google Scholar

Cited By

View all

Berndt SMnich MStamm T(2024)New Support Size Bounds and Proximity Bounds for Integer Linear ProgrammingSOFSEM 2024: Theory and Practice of Computer Science10.1007/978-3-031-52113-3_6(82-95)Online publication date: 19-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-52113-3_6
Mehmet Kilic KSima JBruck J(2022)On Algebraic Constructions of Neural Networks with Small Weights2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834401(3007-3012)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834401

Recommendations

A linear bound on the Manickam-Miklós-Singhi conjecture

Suppose that we have a set S of n real numbers which have nonnegative sum. How few subsets of S of order k can have nonnegative sum__ __ Manickam, Miklós, and Singhi conjectured that for n 4 k the answer is ( n - 1 k - 1 ) . This conjecture is known to ...
Variations on the Erdős distinct-sums problem
Abstract
Let { a 1 , . . . , a n } be a set of positive integers with a 1 < ⋯ < a n such that all 2 n subset sums are distinct. A famous conjecture by Erdős states that a n > c ⋅ 2 n for some constant c, while the best result known to date is ...
Randomized Construction of Complexes with Large Diameter
Abstract
We consider the question of the largest possible combinatorial diameter among pure dimensional and strongly connected $(d - 1)$ -dimensional simplicial complexes on n vertices, denoted $H_{s} (n, d)$ . Using a probabilistic construction we give a new lower ... $_{}$ $^{}$ $^{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Discrete Mathematics

SIAM Journal on Discrete Mathematics Volume 35, Issue 1

DOI:10.1137/sjdmec.35.1

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 January 2021

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Berndt SMnich MStamm T(2024)New Support Size Bounds and Proximity Bounds for Integer Linear ProgrammingSOFSEM 2024: Theory and Practice of Computer Science10.1007/978-3-031-52113-3_6(82-95)Online publication date: 19-Feb-2024
https://dl.acm.org/doi/10.1007/978-3-031-52113-3_6
Mehmet Kilic KSima JBruck J(2022)On Algebraic Constructions of Neural Networks with Small Weights2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834401(3007-3012)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834401

Abstract

References

Cited By

Recommendations

A linear bound on the Manickam-Miklós-Singhi conjecture

Variations on the Erdős distinct-sums problem

Randomized Construction of Complexes with Large Diameter

Comments

Information

Published In

Publisher

Publication History

Author Tags

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations