Induced matroids

Brualdi, R. A.

doi:10.1090/S0002-9939-1971-0289335-5

Induced matroids
HTML articles powered by AMS MathViewer

by R. A. Brualdi

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

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

PDF | Request permission

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

Richard A. Brualdi, Comments on bases in dependence structures, Bull. Austral. Math. Soc. 1 (1969), 161–167. MR 250914, DOI 10.1017/S000497270004140X
Richard A. Brualdi and Edward B. Scrimger, Exchange systems, matchings, and transversals, J. Combinatorial Theory 5 (1968), 244–257. MR 231727
R. A. Brualdi and J. S. Pym, A general linking theorem in directed graphs, Studies in Pure Mathematics (Presented to Richard Rado), Academic Press, London, 1971, pp. 17–29. MR 0272678
Jack Edmonds and D. R. Fulkerson, Transversals and matroid partition, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 147–153. MR 188090
Frank Harary and Dominic Welsh, Matroids versus graphs, The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) Springer, Berlin, 1969, pp. 155–170. MR 0263666

Representations of independence spaces

Hazel Perfect, Independence spaces and combinatorial problems, Proc. London Math. Soc. (3) 19 (1969), 17–30. MR 241309, DOI 10.1112/plms/s3-19.1.17
Hazel Perfect, Applications of Menger’s graph theorem, J. Math. Anal. Appl. 22 (1968), 96–111. MR 224494, DOI 10.1016/0022-247X(68)90163-7
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
W. T. Tutte, Lectures on matroids, J. Res. Nat. Bur. Standards Sect. B 69B (1965), 1–47. MR 179781
Hassler Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), no. 3, 509–533. MR 1507091, DOI 10.2307/2371182