Premium
Infinite Matroidal Version of Hall's Matching Theorem
Author(s) -
Wojciechowski Jerzy
Publication year - 2005
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/s0024610705006320
Subject(s) - finitary , matroid , bipartite graph , combinatorics , mathematics , matching (statistics) , graphic matroid , discrete mathematics , rank (graph theory) , countable set , graph , statistics
Hall's theorem for bipartite graphs gives a necessary and sufficient condition for the existence of a matching in a given bipartite graph. Aharoni and Ziv have generalized the notion of matchability to a pair of possibly infinite matroids on the same set and given a condition that is sufficient for the matchability of a given pair ( M, W ) of finitary matroids, where the matroid M is SCF (a sum of countably many matroids of finite rank). The condition of Aharoni and Ziv is not necessary for matchability. The paper gives a condition that is necessary for the existence of a matching for any pair of matroids (not necessarily finitary) and is sufficient for any pair ( M, W ) of finitary matroids, where the matroid M is SCF.