Suppose that $S$ is a finite set of natural numbers, and $\{(x_i, y_i)\}$ is a set of tuples of numbers in $S$ with $$ \{x_i - y_i\} = S - S := \{a - b \mid a, b \in S\} $$ that is, $\{(x_i, y_i)\}$ "spans" $S - S$. Now, let $S' = \{x_i, y_j\} \subset S$. Is there anything we can say about $|S'|$? Trivially $|S'| > \sqrt{|S|}$, but I can't seem to get anything better. A natural conjecture is that $|S'| > |S|/2$, but I can't seem to get anywhere with that, or indeed, with anything better than the square root estimate.
Edit: The $|S|/2$ conjecture is false, which can be seen by taking $S = \{0, \ldots, 15\}$ and the pairs to be all ordered pairs in $\{0, 1, 2, 7, 11, 14, 15\}$.