← All problems

Erdős Problem #862 — Number of Maximal Sidon Sets

1 year old · traced to

For a positive integer NN, write [N]={1,…,N}[N]=\{1,\ldots,N\}. A subset S⊆[N]S\subseteq[N] is Sidon if equality of two sums of pairs of its elements forces the pairs to be equal, with pairs understood as unordered and repetitions allowed. It is inclusion-maximal if no strictly larger Sidon subset of [N][N] contains it; this does not require it to have maximum cardinality. Let A1(N)A_1(N) be the number of such inclusion-maximal subsets. Is it true that

log⁡2A1(N)=o(N)(N→∞),\log_2 A_1(N)=o(\sqrt N)\qquad(N\to\infty),

that is, that log⁡2A1(N)/N→0\log_2 A_1(N)/\sqrt N\to0? Erdős Problems #862

Background

The question sits alongside the classical enumeration problem of Cameron and Erdős: how many Sidon subsets does an interval contain? This is distinct from counting inclusion-maximal ones. The distinction matters because every Sidon set can be extended to a maximal one, while a maximal set can contain many Sidon subsets. Cameron and Erdős also considered maximal members of other families of integer sets. Kohayakawa, Lee, Rödl and Samotij, The Number of Sidon Sets Cameron and Erdős, Notes on sum-free and related sets

The relevant scale comes from the extremal size of a Sidon subset of an interval: if F(N)F(N) denotes the largest possible size, then F(N)=(1+o(1))NF(N)=(1+o(1))\sqrt N. Thus a single maximal Sidon set has at most 2(1+o(1))N2^{(1+o(1))\sqrt N} subsets. Enumeration of all Sidon sets on the exponential-in-N\sqrt N scale can therefore yield information about how many maximal sets there are. Kohayakawa, Lee, Rödl and Samotij, The Number of Sidon Sets Saxton and Thomason, Hypergraph containers

References

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.