Article contents
Some applications of a theorem of Rado
Published online by Cambridge University Press: 26 February 2010
Extract
It has been shown by Mirsky and Perfect [1] that the theorem of Rado [2], linking matroid theory and transversal theory, has important applications in combinatorial theory. In this note I use it to obtain necessary and sufficient conditions for two families of sets to have a common transversal containing a given set, and then I show how it may be used to obtain a variant of a well-known theorem that was obtained by Hoffman and Kuhn [3] using linear programming methods.
- Type
- Research Article
- Information
- Copyright
- Copyright © University College London 1968
References
1.Mirsky, L. and Perfect, Hazel, “Applications of the notion of independence to problems in combinatorial analysis”, Journ. Comb. Theory, 2 (1967), 327–357.CrossRefGoogle Scholar
2.Rado, R., “A theorem on independence relations”, Quart. J. Math. (Oxford), 13 (1942), 83–89.Google Scholar
3.Hoffman, A. J. and Kuhn, H. W., “On systems of distinct representatives; Linear inequalities and related systems”, Ann. Math. Studies, 38 (Princeton, 1956), 199–206.Google Scholar
4.Mirsky, L. and Perfect, Hazel, “Systems of representatives”, J. Math. Anal, and Appl., 15 (1966), 520–568.Google Scholar
5.Hoffman, A. J. and Kuhn, H. W., “Systems of distinct representatives and linear programming”, Amer. Math. Monthly, 63 (1956), 455–460.Google Scholar
6.Mann, H. B. and Ryser, H. J., “Systems of distinct representatives”, Amer. Math. Monthly, 60 (1953), 397–401.Google Scholar
7.JrFord, L. R.. and Fulkerson, D. R., Flows in Networks (Van Nostrand, Princeton, 1962).Google Scholar
8.Whitney, H., “On the abstract properties of linear dependence”, Amer. J. Math., 57 (1935), 509–533.Google Scholar
10.Edmonds, J. and Fulkerson, D. R., “Transversals and matroid partition”, Journ. N.B.S., 69B (1965), 147–153.Google Scholar
12.Perfect, Hazel, “Some applications of Menger's graph theorem”, J. Math. Anal, and Appl., (to appear).Google Scholar
- 9
- Cited by