Base Exchange and Extremal Properties of Matroids

矩阵的概念最早是由惠特尼在1932年提出的。拟阵是由集合上的公理定义的代数结构。许多组合结构、代数结构和几何结构具有共同的性质，在某种意义上，矩阵是代表这三者的抽象对象。拟阵在组合学的许多领域，如图论、组合优化和编码理论中都被证明是重要的。越来越多的人看到它们在数学的其他领域，尤其是代数中扮演着重要的角色。本建议的目的有两个方面：首先，我们将研究处理所谓的拟阵类“增长率”的具体问题，即该类中拟阵的最大大小（即最大元素数）如何作为秩的函数增长。我们知道小闭类拟阵，它们的增长率可分为四类：线性增长、二次增长、指数增长或无界增长。在许多情况下，我们对它们的增长率没有“明确的”界限。这一建议的目的是改进这些界限为各种类型的拟阵。对于“图”拟阵，这类问题在图论领域已经得到了广泛的研究。但是一般来说，我们对类人猿知之甚少。人们对图和拟阵之间的联系越来越感兴趣，最近的进展似乎表明，许多已知的图的结果对拟阵也有相应的结果。我在图和正则拟阵方面的工作给了我一个独特的见解，让我知道如何解决像二元拟阵这样的大类群的问题。******除了上述内容外，该提案还旨在阐明拟阵的所谓碱基交换特性。拟阵可以由称为“基”的对象来定义，基是拟阵中具有最大秩的独立集合。玩家可以通过“交换”元素从一个基地“转向”另一个基地。从一个基地转向另一个基地的方式是一个重要而复杂的问题。在20世纪80年代，怀特在代数中提出了一些问题，结果证明，这些问题可以转化为涉及拟阵中交换基的问题。粗略地说，一般的问题是，给定两种基底A和B，有没有一种方法可以连续地从一种基底转向另一种基底从而使基底A变换成基底B？本提案中的工作旨在解决这个问题及其在特殊情况下的变化，例如正则拟阵。怀特的问题，虽然在过去的二十年里几乎被忽视，但最近在代数学家中重新引起了兴趣。我的目标是研究这种类型的各种问题，包括正则拟阵的具体问题。这些问题需要同时了解图和拟阵。通过对正则拟阵的研究，特别是解决White的一个问题，我积累了很多宝贵的经验，希望可以用来解决更多的问题。

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.