Some problems in combinatorial geometry

Thesis



This thesis is in two parts. The first two chapters deal with infinite matroids and the remaining three chapters with finite matroids.

Chapter 1 has two main results. Firstly we prove that there is no duality function on the class of independence spaces which behaves like duality for finite matroids. Secondly we determine the unique class of preindependence spaces which contains the class of independence spaces and is closed under restriction, contraction and the natural duality function. Two other results of this chapter answer questions of Higgs and Welsh on infinite matroids.

The main result of Chapter 2 is a counter-example to a 1967 conjecture of Nash-Williams concerning packing disjoint spanning trees in countably infinite graphs.

In the third chapter we prove matroid analogues of various bounds on the chromatic number of a graph due to Matula, Szekeres and Wilf, and Brooks. These matroid results sharpen earlier bounds of Heron and Lindstrőm. In the second half of the chapter we answer a number of questions of Mullin and Stanton related to the critical problem for binary matroids.

In Chapter 4 we prove the binary case of a matroid conjecture of Welsh which is a natural analogue of Gallai's theorem that the vertex-stability and vertex-covering numbers of a graph G sum to the number of vertices of G.

The Tutte polynomial of a graph is known to be related to the bond percolation model on the graph. In Chapter 5 we introduce a basic abstraction of classical percolation theory, namely percolation on clutters. We give new and simpler proofs of several results of Hammersley and bound the percolation probability above and below. One of the main results shows that the theory of the Tutte polynomial cannot be extended from matroids to arbitrary clutters.

Authors: Oxley, J; Oxley, James G.

• Publication date: 1978
• DOI: 10.5287/ora-o55xvnx1y
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Subjects: Matroids