Group weighted matchings in bipartite graphs (Q1804248): Difference between revisions

Let \(G\) be a bipartite graph with equal number of vertices of both colours, and \(K\) a (multiplicative) finite abelian group. Let \(M\) denote all mappings \(w:E(G) \rightarrow K\), which have \(w(M)=1\) for each perfect matching of \(G\). (The value \(w(M)\) is the product of all \(w(e), e\in M\).) Finally, \(U\) is the subset of all \(w \in M\) obtained by choosing a function \(\alpha\) on the black vertices of \(G\) and another function \(\beta\) on the white vertices of \(G\), both with values in \(K\), so that the product of all \(\alpha(v)\) and \(\beta(v)\) is \(1\), and letting \(w(a,b)=\alpha(a)\beta(b)\). If \(K\) is the trivial group then it is clear that \(M=U\). The authors prove that if each edge of \(G\) lies in a perfect matching then \(M=U\). (This has been proved earlier for the special case of the two-element group \(K\).) They also prove that if \(G\) is a complete bipartite graph with \(k+1\) vertices of each colour, and \(K\) has \(k\) elements, then for any \(w \in F\), the existence of one perfect matching \(M\) with \(w(M)=1\) implies the existence of at least one other such perfect matching. Finally, the authors consider again the two-element group \(K\), and prove, for any \(w \in F\), if \(G\) has all degrees of white vertices at least \(d\), the existence of one perfect matching \(M\) with \(w(M)=1\) implies the existence of at least \((d-1)!\) such perfect matchings. The last two results are modified for digraphs, and applied to solve a problem of Rinnot on random matrices.