Additive Number Theory and the Cacetta-Haggkvist Conjecture

The Cacetta-Haggkvist conjecture states that if G is a finite directed graph with n vertices and outdegree at least n/k at each vertex, then the graph contains a directed cycle of length at most k. An addition theorem of Kemperman for product sets in nonabelian groups can be applied to prove the conjecture for Cayley graphs, and, more generally, for arbitrary vertex-transitive graphs. Some related results in the intersection of graph theory and additive number theory will also be discussed.

Mel Nathanson