A generalisation of the matroid lift construction

Whittle, Geoff

doi:10.1090/S0002-9947-1989-0957084-1

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

Constructions

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

Economical presentation of matroids by functions

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

The three matroids

Biased graphs

Chromatic and dichromatic invariants

Biased graphs

Geometric realizations

Biased graphs

Universal and topological gains

Biased graphs whose matroids are special binary matroids