Symmetrized and continuous generalization of transversals

Martin Kochol

Mathematica Bohemica (1996)

  • Volume: 121, Issue: 1, page 95-106
  • ISSN: 0862-7959

Abstract

top
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.

How to cite

top

Kochol, Martin. "Symmetrized and continuous generalization of transversals." Mathematica Bohemica 121.1 (1996): 95-106. <http://eudml.org/doc/247973>.

@article{Kochol1996,
abstract = {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.},
author = {Kochol, Martin},
journal = {Mathematica Bohemica},
keywords = {transversal; polymatroid; system of representatives; transversal; polymatroid},
language = {eng},
number = {1},
pages = {95-106},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Symmetrized and continuous generalization of transversals},
url = {http://eudml.org/doc/247973},
volume = {121},
year = {1996},
}

TY - JOUR
AU - Kochol, Martin
TI - Symmetrized and continuous generalization of transversals
JO - Mathematica Bohemica
PY - 1996
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 121
IS - 1
SP - 95
EP - 106
AB - 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.
LA - eng
KW - transversal; polymatroid; system of representatives; transversal; polymatroid
UR - http://eudml.org/doc/247973
ER -

References

top
  1. M. Aigner, Combinatorial Theory, Springer, Berlin, 1979. (1979) Zbl0415.05001MR0542445
  2. R. A. Brualdi, Common transversals and strong exchange systems, J. Combin. Theory Ser. B 3 (1970), 307-329. (1970) Zbl0194.00802MR0256887
  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. (1970) Zbl0268.05019MR0270945
  4. J. Edmonds D. R. Fulkerson, Transversals and matroid partitions, J. Res. Nat. Bur. Standards Sect. B 69 (1965), 147-153. (1965) MR0188090
  5. M. Grötschel L. Lovász A. Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer, Berlin, 1988. (1988) MR0936633
  6. P. Hall, 10.1112/jlms/s1-10.37.26, J. London Math. Soc. 10 (1935), 26-30. (1935) Zbl0010.34503DOI10.1112/jlms/s1-10.37.26
  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. (1990) MR1100058
  8. M. Kochol, 10.1016/0012-365X(92)90333-B, Discrete Math. 104 (1991), 191-196. (1991) MR1172847DOI10.1016/0012-365X(92)90333-B
  9. M. Kochol, About a generalization of transversals, Math. Bohem. 119 (1994), 143-149. (1994) Zbl0806.05064MR1293247
  10. M. Kochol, Some generalizations of transversal theory, CSc. thesis, Bratislava, 1990. (In Slovak.) (1990) 
  11. E. L. Lawler C. U. Martel, 10.1287/moor.7.3.334, Math. Oper. Research 7 (1982), 334-347. (1982) MR0667926DOI10.1287/moor.7.3.334
  12. C. J. H. McDiarmid, Rado's theorem for polymatroids, Proc. Cambridge Phil. Soc. 18 (1975), 263-281. (1975) Zbl0321.05028MR0379247
  13. L. Mirsky, Transversal Theory, Academic Press, London, 1971. (1971) Zbl0282.05001MR0282853
  14. L. Mirsky H. Perfect, 10.1016/S0021-9800(67)80034-6, J. Combin. Theory 2 (1967), 327-357. (1967) MR0225675DOI10.1016/S0021-9800(67)80034-6
  15. H. Perfect, 10.1112/plms/s3-19.1.17, Proc. London Math. Soc. 19 (1969), 17-30. (1969) Zbl0176.28302MR0241309DOI10.1112/plms/s3-19.1.17
  16. S. Poljak, [unknown], Personal communication. Zbl1167.05028
  17. R. Rado, 10.1093/qmath/os-13.1.83, Quart. J. Math. (Oxford) 13 (1942), 83-89. (1942) Zbl0063.06369MR0008250DOI10.1093/qmath/os-13.1.83
  18. A. Recski, Matroid Theory and its Applications in Electric Network Theory and in Statics, Springer, Berlin, 1989. (1989) Zbl0729.05012MR1027839
  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. (1984) Zbl0542.90068MR0771885
  20. D. J. A. Welsh, Matroid Theory, Academic Press, London, 1976. (1976) Zbl0343.05002MR0427112
  21. D. R. Woodall, 10.1016/0095-8956(82)90035-1, J. Combin. Theory Ser. B 32 (1982), 189-205. (1982) Zbl0467.05024MR0657688DOI10.1016/0095-8956(82)90035-1

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.