Joint colloquium with Pure Mathematics

Additive Number Theory, Graphs and Matroids

Abstract:

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.