Group weighted matchings in bipartite graphs (Q1804248): Difference between revisions
From MaRDI portal
Removed claims |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / author | |||
Property / author: Ron Aharoni / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Roy Meshulam / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Bronisław Wajnryb / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Pavol Hell / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Special parity of perfect matchings in bipartite graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Diophantine problems in variables restricted to the values 0 and 1 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5656945 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3880849 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An uncertainty inequality and zero subsums / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A combinatorial problem on finite Abelian groups. I / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Disjoint cycles in digraphs / rank | |||
Normal rank |
Latest revision as of 14:23, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Group weighted matchings in bipartite graphs |
scientific article |
Statements
Group weighted matchings in bipartite graphs (English)
0 references
25 September 1997
0 references
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.
0 references
bipartite matching
0 references
abelian group
0 references
edge labels
0 references