Vol. 41, No. 3, 1972

Download this article
Download this article. For screen
For printing
Recent Issues
Vol. 329: 1
Vol. 328: 1  2
Vol. 327: 1  2
Vol. 326: 1  2
Vol. 325: 1  2
Vol. 324: 1  2
Vol. 323: 1  2
Vol. 322: 1  2
Online Archive
The Journal
About the journal
Ethics and policies
Peer-review process
Submission guidelines
Submission form
Editorial board
ISSN: 1945-5844 (e-only)
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

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
Received: 31 March 1970
Revised: 25 May 1971
Published: 1 June 1972
Richard Anthony Brualdi
John H. Mason