Base Exchange and Extremal Properties of Matroids

拟阵的概念最早是由惠特尼于1932年提出的。拟阵是由集合上的公理定义的代数结构。许多组合、代数和几何结构都有共同的性质，而拟阵在某种意义上是代表这三种结构的抽象对象。拟阵已被证明在组合数学的许多领域中都很重要，例如图论、组合优化和编码理论。它们越来越多地被认为在数学的其他领域发挥着重要作用，特别是在代数领域。这项建议的目的有两个：首先，我们将研究与拟阵类的所谓“增长率”有关的具体问题，即这一类中拟阵的最大尺寸(即最大元素数量)如何作为等级的函数增长。我们知道，次闭类拟阵的增长率分为四类：线性增长、二次增长、指数增长或无界增长。在许多情况下，我们对它们的增长率没有“清晰”的界限。这项提议旨在改善不同类别拟阵的界限。对于“图”拟阵，这类问题在图论领域已经得到了广泛的研究。但总体来说，人们对拟阵行虫的了解相对较少。人们对图和拟阵之间的联系越来越感兴趣，最近的进展似乎表明，许多关于图的已知结果都有关于拟阵的相应结果。我在图和正则拟阵方面的工作使我对如何解决更大类拟阵的问题有了独特的见解，例如二进制拟阵。*除上述外，本提案还旨在阐明拟阵的所谓碱基交换性质。拟阵可以由称为“基”的对象来定义，基是拟阵中具有最大等级的独立集合。一个人可以通过“交换”元素从一个基地“旋转”到另一个基地。从一个基地转向另一个基地的方式是一个重要而复杂的问题。上世纪80年代，S·怀特在《代数》中提出了许多问题，并证明这些问题可以转化为拟阵中的基互换问题。粗略地说，一般的问题是，假设有两个碱基A和B，有没有一种方法可以连续地从一个碱基转到另一个碱基，从而使碱基A变成碱基B？这项提案中的工作旨在解决这一问题及其在特殊情况下的变化，例如，对于规则拟阵。怀特的问题虽然在过去20年里大多被忽视，但最近在代数学家中重新引起了兴趣。我的目标是研究这种类型的各种问题，包括正则拟阵的具体问题。这些问题需要对图和拟阵都有所了解。从我对正则拟阵的研究，特别是我对怀特问题的解决中，我积累了丰富的宝贵经验，希望能用来解决更多的问题。

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.