On the Number of Group-Weighted Matchings
Jeff Kahn
and Roy Meshulam
DOI: 10.1023/A:1008671206536
Abstract
Let G be a bipartite graph with a bicoloration {A,B}, |A|=|B|. Let E(G) 
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) K be a weight assignment on the edges of G. FOr S E(G) let w(S) = 
e 
Sw(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.
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) K be a weight assignment on the edges of G. FOr S E(G) let w(S) = e Sw(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) 
d for all a A, then either G has no w-matchings, or G has at least (d - k + 1)! w-matchings.
d for all a A, then either G has no w-matchings, or G has at least (d - k + 1)! w-matchings.Pages: 285–290
Keywords: bipartite matching; digraph; finite abelian group; group algebra; olson”s theorem
Full Text: PDF
References
1. R. Aharoni, R. Meshulam, and B. Wajnryb, “Group weighted matching in bipartite graphs,” J. Alg. Combin. 4 (1995), 165-171.
2. P.C. Baayen, “Een combinatorisch probleem voor eindige Abelse groepen,” Math. Centrum Syllabus 5, Colloquium Discrete Wiskunde Caput 3, Math. Centre Amsterdam, 1968.
3. R.C. Baker and W.M. Schmidt, “Diophantine problems in variables restricted to the values 0 and 1,” J. Number Theory 12 (1980), 460-486.
4. F.R.K. Chung, P. Frankl, R. Graham, and J.B. Shearer, “Some intersection theorems for ordered sets and graphs,” J. Combinatorial Theory Ser. A 48 (1986), 23-37.
5. P. van Emde Boas and D. Kruyswijk, “A combinatorial problem on finite abelian groups III,” Z.W. 1969-008 (Math. Centrum, Amsterdam).
6. R. Faudree, R. Schelp, and V.T. Sós, “Some intersection theorems on two-valued functions,” Combinatorica 6 (1986), 327-333. P1: ICA Journal of Algebraic Combinatorics KL559-04-Kahn February 24, 1998 9:10 290 KAHN AND MESHULAM
7. Z. F\ddot uredi, J.R. Griggs, R. Holzman, and D.J. Kleitman, “Representations of families of triples over G F (2),” J. Combinatorial Theory Ser. A 53 (1990), 306-315.
8. J. Griggs and J. Walker, “Anticlusters and intersecting families of subsets,” J. Combinatorial Theory Ser. A 51 (1989), 90-103.
9. L. Lovász, Combinatorial Problems and Exercises, North-Holland, New York, 1979.
10. R. Meshulam, “An uncertainty inequality and zero subsums,” Discrete Math. 84 (1990), 197-200.
11. J.E. Olson, “A combinatorial problem on finite abelian groups I,” J. Number Theory 1 (1969), 8-10.
12. D.S. Passman, The Algebraic Structure of Group Rings, Wiley-Interscience, New York, 1977.
2. P.C. Baayen, “Een combinatorisch probleem voor eindige Abelse groepen,” Math. Centrum Syllabus 5, Colloquium Discrete Wiskunde Caput 3, Math. Centre Amsterdam, 1968.
3. R.C. Baker and W.M. Schmidt, “Diophantine problems in variables restricted to the values 0 and 1,” J. Number Theory 12 (1980), 460-486.
4. F.R.K. Chung, P. Frankl, R. Graham, and J.B. Shearer, “Some intersection theorems for ordered sets and graphs,” J. Combinatorial Theory Ser. A 48 (1986), 23-37.
5. P. van Emde Boas and D. Kruyswijk, “A combinatorial problem on finite abelian groups III,” Z.W. 1969-008 (Math. Centrum, Amsterdam).
6. R. Faudree, R. Schelp, and V.T. Sós, “Some intersection theorems on two-valued functions,” Combinatorica 6 (1986), 327-333. P1: ICA Journal of Algebraic Combinatorics KL559-04-Kahn February 24, 1998 9:10 290 KAHN AND MESHULAM
7. Z. F\ddot uredi, J.R. Griggs, R. Holzman, and D.J. Kleitman, “Representations of families of triples over G F (2),” J. Combinatorial Theory Ser. A 53 (1990), 306-315.
8. J. Griggs and J. Walker, “Anticlusters and intersecting families of subsets,” J. Combinatorial Theory Ser. A 51 (1989), 90-103.
9. L. Lovász, Combinatorial Problems and Exercises, North-Holland, New York, 1979.
10. R. Meshulam, “An uncertainty inequality and zero subsums,” Discrete Math. 84 (1990), 197-200.
11. J.E. Olson, “A combinatorial problem on finite abelian groups I,” J. Number Theory 1 (1969), 8-10.
12. D.S. Passman, The Algebraic Structure of Group Rings, Wiley-Interscience, New York, 1977.
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition