Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$).

share|improve this question
    
Fedor, I've never seen such a strengthening of CD, can you give a hint towards the proof? –  Gjergji Zaimi Aug 29 '10 at 13:56
    
>I've never seen me too! –  Fedor Petrov Aug 29 '10 at 15:49
    
Sergey's proof is both short and elegant. –  Fedor Petrov Aug 29 '10 at 18:37
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
    
Thanks, that's really nice argument! It is true at least, which is good itself. I would however care for independent inductive proof, which would lead to another combinatorial proof of CD (and so, maybe, to combinatorial proofs of some analogues like Erdos-Heilbronn conjecture). Your argument shows that we may try to prove usual CD assuming inductive propose even for this version. –  Fedor Petrov Aug 29 '10 at 18:37
1  
+1 Another instance of matroids taking over the world. –  Tony Huynh Aug 30 '10 at 9:43
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.