On the number of group-weighted matchings (Q1386528): Difference between revisions

Let \(G\) be a bipartite graph with bipartition \(\{A, B\}\), where \(| A| = | B| \). Let \(K\) be a finite abelian group with \(k\) elements, and let \(w : E(G) \rightarrow K\) be a weight assignment on the edges of \(G\). For a subset \(S\) of the edge set of \(G\), let \(w(S)\) denote the product of the weights of the edges in \(S\). A perfect matching \(M\) is a \(w\)-matching if \(w(M) = 1\). The authors show that if \(\text{deg} (a) \geq d\) for all \(a \in A\), then either \(G\) has no \(w\)-matchings or \(G\) has at least \((d-k+1)!\) \(w\)-matchings.