Partial fields in matroid theory

Matroid theory is the study of abstract properties of linear dependence. A matroid consists of a finite set, and a partition of its subsets into "dependent" and "independent" ones. For example, if E is a finite set of vectors in some vector space, then we can define a matroid on E by partitioning the subsets into those that are linearly dependent and those that are linearly independent. Conversely we may ask, for a given matroid, if there exists a set of vectors such that the linearly (in)dependent subsets are precisely those prescribed by the matroid. This is the matroid representation problem. In this thesis we study, using a blend of algebraic, combinatorial, and geometric techniques, matroids that have representations over several distinct fields. Some classes of such matroids have been characterized by the property that, among the representation matrices for each of its members, there is one with special structure: the determinants of all square submatrices are restricted to a certain subset of the field. Semple and Whittle introduced the notion of a partial field to study such characterizations systematically. A partial field is an algebraic structure where multiplication is as usual, but addition is not always defined. The "matrices with special structure" then correspond with "matrices for which all determinants of square submatrices are defined". In Chapter 2 we build up the theory of partial fields. Our definition of a partial field differs from that by Semple and Whittle, and we obtain a number of results more easily. We also propose a generalization to include skew partial fields. There are many ways to construct partial fields. In Chapter 3 we give three examples. The first example is the product partial field, in which we combine several distinct representations of a matroid into one representation over a new partial field. The second construction is the Dowling lift of a partial field, which gives insight in the representability of Dowling geometries. The third construction is the universal partial field of a matroid M, which is the most general partial field over which M is representable. Moreover, any representation of M, over any field, can be derived from it. In Chapter 4 we prove the Lift Theorem, which can be used to characterize sets of matroids representable over a number of fields. For instance, the set of matroids representable over both GF(4) and GF(5) equals the set of matroids representable over R by a matrix for which every subdeterminant is a power of the golden ratio. Let M and N be 3-connected matroids, where N is a minor of M. If M is representable over a partial field, and N is representable over a sub-partial field, then the Confinement Theorem, the main result of Chapter 6, states that either M is representable over the sub-partial field, or there is a small extension of N that is already not representable over the sub-partial field. The Confinement Theorem has a number of applications, including a characterization of the inequivalent representations of quinary matroids. A corollary is the Settlement Theorem. This result combines the theory of universal partial fields with the Confinement Theorem to give conditions under which the number of inequivalent representations of a matroid is bounded by the number of representations of a certain minor. A minor of a representable matroid M is a matroid obtained from M by repeatedly applying certain reductions. An excluded minor for a class of matroids is a matroid that is not in the class, but after any single reduction the resulting matroid is in the class. The most famous conjecture in matroid theory is Rota’s Conjecture, which states that for each prime power q, the set of matroids representable over GF(q) has a finite number of excluded minors. Rota’s Conjecture has been proven only for q = 2, 3, 4. In Chapter 7 we prove a theorem that gives sufficient conditions for the set of excluded minors for the class of matroids representable over a fixed partial field to be finite. We show that this theorem implies the finiteness of the set of excluded minors in all cases that were previously known. Moreover, we indicate how the techniques of this chapter might be applied in the future to yield a proof that there are finitely many excluded minors for the class of matroids representable over GF(5)

• View at Publisher
• View at Worldcat

Free Full Text ( Author Manuscript , 1mb )