Geodesic
On the number of group-weighted matchings
Journal of Algebraic Combinatorics, Tome 7 (1998) no. 3, pp. 285-290.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: Let G be a bipartite graph with a bicoloration ${A,B}$, |A|=|B|. Let $E(G)rarr$ A x B denote the edge set of G, and let $m(G)$ denote the number of perfect matchings of G. Let K be a (multiplicative) finite abelsian group |K| = k, and let w:$E(G)rarr$ K be a weight assignment on the edges of G. FOr S $rarrE(G)$ let $w(S) = prod _{e $isin$S}w(e)$. A perfect matching M of G is a w-matching if $w(M)=1$. We shall be interested in $m(G,w)$, the number of w-matchings of G. It is shown that if $deg(a)ge$ d for all a $isin$ A, then either G has no w-matchings, or G has at least (d - k + 1)! w-matchings.
Keywords: bipartite matching, digraph, finite abelian group, group algebra, olson"s theorem 
@article{JAC_1998__7_3_a2,
     author = {Kahn, Jeff and Meshulam, Roy},
     title = {On the number of group-weighted matchings},
     journal = {Journal of Algebraic Combinatorics},
     pages = {285--290},
     publisher = {mathdoc},
     volume = {7},
     number = {3},
     year = {1998},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a2/}
}
TY  - JOUR
AU  - Kahn, Jeff
AU  - Meshulam, Roy
TI  - On the number of group-weighted matchings
JO  - Journal of Algebraic Combinatorics
PY  - 1998
SP  - 285
EP  - 290
VL  - 7
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a2/
LA  - en
ID  - JAC_1998__7_3_a2
ER  - 
%0 Journal Article
%A Kahn, Jeff
%A Meshulam, Roy
%T On the number of group-weighted matchings
%J Journal of Algebraic Combinatorics
%D 1998
%P 285-290
%V 7
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a2/
%G en
%F JAC_1998__7_3_a2
Kahn, Jeff; Meshulam, Roy. On the number of group-weighted matchings. Journal of Algebraic Combinatorics, Tome 7 (1998) no. 3, pp. 285-290. http://geodesic.mathdoc.fr/item/JAC_1998__7_3_a2/