DIMACS Discrete Math/Theory of Computing Seminar


Title:

Bipartite matchings and abelian groups

Speaker:

Roy Meshulam
Technion, Israel

Place:

Seminar Room 431, CoRE Building,
Rutgers University

Time:

4:30 PM
Tuesday, September 17, 1996
Abstract:

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