On the Schrijver-Seymour Conjecture

On the Schrijver-Seymour Conjecture

-
Matt DeVos, Simon Fraser University
Fine Hall 224

Two interesting classical results in combinatorial number theory are the Erdos-Ginzburg-Ziv Theorem and the Furedi-Kleitman Theorem. Fixing an abelian group $G$ of order $n$, the former asserts that every sequence of $2n+1$ elements of $G$ has a length $n$ subsequence which sums to 0, while the latter asserts that every edge-weighting of a complete graph of order $n+1$ with elements of $G$ has a spanning tree of weight 0.Schrijver and Seymour established a fascinating common generalization of these problems by considering a matroid $M$ with a weighting $w:E(M)\rightarrow G$. In this framework, they conjectured a natural lower bound on the number of distinct weights of bases. In addition to generalizing the above results, their conjecture (if true) would generalize Kneser's addition theorem for abelian groups. Schrijver and Seymour proved their conjecture in the special case when $G$ has prime order, a result which implies the Erdos-Ginzburg-Ziv Theorem, among its numerous consequences. In this talk, I will discuss a proof of the Schrijver-Seymour conjecture in the special case when $M$ is a matroid obtained from a uniform matroid by adding parallel elements. As I will detail, this result has numerous consequences for subsequence sums including two conjectures of Gao, Thangadurai, and Zhuang. This is joint work with B. Mohar and L. Goddyn.