Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Weighted join semilattices and transversal matroids

Author: Richard A. Brualdi
Journal: Trans. Amer. Math. Soc. 191 (1974), 317-328
MSC: Primary 05B35
MathSciNet review: 0382039
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: We investigate join-semilattices in which each element is assigned a nonnegative weight in a strictly increasing way. A join-subsemilattice of a Boolean lattice is weighted by cardinality, and we give a characterization of these in terms of the notion of a spread. The collection of flats with no coloops (isthmuses) of a matroid or pregeometry, partially ordered by set-theoretic inclusion, forms a join-semilattice which is weighted by rank. For transversal matroids these join-semilattices are isomorphic to join-subsemilattices of Boolean lattices. Using a previously obtained characterization of transversal matroids and results on weighted join-semilattices, we obtain another characterization of transversal matroids. The problem of constructing a transversal matroid whose join-semilattice of flats is isomorphic to a given join-subsemilattice of a Boolean lattice is then investigated.

References [Enhancements On Off] (What's this?)

  • [1] G. Birkhoff, Lattice theory, 3rd ed., Amer. Math. Soc. Colloq. Publ., vol. 25, Amer. Math. Soc., Providence, R. I., 1967. MR 37 #2638. MR 0227053 (37:2638)
  • [2] J. A. Bondy and D. J. A. Welsh, Some results on transversal matroids and constructions for identically self-dual matroids, Quart. J. Math. Oxford Ser. (2) 22 (1971), 435-451. MR 44 #3899. MR 0286690 (44:3899)
  • [3] R. A. Brualdi and G. W. Dinolt, Characterizations of transversal matroids and their presentations, J. Combinatorial Theory 12 (1972), 268-286. MR 0304210 (46:3345)
  • [4] H. Crapo and G. C. Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, M. I. T. Press, Cambridge, Mass., 1970. MR 45 #74. MR 0290980 (45:74)
  • [5] H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57 (1935), 509-533. MR 1507091

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05B35

Retrieve articles in all journals with MSC: 05B35

Additional Information

Keywords: Weighted semilattice, spread, Boolean lattice, transversal matroid
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society