| Title:
|
Symmetrized and continuous generalization of transversals (English) |
| Author:
|
Kochol, Martin |
| Language:
|
English |
| Journal:
|
Mathematica Bohemica |
| ISSN:
|
0862-7959 (print) |
| ISSN:
|
2464-7136 (online) |
| Volume:
|
121 |
| Issue:
|
1 |
| Year:
|
1996 |
| Pages:
|
95-106 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
transversal |
| Keyword:
|
polymatroid |
| Keyword:
|
system of representatives |
| MSC:
|
05B35 |
| MSC:
|
05D15 |
| MSC:
|
52B40 |
| MSC:
|
90C35 |
| idZBL:
|
Zbl 0863.05078 |
| idMR:
|
MR1388181 |
| DOI:
|
10.21136/MB.1996.125937 |
| . |
| Date available:
|
2009-09-24T21:16:18Z |
| Last updated:
|
2020-07-29 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/125937 |
| . |
| Reference:
|
[1] M. Aigner: Combinatorial Theory.Springer, Berlin, 1979. Zbl 0415.05001, MR 0542445 |
| Reference:
|
[2] R. A. Brualdi: Common transversals and strong exchange systems.J. Combin. Theory Ser. B 3 (1970), 307-329. Zbl 0194.00802, MR 0256887 |
| Reference:
|
[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. Zbl 0268.05019, MR 0270945 |
| Reference:
|
[4] J. Edmonds D. R. Fulkerson: Transversals and matroid partitions.J. Res. Nat. Bur. Standards Sect. B 69 (1965), 147-153. MR 0188090 |
| Reference:
|
[5] M. Grötschel L. Lovász A. Schrijver: Geometric Algorithms and Combinatorial Optimization.Springer, Berlin, 1988. MR 0936633 |
| Reference:
|
[6] P. Hall: On representatives of subsets.J. London Math. Soc. 10 (1935), 26-30. Zbl 0010.34503, 10.1112/jlms/s1-10.37.26 |
| Reference:
|
[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 |
| Reference:
|
[8] M. Kochol: The notion and basic properties of M-transversals.Discrete Math. 104 (1991), 191-196. MR 1172847, 10.1016/0012-365X(92)90333-B |
| Reference:
|
[9] M. Kochol: About a generalization of transversals.Math. Bohem. 119 (1994), 143-149. Zbl 0806.05064, MR 1293247 |
| Reference:
|
[10] M. Kochol: Some generalizations of transversal theory.CSc. thesis, Bratislava, 1990. (In Slovak.) |
| Reference:
|
[11] E. L. Lawler C. U. Martel: Computing maximal "polymatroidal" network flows.Math. Oper. Research 7 (1982), 334-347. MR 0667926, 10.1287/moor.7.3.334 |
| Reference:
|
[12] C. J. H. McDiarmid: Rado's theorem for polymatroids.Proc. Cambridge Phil. Soc. 18 (1975), 263-281. Zbl 0321.05028, MR 0379247 |
| Reference:
|
[13] L. Mirsky: Transversal Theory.Academic Press, London, 1971. Zbl 0282.05001, MR 0282853 |
| Reference:
|
[14] L. Mirsky H. Perfect: Applications of the notion of independence to combinatorial analysis.J. Combin. Theory 2 (1967), 327-357. MR 0225675, 10.1016/S0021-9800(67)80034-6 |
| Reference:
|
[15] H. Perfect: Independence spaces and combinatorial problems.Proc. London Math. Soc. 19 (1969), 17-30. Zbl 0176.28302, MR 0241309, 10.1112/plms/s3-19.1.17 |
| Reference:
|
[16] S. Poljak: .Personal communication. Zbl 1167.05028 |
| Reference:
|
[17] R. Rado: A theorem on independence relations.Quart. J. Math. (Oxford) 13 (1942), 83-89. Zbl 0063.06369, MR 0008250, 10.1093/qmath/os-13.1.83 |
| Reference:
|
[18] A. Recski: Matroid Theory and its Applications in Electric Network Theory and in Statics.Springer, Berlin, 1989. Zbl 0729.05012, MR 1027839 |
| Reference:
|
[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. Zbl 0542.90068, MR 0771885 |
| Reference:
|
[20] D. J. A. Welsh: Matroid Theory.Academic Press, London, 1976. Zbl 0343.05002, MR 0427112 |
| Reference:
|
[21] D. R. Woodall: Vector transversals.J. Combin. Theory Ser. B 32 (1982), 189-205. Zbl 0467.05024, MR 0657688, 10.1016/0095-8956(82)90035-1 |
| . |
