A generalisation of the matroid lift construction

Author:
Geoff Whittle

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

MSC:
Primary 05B35

MathSciNet review:
957084

Full-text PDF Free Access

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]**Claude Berge,*Graphs and hypergraphs*, Second revised edition, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York., 1976. Translated from the French by Edward Minieka; North-Holland Mathematical Library, Vol. 6. MR**0384579****[2]**Tom Brylawski,*Coordinatizing the Dilworth truncation*, Matroid theory (Szeged, 1982) Colloq. Math. Soc. János Bolyai, vol. 40, North-Holland, Amsterdam, 1985, pp. 61–95. MR**843372****[3]**T. Brylawski,*Constructions*, Chapter 7 in [20].**[4]**Collette R. Coullard, John G. del Greco, and Donald K. Wagner,*Representations of bicircular matroids*, Discrete Appl. Math.**32**(1991), no. 3, 223–240. MR**1120878**, 10.1016/0166-218X(91)90001-D**[5]**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****[6]**Jeremy E. Dawson,*Balanced sets in an independence structure induced by a submodular function*, J. Math. Anal. Appl.**95**(1983), no. 1, 214–222. MR**710428**, 10.1016/0022-247X(83)90144-0**[7]**Peter Doubilet, Gian-Carlo Rota, and Richard Stanley,*On the foundations of combinatorial theory. VI. The idea of generating function*, Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971) Univ. California Press, Berkeley, Calif., 1972, pp. 267–318. MR**0403987****[8]**T. A. Dowling,*A class of geometric lattices based on finite groups*, J. Combinatorial Theory Ser. B**14**(1973), 61–86. MR**0307951****[9]**T. A. Dowling and D. G. Kelly,*Elementary strong maps and transversal geometries*, Discrete Math.**7**(1974), 209–224. MR**0329935****[10]**Jack Edmonds and D. R. Fulkerson,*Transversals and matroid partition*, J. Res. Nat. Bur. Standards Sect. B**69B**(1965), 147–153. MR**0188090****[11]**J. Kahn and J. P. S. Kung,*Varieties of combinatorial geometries*, Trans. Amer. Math. Soc.**271**(1982), no. 2, 485–499. MR**654846**, 10.1090/S0002-9947-1982-0654846-9**[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*, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976), NATO Adv. Study Inst. Ser., Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp. 133–176. MR**519783****[14]**Laurence R. Matthews,*Bicircular matroids*, Quart. J. Math. Oxford Ser. (2)**28**(1977), no. 110, 213–227. MR**0505702****[15]**James G. Oxley,*A characterization of the ternary matroids with no 𝑀(𝐾₄)-minor*, J. Combin. Theory Ser. B**42**(1987), no. 2, 212–249. MR**884255**, 10.1016/0095-8956(87)90041-4**[16]**J. S. Pym and Hazel Perfect,*Submodular functions and independence structures*, J. Math. Anal. Appl.**30**(1970), 1–31. MR**0263668****[17]**J. M. S. Simoes-Pereira,*On subgraphs as matroid cells*, Math. Z.**127**(1972), 315–322. MR**0317973****[18]**J. M. S. Simoes-Pereira,*On matroids on edge sets of graphs with connected subgraphs as circuits. II*, Discrete Math.**12**(1975), 55–78. MR**0419275****[19]**D. J. A. Welsh,*Matroid theory*, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. L. M. S. Monographs, No. 8. MR**0427112****[20]**Neil White (ed.),*Theory of matroids*, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986. MR**849389****[21]**Geoff Whittle,*Dowling group geometries and the critical problem*, J. Combin. Theory Ser. B**47**(1989), no. 1, 80–92. MR**1007716**, 10.1016/0095-8956(89)90067-1**[22]**Geoffrey Whittle,*Quotients of Dilworth truncations*, J. Combin. Theory Ser. B**49**(1990), no. 1, 78–86. MR**1056820**, 10.1016/0095-8956(90)90064-7**[23]**Thomas Zaslavsky,*Biased graphs. I. Bias, balance, and gains*, J. Combin. Theory Ser. B**47**(1989), no. 1, 32–52. MR**1007712**, 10.1016/0095-8956(89)90063-4**[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