Cauchy-Davenport strengthening?

2010-08-29T12:11:10Z

Is the following statement, refining classical Cauchy-Davenport Theorem (that states that for sets $A$, $B$ of residues modulo prime $p$, $|A+B|\geq |A|+|B|-1$ provided that RHS does not exceed $p$) true/known?

Let $A$, $B$ be two subsets of $\mathbb{F}_p$, $p$ being prime, and $|A|+|B|\leq p+1$. Then a complete bipartite graphs with parts $A$, $B$ (rigorously speaking, disjoint copies of $A$ and $B$, say $A\times {0}$ and $B\times{1}$) have a spanning tree such that all $|A|+|B|-1$ edgesums are different. (for edge $e=(a,b)$ its edgesum is defined as $\,a+b$).

Answer by Sergey Norin for Cauchy-Davenport strengthening?

2010-08-29T15:06:50Z

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( E\setminus U) \geq c(U)-1$,

as desired.

Cauchy-Davenport strengthening? - MathOverflow

Cauchy-Davenport strengthening?

Answer by Sergey Norin for Cauchy-Davenport strengthening?