Some problems in combinatorial theory: with particular reference to induced matroids

Thesis

In Chapter 1 it is shown that transversal matroids and strictgammoids are dual matroids, and hence that Hall's and Menger's Theorems are dual theorems. Corollaries are the results on minimal and maximal presentations of transversal matroids. It is suggested by the proofs that the correct context in which to study transversal matroids is by considering the dual pair of matroids. The maximal presentation of an infinite independence structure is shown to be unique. Finally, Dilworth's Theorem is derived from Hall's Theorem by a similar method to the derivation of Menger's Theorem.

Chapter 2 demonstrates that the properties of being binary or regular are of finite character. V arious operations on matroids are also shown to preserve representability, the principal one being induction through a directed graph. In Chapter 3 the same result is proved for algebraic representability.

Chapter 4 is concerned with the automorphisms of independence structures. It is shown that all groups are possible, up to isomorphism, for the automorehism groups of a) graphic geometries, b) transversal geometries, c) partition geometries. The proof of b) relies heavily on the results of Chapter 1. The existence of cyclic matroids, and of certain cyclic transversal matroids and hence of certain cyclic strict gammoids, is demonstrated.

Finally, Chapter 5 is concerned with enumerating the equivalence classes of matroids under isomorphism. Bounds are obtained for general matroids, representable matroids and transversal matroids.

Unless specifically stated otherwise, all theorems may be assumed to be original. It is also specifically stated when a theorem is not original but the proof or derivation is.

Authors: Piff, MJ

• DOI: 10.5287/ora-n6n2dekrj
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English