Hostname: page-component-586b7cd67f-tf8b9 Total loading time: 0 Render date: 2024-11-24T11:39:23.302Z Has data issue: false hasContentIssue false
  • English
  • Français

Some applications of a theorem of Rado

Published online by Cambridge University Press:  26 February 2010

D. J. A. Welsh
D. J. A. Welsh
Affiliation:
Merton College, Oxford, and The University of Michigan
Get access

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
Mathematika , Volume 15 , Issue 2 , December 1968 , pp. 199 - 203
Copyright
Copyright © University College London 1968

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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
9.Tutte, W. T., “Lectures on matroids”, Journ. N.B.S., 69B (1965), 1–48.Google Scholar
10.Edmonds, J. and Fulkerson, D. R., “Transversals and matroid partition”, Journ. N.B.S., 69B (1965), 147–153.Google Scholar
11.Ore, O., “Graphs and matching theorems”, Duke Math. Journ., 22 (1955), 625–639.Google Scholar
12.Perfect, Hazel, “Some applications of Menger's graph theorem”, J. Math. Anal, and Appl., (to appear).Google Scholar