Cauchy-Davenport strengthening? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T20:48:09Z http://mathoverflow.net/feeds/question/37044 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/37044/cauchy-davenport-strengthening Cauchy-Davenport strengthening? Fedor Petrov 2010-08-29T12:11:10Z 2010-08-29T15:06:50Z <p>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?</p> <p>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$).</p> http://mathoverflow.net/questions/37044/cauchy-davenport-strengthening/37059#37059 Answer by Sergey Norin for Cauchy-Davenport strengthening? Sergey Norin 2010-08-29T15:06:50Z 2010-08-29T15:06:50Z <p>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 <a href="http://www-math.mit.edu/~goemans/18997-CO/co-lec13.ps" rel="nofollow">here</a>.) </p> <p>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.</p> <p>By matroid intersection it suffices to show that for any set of edges $U$ in your graph </p> <p>$r_1(U)+r_2(E \setminus U) \geq |A|+|B|-1,$</p> <p>where: </p> <p>$E$ is the set of all $|A||B|$ edges,</p> <p>$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 </p> <p>$r_2(E \setminus U)$ is the number of edgesums obtained by the edges not in $U$.</p> <p>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</p> <p>$r_2( E\setminus U) \geq c(U)-1$,</p> <p>as desired. </p>