A solution to a strengthened conjecture of Bukh, van Hintum and Keevash on additive bases

Motivated by the change-of-domain problem for additive bases, Bukh, van Hintum and Keevash conjectured that if $A,B\subseteq {\mathbb{Q}}^n$ and $\{{\mathit{e}}_i+{\mathit{e}}_j:1\le i\le j\le n\}\subseteq A+B,$ then $\mathrm{\mid }A\mathrm{\mid }+\mathrm{\mid }B\mathrm{\mid }\ge 2n$. They further proposed the strengthened conjecture: if $\mathrm{\mid }A\mathrm{\mid }=n-t$, then $\mathrm{\mid }B\mathrm{\mid }\ge n+\left(\genfrac{}{}{0px}{}{t+1}{2}\right)\mathrm{.}$ Bukh also explicitly asked whether the same bounds hold for $A,B\subseteq {\mathbb{R}}^n$ and an arbitrary basis $S$ of ${\mathbb{R}}^n$, under the assumption $S+S\subseteq A+B$. We prove the full strengthened statement over ${\mathbb{R}}^n$: if $S+S\subseteq A+B$ and $\mathrm{\mid }A\mathrm{\mid }\le n-t$ with $0\le t\le n-1$, then $\mathrm{\mid }B\mathrm{\mid }\ge n+\left(\genfrac{}{}{0px}{}{t+1}{2}\right),$ which is sharp for every basis $S$ and every $0\le t\le n-1.$ The proof is short, using edge contractions in a graph-theoretical framework and a new coloring lemma over ${\mathbb{F}}_2^n$.