Title : Integer Sets Having the Maximum Number of Distinct Differences
Speaker : Oleg Pikhurko
When : 4:30-5:30pm, April 5th
Where : Physical Plant Building(PPB) Room #300
Abstract:
We consider the function $D(k,n)$ which is the maximum of $ |A-A|=|\{a-b \mid a,b\in A\}| $ over all $k$-subsets $A$ of $[n]=\{0,\ldots,n\}$. In other words, we want to maximize the number of distinct differences that a $k$-subset of $[n]$ can have. The range of interest is when $k$ is of order $\sqrt n$. A few well-known problems from additive number theory can be restated in terms of the function $D(k,n)$.
We show that for any fixed real $c\ge 0$ and any function $k(n)=(c+o(1))\sqrt n$ the limit $ d(c)=\lim_{n\to\infty} \frac{D(k(n),n)}n $ exists. We present upper and lower bounds on $d(c)$, outlining (mostly combinatorial) proofs. A few other versions of the problem, such as maximizing the number of distinct sums, will be considered as well.
Some of the presented results are joint work with B\’ela Bollob\’as and with Tomasz Schoen.
