Additive Number Theory, Graphs and Matroids
|Affiliation:||University of Waterloo|
|Room:||Mathematics and Computer Building (MC) 6486|
Cauchy in 1813 and Davenport in 1935 proved the following fundamental result in Additive Number Theory: given prime p and two subsets A and B of Z_p, the number of elements produced as a sum of an element from A and an element from B is at least the minimum of p and |A|+|B|-1. In 1990, Bialostocki and Dierker added a graph theoretic flavour to the field by showing the following: in a complete graph on p+1 vertices where each edge has a weight in Z_p, there is always a zero-sum spanning tree.
In this talk, I will give an overview of these results, and bring to your attention a beautiful conjecture of Schrijver and Seymour that ties together these two results, along with many other results of Kneser, Erdos-Ginzburg-Ziv, Grynkiewicz, Furedi and Kleitman, etc. Vaguely speaking, the conjecture provides a lower bound on the number of bases of different weights in a matroid, given an arbitrary weighting of its edges from an arbitrary abelian group.
I will also discuss a major recent work of DeVos, Goddyn and Mohar, where they prove the conjecture for a special class of matroids.
200 University Avenue West
Waterloo, ON N2L 3G1