Erdős Problem #757

declared status 'open'. Formalized: yes. Let $A\subset \mathbb{R}$ be a set of size $n$ such that every subset $B\subseteq A$ with $\lvert B\rvert =4$ has $\lvert B-B\rvert\geq 11$. Find the best constant $c>0$ such that $A$ must always contain a Sidon set of size $\geq cn$. Current best: Erd\H{o}s and S\'{o}s proved that $c\geq 1/2$. Gy\'{a}rf\'{a}s and Lehel [GyLe95] proved$$\frac{1}{2}<c<\frac{3}{5}.$$(The example proving the upper bound is the set of the first $n$ Fibonacci numbers.) References [GyLe95] Gy\'{a}rf\'{a}s, Andr\'{a}s and Lehel, Jen\H{o}, Linear sets with five distinct differences among any four elements. Prize: no. Tags: distances, geometry, sidon sets.

Notation is rendered from the stored source. The pinned checkout remains the exact record.