DIMACS Discrete Math/Theory of Computing Seminar


Bipartite matchings and abelian groups


Roy Meshulam
Technion, Israel


Seminar Room 431, CoRE Building,
Rutgers University


4:30 PM
Tuesday, September 17, 1996

Let $G$ be a bipartite graph, and let $w$ be a weight function on the edges which takes values in a finite abelian group $K$. A perfect matching of $G$ is a $w$-{\it matching} if the product of the weights of its edges is 1.

We'll give a lower bound on the number of w-matchings and a characterization of all $w$'s for which every perfect matching is a $w$-matching, and describe some connections with the zero-sum problem in abelian groups.

Document last modified on September 17, 1996