On the interplay between graphs and matroids

Publication date 17 February 2002

binary matroid connectivity graph independent set matroid theory uniform matroid

Combinatorial aspects of matroids and geometric lattices (05B35)

The main goal of this paper is to give a pedagogical introduction to the subject of interplay between graphs and matroids. It is primary intended for graduate students and specialists who are interested in graphs, linear algebra, matroids, coding theory and their applications. This paper should be accessible for any reader with some background in graph theory and linear algebra. The basic ideas and techniques are treated in detail, including examples. This is a renew version of some chapters of the author's book [Matroid theory (Oxford Science Publications. Oxford: Oxford University Press) (1992; Zbl 0784.05002)]. Also it includes recent results on matroids. The organization of the paper is as follows: 1. Introduction. 2. The bare facts about matroids. 3. Connectedness, 2-connectedness, and unavoidable structures. 4. Some proofs. 5. Removable circuits. 6. Removing circuits from 3-connected matroids. 7. Minors and infinite antichains. 8. Branch-width and infinite antichains. 9. The implication of large branch-width. 10. Some proof outlines. 11. Unavoidability revisited. NEWLINENEWLINENEWLINEThe material of the paper is outlined in the titles of sections and informally discussed in the introduction. Section 2 gives an admirable straightforward introduction to the basics of matroid theory. ``Section 3 begins by showing how 2-connectedness for graphs extends naturally to matroids. It then indicates how the number of edges in a 2-connected loopless graph can be bounded in terms of the circumference and the size of a largest bond. The main result of the section extends this graph result to matroids. Section 4 outlines the proofs of the main results from Section 3. In Sections 5-6 the author describes verious extensions and non-extensions for 2-connected graphs and matroids in a 1974 theorem of \textit{W. Mader} [Abh. Math. Semin. Univ. Hamb. 42, 187-204 (1974; Zbl 0266.05111)]. The graph minors project by \textit{N. Robertson} and \textit{P. D. Seymour} [Surveys in combinatorics 1985, Lond. Math. Soc. Lect. Note Ser. 103, 153-171 (1985; Zbl 0568.05025)] and a longstanding matroid conjecture of \textit{G.-C. Rota} [Actes Congr. Internat. Math. 1970, 229-233 (1971; Zbl 0362.05044)] motivate in particular Sections 7-10. The paper ends with a comprehensive list of references, arranged alphabetically. NEWLINENEWLINENEWLINEThis excellent paper will be of interest to graduate students and researches in graph, matroid and coding theory.NEWLINENEWLINEFor the entire collection see [Zbl 0964.00035].

Recommendations

Cited in

(22)

This page was built for publication: On the interplay between graphs and matroids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2741178)