Largest Sidon subsets in weak Sidon sets

Abstract

A finite set $S\subset \mathbb{R}$ is called a Sidon set if all sums $x+y$ with $x,y\in S$ and $x\le y$ are distinct, and a weak Sidon set if all sums $x+y$ with $x,y\in S$ and $x<y$ are distinct. For a finite set $A\subset \mathbb{R}$, let $h(A)$ denote the maximum size of a Sidon subset of $A$, and define $$g(n):=\min \{h(A):A\subset \mathbb{R},|A|=n,A\text{ is a weak Sidon set}\}.$$ Sárközy and Sós asked whether the limit ${\lim }_{n\to \infty }g(n)/n$ exists and, if so, to determine its value. We resolve this problem completely by determining $g(n)$ exactly: $$g(n)=\lceil \frac{n+1}{2}\rceil \text{for all }n\ge 1.$$ In particular, ${\lim }_{n\to \infty }g(n)/n=\frac{1}{2}$. We also investigate a related problem of Erdős concerning a local difference condition. A finite set $A\subset \mathbb{R}$ is called a $(4,5)$-set if every $4$-element subset of $A$ determines at least five distinct values among its six pairwise absolute differences. Erdős asked for the optimal constant $c_{\ast }>0$ such that every $(4,5)$-set of size $n$ contains a Sidon subset of size at least $c_{\ast }n$. Gyárfás and Lehel reduced this to an extremal problem of $3$-uniform hypergraphs and proved $\frac{1}{2}+\frac{1}{141\cdot 76}\le c_{\ast }\le \frac{3}{5}$. We improve both bounds by establishing $$\frac{9}{17}\le c_{\ast }\le \frac{4}{7},$$ where the lower bound uses a reformulation of the extremal problem, and the upper bound follows from an explicit construction together with a convenient characterization of $c_{\ast }$.

arXiv comment15 pages. This is the submitted version