Base Exchange and Extremal Properties of Matroids

点击翻译按钮获取中文摘要

The concept of a matroid was first introduced by Whitney in 1932. A matroid is an algebraic structure which is defined by axioms on sets. Many combinatorial, algebraic and geometric structures share common properties and a matroid is, in some sense, an abstract object representing all three. Matroids have proven to be important in a number of areas of combinatorics such as graph theory, combinatorial optimization, and coding theory. Increasingly, they are seen to play an important role in other areas of mathematics, especially algebra. The aims of this proposal are two-fold: first, we shall look at specific problems dealing with the so-called "growth-rates" of matroid classes, that is, how the maximum size (i.e. maximum number of elements) of matroids in this class grow as a function of rank. We know that minor-closed classes of matroids , their growth rates fall into four categories: either linear, quadratic, exponential, or unbounded growth. In many cases, we do not have "sharp" bounds for their growth rates. This proposal aims to improve these bounds for various classes of matroids. For "graphic" matroids, such problems have already been studied extensively in the field of graph theory. But relatively little is known for matroids in general. There is a growing interest in the connections between graphs and matroids, and recent progress seems to indicate that many known results for graphs have a corresponding result for matroids.  My work on graphs and regular matroids has given me a unique insight into how one might attack problems for larger classes of matroids such as binary matroids. ******In addition to the above, this proposal also aims to shed some light on the so-called base-exchange properties of matroids. Matroids can be defined by objects called "bases", which are independent sets in the matroid having maximum rank. One can "pivot" from one base to another by "swapping" elements. The ways in which one can pivot to from one base to another is an important yet complex issue. In the 1980's, White posed a number of problems in Algebra which it turned out, could be translated into problems involving swapping bases in matroids. Roughly speaking, the general problem is, given two bases A and B say, is there a way that one can successively pivot from one base to another so that base A is transformed into base B? The work in this proposal aims to tackle this problem and variations of it in special cases, for example, for regular matroids. White's problems, while being mostly ignored in the last twenty years, have recently seen a re-birth of interest among algebraists. I aim to look at various problems of this type, including specific probems for regular matroids. These problems require an understanding of both graphs and matroids. From my research on regular matroids, and in particular my solution to one of White's problems, I have accumulated a wealth of valuable experience which hopefully I can use to solve more problems.