Article
Full entry |
PDF
(0.6 MB)
Feedback
PDF
(0.6 MB)
Feedback
Keywords:
transversal; polymatroid; system of representatives
transversal; polymatroid; system of representatives
Summary:
The theorem of Edmonds and Fulkerson states that the partial transversals of a finite family of sets form a matroid. The aim of this paper is to present a symmetrized and continuous generalization of this theorem.
References:
[1] M. Aigner: Combinatorial Theory. Springer, Berlin, 1979. MR 0542445 | Zbl 0415.05001
[2] R. A. Brualdi: Common transversals and strong exchange systems. J. Combin. Theory Ser. B 3 (1970), 307-329. MR 0256887 | Zbl 0194.00802
[3] J. Edmonds: Submodular functions, matroids and certain polyhedra. Combinatorial structures and their applications (R. Guy, H. Hanani, N. Sauer, J. Schonheim, eds.). Gordon and Breach, New York, 1970, pp. 69-87. MR 0270945 | Zbl 0268.05019
[4] J. Edmonds D. R. Fulkerson: Transversals and matroid partitions. J. Res. Nat. Bur. Standards Sect. B 69 (1965), 147-153. MR 0188090
[5] M. Grötschel L. Lovász A. Schrijver: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin, 1988. MR 0936633
[6] P. Hall: On representatives of subsets. J. London Math. Soc. 10 (1935), 26-30. DOI 10.1112/jlms/s1-10.37.26 | Zbl 0010.34503
[7] P. Horák: Transversals and matroids. Topics in Combinatorics and Graph Theory (R. Bodendiek, R. Henn, eds.). Physica-Verlag, Heidelberg, 1990, pp. 381-389. MR 1100058
[8] M. Kochol: The notion and basic properties of M-transversals. Discrete Math. 104 (1991), 191-196. DOI 10.1016/0012-365X(92)90333-B | MR 1172847
[9] M. Kochol: About a generalization of transversals. Math. Bohem. 119 (1994), 143-149. MR 1293247 | Zbl 0806.05064
[10] M. Kochol: Some generalizations of transversal theory. CSc. thesis, Bratislava, 1990. (In Slovak.)
[11] E. L. Lawler C. U. Martel: Computing maximal "polymatroidal" network flows. Math. Oper. Research 7 (1982), 334-347. DOI 10.1287/moor.7.3.334 | MR 0667926
[12] C. J. H. McDiarmid: Rado's theorem for polymatroids. Proc. Cambridge Phil. Soc. 18 (1975), 263-281. MR 0379247 | Zbl 0321.05028
[13] L. Mirsky: Transversal Theory. Academic Press, London, 1971. MR 0282853 | Zbl 0282.05001
[14] L. Mirsky H. Perfect: Applications of the notion of independence to combinatorial analysis. J. Combin. Theory 2 (1967), 327-357. DOI 10.1016/S0021-9800(67)80034-6 | MR 0225675
[15] H. Perfect: Independence spaces and combinatorial problems. Proc. London Math. Soc. 19 (1969), 17-30. DOI 10.1112/plms/s3-19.1.17 | MR 0241309 | Zbl 0176.28302
[16] S. Poljak: Personal communication. Zbl 1167.05028
[17] R. Rado: A theorem on independence relations. Quart. J. Math. (Oxford) 13 (1942), 83-89. DOI 10.1093/qmath/os-13.1.83 | MR 0008250 | Zbl 0063.06369
[18] A. Recski: Matroid Theory and its Applications in Electric Network Theory and in Statics. Springer, Berlin, 1989. MR 1027839 | Zbl 0729.05012
[19] A. Schrijver: Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions. Progress in Combinatorial Optimization (W. R. Pulleyblank, ed.). Academic Press, Toronto, 1984, pp. 315-362. MR 0771885 | Zbl 0542.90068
[20] D. J. A. Welsh: Matroid Theory. Academic Press, London, 1976. MR 0427112 | Zbl 0343.05002
[21] D. R. Woodall: Vector transversals. J. Combin. Theory Ser. B 32 (1982), 189-205. DOI 10.1016/0095-8956(82)90035-1 | MR 0657688 | Zbl 0467.05024
Search
Partner of
