Back to Search
Start Over
INFINITE MATROIDAL VERSION OF HALL'S MATCHING THEOREM
- Source :
- Journal of the London Mathematical Society. 71:563-578
- Publication Year :
- 2005
- Publisher :
- Wiley, 2005.
-
Abstract
- 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 of finitary matroids, where the matroid 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 of finitary matroids, where the matroid is SCF.
- Subjects :
- Discrete mathematics
Computer Science::Computer Science and Game Theory
Mathematics::Combinatorics
Matching (graph theory)
General Mathematics
Matroid
Combinatorics
Set (abstract data type)
Graphic matroid
Computer Science::Discrete Mathematics
Bipartite graph
Finitary
Rank (graph theory)
Computer Science::Data Structures and Algorithms
Mathematics
Subjects
Details
- ISSN :
- 14697750 and 00246107
- Volume :
- 71
- Database :
- OpenAIRE
- Journal :
- Journal of the London Mathematical Society
- Accession number :
- edsair.doi...........84da35d020cc36b05f9a99deb684b59d