Connectivity and characteristic polynomials of binary matroids.

摘要

In this dissertation we investigate two main topics: minor-minimally 3-connected matroids and characteristic polynomials. Chapter 1 provides a survey of basic concepts from matroid theory that will be referenced in later chapters. The remainder of this dissertation includes the main results, their proofs, as well as motivation of these results.;A 3-connected matroid M is minor-minimally 3-connected if, for every e ∈ E(M), either Me or M/e is not 3-connected. In Chapter 2, we review several theorems concerning minor-minimally 3-connected matroids. We also consider a conjecture of Wagner, which is the motivation of our research in this area. We provide a counterexample to Wagner's conjecture in this chapter. In Chapter 3 we introduce and prove our main result concerning minor-minimally 3-connected binary matroids. This is a chain-type theorem that offers a characterization of minor-minimally 3-connected binary matroids. As a consequence, one can generate all minor-minimally 3-connected binary matroids starting from M(K4 ), the graphic matroid of the complete graph with four vertices, the Fano matroid F7, and its dual.;The characteristic polynomial of a rank r matroid M with ground set E is defined as cM,x= X⊆E-1 Xxr-r X. The characteristic polynomial PG( x) of a graphic matroid M(G) is related to the chromatic polynomial of G by the equation PGx=xw Gc MG,x where o(G) is the number of components of G. In Chapter 4, we present existing results concerning these polynomials, and we prove a broken-circuit theorem for matroids. In Chapter 5, we give new upper and lower bounds for the coefficients of the characteristic polynomial of simple binary matroids. New bounds for the coefficients of the flow polynomials of graphs can be obtained as a direct consequence.