A generalisation of the matroid lift construction
HTML articles powered by AMS MathViewer
- by Geoff Whittle PDF
- Trans. Amer. Math. Soc. 316 (1989), 141-159 Request permission
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 $M$, it is necessary (but not sufficient) to have a submodular function inducing $M$. Elementary lifts are obtained when the submodular function chosen is the rank function of $M$. We define what is meant by a $k$-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 $k$-induced matroids using these natural submodular functions is studied. Results on minors of $k$-induced matroids and the matroids obtained from them using the construction are given.References
- Claude Berge, Graphs and hypergraphs, Second revised edition, North-Holland Mathematical Library, Vol. 6, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1976. Translated from the French by Edward Minieka. MR 0384579
- 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 T. Brylawski, Constructions, Chapter 7 in [20].
- 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, DOI 10.1016/0166-218X(91)90001-D
- 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
- 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, DOI 10.1016/0022-247X(83)90144-0
- 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
- T. A. Dowling, A class of geometric lattices based on finite groups, J. Combinatorial Theory Ser. B 14 (1973), 61โ86. MR 307951, DOI 10.1016/s0095-8956(73)80007-3
- T. A. Dowling and D. G. Kelly, Elementary strong maps and transversal geometries, Discrete Math. 7 (1974), 209โ224. MR 329935, DOI 10.1016/0012-365X(74)90036-3
- Jack Edmonds and D. R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 147โ153. MR 188090
- J. Kahn and J. P. S. Kung, Varieties of combinatorial geometries, Trans. Amer. Math. Soc. 271 (1982), no.ย 2, 485โ499. MR 654846, DOI 10.1090/S0002-9947-1982-0654846-9 C. Lintzeris, Economical presentation of matroids by functions, Ph.D. thesis, University of Tasmania, 1987.
- J. H. Mason, Matroids as the study of geometrical configurations, Higher combinatorics (Proc. NATO Advanced Study Inst., Berlin, 1976) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 31, Reidel, Dordrecht-Boston, Mass., 1977, pp.ย 133โ176. MR 519783
- Laurence R. Matthews, Bicircular matroids, Quart. J. Math. Oxford Ser. (2) 28 (1977), no.ย 110, 213โ227. MR 505702, DOI 10.1093/qmath/28.2.213
- James G. Oxley, A characterization of the ternary matroids with no $M(K_4)$-minor, J. Combin. Theory Ser. B 42 (1987), no.ย 2, 212โ249. MR 884255, DOI 10.1016/0095-8956(87)90041-4
- J. S. Pym and Hazel Perfect, Submodular functions and independence structures, J. Math. Anal. Appl. 30 (1970), 1โ31. MR 263668, DOI 10.1016/0022-247X(70)90180-0
- J. M. S. Simoes-Pereira, On subgraphs as matroid cells, Math. Z. 127 (1972), 315โ322. MR 317973, DOI 10.1007/BF01111390
- 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 419275, DOI 10.1016/0012-365X(75)90095-3
- D. J. A. Welsh, Matroid theory, L. M. S. Monographs, No. 8, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1976. MR 0427112
- Neil White (ed.), Theory of matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge University Press, Cambridge, 1986. MR 849389, DOI 10.1017/CBO9780511629563
- Geoff Whittle, Dowling group geometries and the critical problem, J. Combin. Theory Ser. B 47 (1989), no.ย 1, 80โ92. MR 1007716, DOI 10.1016/0095-8956(89)90067-1
- Geoffrey Whittle, Quotients of Dilworth truncations, J. Combin. Theory Ser. B 49 (1990), no.ย 1, 78โ86. MR 1056820, DOI 10.1016/0095-8956(90)90064-7
- Thomas Zaslavsky, Biased graphs. I. Bias, balance, and gains, J. Combin. Theory Ser. B 47 (1989), no.ย 1, 32โ52. MR 1007712, DOI 10.1016/0095-8956(89)90063-4 โ, Biased graphs. II. The three matroids, preprint. โ, Biased graphs. III. Chromatic and dichromatic invariants, preprint. โ, Biased graphs. IV. Geometric realizations, preprint. โ, Biased graphs. V. Universal and topological gains, preprint. โ, Biased graphs whose matroids are special binary matroids, preprint.
Additional Information
- © Copyright 1989 American Mathematical Society
- 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