additive combinatorics - Cauchy-Davenport strengthening?

I believe that your statement follows from Cauchy-Davenport via matroid intersection theorem. (Matroid intersection theorem is stated in Chapter 41 of Alexander Schrijver's "Combinatorial optimization" book and can be also found here.)

You want to find a "rainbow" spanning tree in a complete bipartite graph you define, where colors correspond to edgesums. "Rainbow" spanning trees, in fact, seem to be commonly used as an example of matroid intersection.

By matroid intersection it suffices to show that for any set of edges $U$ in your graph

$r_1(U)+r_2(E setminus U) geq |A|+|B|-1,$

where:

$E$ is the set of all $|A||B|$ edges,

$r_1(U)$ is the rank of $U$ in the cycle matroid, and is equal to $|A|+|B|-c(U)$ where $c(U)$ is the number of connected components in the graph induced by $U$, and

$r_2(E setminus U)$ is the number of edgesums obtained by the edges not in $U$.

If $c(U)=1$ then we are done. Otherwise, let $A' subseteq A$, $B' subseteq B$ be obtained from $A$ and $B$ by choosing one element from each component of the graph induced by $U$, so that both are non-empty. Then the edges between $A'$ and $B'$ are not in $U$ and thus by Cauchy-Davenport

$r_2( Esetminus U) geq c(U)-1$,

as desired.

• Next zoology - Small worm living in some kind of cocoon, what are these animals?
• Previous pr.probability - order statistics for components of a random unit vector