A generalisation of the matroid lift construction

Author:
Geoff Whittle

Journal:
Trans. Amer. Math. Soc. **316** (1989), 141-159

MSC:
Primary 05B35

DOI:
https://doi.org/10.1090/S0002-9947-1989-0957084-1

MathSciNet review:
957084

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: This paper introduces a general matroid-theoretic construction which includes, as special cases, elementary lifts of matroids and bias matroids of biased graphs. To perform the construction on a matroid , it is necessary (but not sufficient) to have a submodular function inducing . Elementary lifts are obtained when the submodular function chosen is the rank function of .

We define what is meant by a -*induced* matroid. These matroids simultaneously generalise matroids of graphs, transversal matroids and Dilworth truncations. They are induced by a particularly natural class of submodular functions. The effect of the above construction on -induced matroids using these natural submodular functions is studied. Results on minors of -induced matroids and the matroids obtained from them using the construction are given.

**[1]**C. Berge,*Graphs and hypergraphs*, North-Holland, Amsterdam, 1976. MR**0384579 (52:5453)****[2]**T. Brylawski,*Coordinatizing the Dilworth truncation*, in Matroid Theory (L. Lovász and A. Recski, eds.), Colloq. Math. Soc. János Bolyai, no. 40, North-Holland, Amsterdam, 1985. MR**843372 (87h:05059)****[3]**T. Brylawski,*Constructions*, Chapter 7 in [20].**[4]**C. R. Coullard, J. G. del Greco and D. K. Wagner,*Representations of bicircular matroids*, preprint. MR**1120878 (92i:05072)****[5]**H. H. Crapo and G.-C. Rota,*On the foundations of combinatorial theory: Combinatorial geometries*, M.I.T. Press, Cambridge, Mass., 1970. MR**0290980 (45:74)****[6]**J. E. Dawson,*Balanced sets in an independence structure induced by a submodular function*, J. Math. Anal. Appl.**95**(1983), 214-222. MR**710428 (84k:05030)****[7]**P. Doubilet, G.-C. Rota and R. Stanley,*On the foundations of combinatorial theory*(IV):*The idea of generating functions*, Proc. Sixth Berkeley Sympos. on Mathematical Statistics and Probability, Berkeley, 1970/1971, vol. 11, Probability Theory, Univ. of California Press, Berkeley, Calif., 1972, pp. 276-318. MR**0403987 (53:7796)****[8]**T. A. Dowling,*A class of geometric lattices based on finite groups*, J. Combin. Theory Ser. B**14**(1973), 61-86. MR**0307951 (46:7066)****[9]**T. A. Dowling and D. G. Kelly,*Elementary strong maps and transversal geometries*, Discrete Math.**7**(1974), 209-224. MR**0329935 (48:8275)****[10]**J. Edmunds and D. R. Fulkerson,*Transversals and matroid partitions*, J. Res. Nat. Bur. Standards B**69**(1965), 147-153. MR**0188090 (32:5531)****[11]**J. Kahn and J. P. S. Kung,*Varieties of combinatorial geometries*, Trans. Amer. Math. Soc.**271**(1982), 485-499. MR**654846 (84j:05043)****[12]**C. Lintzeris,*Economical presentation of matroids by functions*, Ph.D. thesis, University of Tasmania, 1987.**[13]**J. H. Mason,*Matroids as the study of geometrical configurations*, in Higher Combinatorics (M. Aigner, ed.), Reidel, Dordrecht, 1977. MR**519783 (80k:05037)****[14]**L. R. Matthews,*Bicircular matroids*, Quart. J. Math. Oxford Ser. (2)**28**(1977), 213-228. MR**0505702 (58:21732)****[15]**J. G. Oxley,*A characterization of the ternary matroids with no*-*minor*, J. Combin. Theory Ser. B**42**(1987), 212-249. MR**884255 (88d:05039)****[16]**J. S. Pym and H. Perfect,*Submodular functions and independence structures*, J. Math. Anal. Appl.**30**(1970), 1-31. MR**0263668 (41:8269)****[17]**J. M. S. Simões-Pereira,*On subgraphs as matroid cells*, Math. Z.**127**(1972), 315-322. MR**0317973 (47:6522)****[18]**-,*On matroids on edge sets of graphs with connected subgraphs as circuits*. II, Discrete Math.**12**(1975), 55-78. MR**0419275 (54:7298)****[19]**D. J. A. Welsh,*Matroid theory*, London Math. Soc. Monographs, No. 8, Academic Press, New York, 1976. MR**0427112 (55:148)****[20]**N. L. White, ed.,*Theory of matroids*(Encyclopedia of Math. and Its Applications), Cambridge Univ. Press, Cambridge, 1986. MR**849389 (87k:05054)****[21]**G. P. Whittle,*Dowling group geometries and the critical problem*, J. Combin. Theory Ser. B (to appear). MR**1007716 (90g:51008)****[22]**-,*Quotients of Dilworth truncations*, J. Combin. Theory Ser. B (to appear). MR**1056820 (91c:05059)****[23]**T. Zaslavsky, Biased graphs. I.*Bias, balance and gains*, preprint. MR**1007712 (90k:05138)****[24]**-,*Biased graphs*. II.*The three matroids*, preprint.**[25]**-,*Biased graphs*. III.*Chromatic and dichromatic invariants*, preprint.**[26]**-,*Biased graphs*. IV.*Geometric realizations*, preprint.**[27]**-,*Biased graphs*. V.*Universal and topological gains*, preprint.**[28]**-,*Biased graphs whose matroids are special binary matroids*, preprint.

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

Retrieve articles in all journals with MSC: 05B35

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1989-0957084-1

Article copyright:
© Copyright 1989
American Mathematical Society