Weighted join semilattices and transversal matroids

Brualdi, Richard A.

doi:10.1090/S0002-9947-1974-0382039-7

Weighted join semilattices and transversal matroids
HTML articles powered by AMS MathViewer

by Richard A. Brualdi PDF

Trans. Amer. Math. Soc. 191 (1974), 317-328 Request permission

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

Garrett Birkhoff, Lattice theory, 3rd ed., American Mathematical Society Colloquium Publications, Vol. XXV, American Mathematical Society, Providence, R.I., 1967. MR 0227053
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 286690, DOI 10.1093/qmath/22.3.435
Richard A. Brualdi and George W. Dinolt, Characterizations of transversal matroids and their presentations, J. Combinatorial Theory Ser. B 12 (1972), 268–286. MR 304210, DOI 10.1016/0095-8956(72)90041-x
Henry H. Crapo and Gian-Carlo Rota, On the foundations of combinatorial theory: Combinatorial geometries, Preliminary edition, The M.I.T. Press, Cambridge, Mass.-London, 1970. MR 0290980
Hassler Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), no. 3, 509–533. MR 1507091, DOI 10.2307/2371182