Vol. 41, No. 3, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 331: 1  2
Vol. 330: 1  2
Vol. 329: 1  2
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Online Archive
Volume:
Issue:
     
The Journal
About the journal
Ethics and policies
Peer-review process
 
Submission guidelines
Submission form
Editorial board
Officers
 
Subscriptions
 
ISSN 1945-5844 (electronic)
ISSN 0030-8730 (print)
 
Special Issues
Author index
To appear
 
Other MSP journals
Transversal matroids and Hall’s theorem

Richard Anthony Brualdi and John H. Mason

Vol. 41 (1972), No. 3, 601–613
Abstract

Transversal matroids, not necessarily having finite character, are investigated. It is demonstrated that if U(I) = (Ai : i I) is an arbitrary family of subsets of an arbitrary set E whose transversal matroid has at least one basis and has no coloops, then A(I) has a transversal; in fact, each basis is a transversal of A(I) but of no proper subfamily of A(I). P. Hall’s theorem on the existence of a transversal for a finite family, and indeed an extension of it, can be obtained from this result.

Some necessary conditions for a matroid to be a transversal matroid are derived. One of these is that a transversal matroid of rank r can have at most (r)
k k-flats having no coloops (1 k r).

Mathematical Subject Classification 2000
Primary: 05B35
Milestones
Received: 31 March 1970
Revised: 25 May 1971
Published: 1 June 1972
Authors
Richard Anthony Brualdi
John H. Mason