Induced matroids

Author:
R. A. Brualdi

Journal:
Proc. Amer. Math. Soc. **29** (1971), 213-221

MSC:
Primary 05.35

DOI:
https://doi.org/10.1090/S0002-9939-1971-0289335-5

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.

**[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**

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

Retrieve articles in all journals with MSC: 05.35

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1971-0289335-5

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