Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Induced matroids

Author: R. A. Brualdi
Journal: Proc. Amer. Math. Soc. 29 (1971), 213-221
MSC: Primary 05.35
MathSciNet review: 0289335
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: There are several known results concerning how matroids can be induced from given matroids by a bipartite graph and the properties that are inherited in this way. The purpose of this note is to extend some of these results to the situation where the bipartite graph is replaced by an arbitrary directed graph. We show how a directed graph and a matroid can be used to induce a new matroid. If the initial matroid is strongly base orderable, we prove that the induced matroid is also. In particular, a matroid induced from a free matroid by a directed graph is strongly base orderable. A consequence is that the cycle matroid of the complete graph on four nodes cannot be induced from a free matroid by any directed graph.

References [Enhancements On Off] (What's this?)

  • [1] R. A. Brualdi, Comments on bases in dependence structures, Bull. Austral. Math. Soc. 1 (1969), 161-167. MR 40 #4146. MR 0250914 (40:4146)
  • [2] R. A. Brualdi and E. B. Scrimger, Exchange systems, matchings, and transversals, J. Combinatorial Theory 5 (1968), 244-257. MR 38 #55. MR 0231727 (38:55)
  • [3] R. A. Brualdi and J. S. Pym, A general linking theorem in directed graphs, edited by L. Mirsky, Studies in Pure Mathematics, Academic Press, London and New York, 1971. MR 0272678 (42:7559)
  • [4] J. Edmonds and D. R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 147-153. MR 32 #5531. MR 0188090 (32:5531)
  • [5] F. Harary and D. J. A. Welsh, Matroids versus graphs: The many facets of graph theory, Lecture Notes in Math., no. 110, Springer-Verlag, Berlin, pp. 155-170. MR 0263666 (41:8267)
  • [6] J. H. Mason, Representations of independence spaces, Ph.D. Dissertation, University of Wisconsin, Madison, Wis., 1969.
  • [7] H. Perfect, Independence spaces and combinatorial problems, Proc. London Math. Soc. (3) 19 (1969), 17-30. MR 39 #2649. MR 0241309 (39:2649)
  • [8] -, Applications of Menger's graph theorem, J. Math. Anal. Appl. 22 (1968), 96-111. MR 37 #93. MR 0224494 (37:93)
  • [9] J. S. Pym and H. Perfect, Submodular functions and independence structures, J. Math. Anal. Appl. 30 (1970), 1-37. MR 0263668 (41:8269)
  • [10] W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1-47. MR 31 #4023. MR 0179781 (31:4023)
  • [11] H. Whitney, On the abstract properties of linear dependence, Amer. J. Math. 57 (1935), 509-533. MR 1507091

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05.35

Retrieve articles in all journals with MSC: 05.35

Additional Information

Keywords: Matroid, directed graph, induced matroid, free matroid, cycle matroid, bipartite graph, pairwise node disjoint paths, base orderable matroid, strongly base orderable matroid
Article copyright: © Copyright 1971 American Mathematical Society

American Mathematical Society