Large Convex sets in Difference sets

Abstract

We give a construction of a convex set $A\subset \mathbb{R}$ with cardinality $n$ such that $A-A$ contains a convex subset with cardinality $\Omega (n^2)$. We also consider the following variant of this problem: given a convex set $A$, what is the size of the largest matching $M\subset A\times A$ such that the set \[ \{ a-b : (a,b) \in M \} \] is convex? We prove that there always exists such an $M$ with $|M|\ge \sqrt{n}$, and that this lower bound is best possible, up a multiplicative constant.

15 pages