Search Results

This chapter examines graphic matroids in more detail. In particular, it presents several proofs delayed from Chapters 1 and 2, including proofs that a graphic matroid is representable over every field, and that a cographic matroid M*(G) is graphic only if G is planar. The main result of the chapter is Whitney's 2-Isomorphism Theorem, which establishes necessary and sufficient conditions for two graphs to have isomorphic cycle matroids.

This chapter provides an overview of the basic questions associated with matroid representability and indicates how one actually goes about constructing representations. The key ideas are presented in Sections 6.1 and 6.3–6.6, which cover projective geometries, different matroid representations, constructing representations for matroids, representability over finite fields, and regular matroids, respectively. Section 6.2 looks at affine geometries, a class of highly symmetric structures that are closely linked to the projective geometries of Section 6.1. Section 6.7 discusses algebraic matroids, a class of matroids that properly contains the class of representable matroids and arises from algebraic dependence over a field. Section 6.8 focuses on characteristic sets, its main idea being concerned with how one can capture geometrically certain algebraic properties of a field. Section 6.9 examines modularity, a special property of flats that is important in several contexts including matroid constructions. Finally, Section 6.10 discusses an important class of matroids introduced by Dowling.

This chapter is organized as follows. Section 10.1 presents Gerards' (1989) proof of Tutte's (1958) excluded-minor characterization of the class of regular matroids. Section 10.2 proves the ternary-matroid result by modifying the proof of Tutte's (1958) excluded-minor characterization of the class of regular matroids. Section 10.3 focuses on graphic matroids and proves Tutte's (1959) excluded-minor characterization of the class of graphic matroids.

This chapter considers several more matroid constructions. The chapter is organized as follows. Section 11.2 considers several applications of submodular functions, one of which is in the proof of Hall's Marriage Theorem, a result that specifies precisely when a family of sets has a transversal. Section 11.3 discusses the operation of matroid union and presents several of its attractive applications. Section 11.4 considers the problem of sticking two matroids together across a common restriction. Much of the discussion there focuses on a generalization of the operation of parallel connection. The last operation is used in Section 11.5 to define a matroid generalization of the graph operation of Δ-Y exchange.