Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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

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 $ 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 [Enhancements On Off] (What's this?)

  • [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 $ M({K_4})$-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.

Similar Articles

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

Retrieve articles in all journals with MSC: 05B35

Additional Information

Article copyright: © Copyright 1989 American Mathematical Society

American Mathematical Society