Matroid minors

这一建议与惠特尼在1935年发表的关于拟阵理论的开创性论文中提出的组合几何中的一个基本问题有关。我们感兴趣的是将有限集E中的点嵌入到一个空间(更具体地说，域F上的一个向量空间)中，使得E的每个子集A都跨越某个指定维度的子空间Rk(A)。这样的嵌入称为F上的(E，Rk)的表示。Whitney问哪些这样的对(E，Rk)允许在F上嵌入。他给出了存在这种嵌入的必要条件，并为满足这些条件的对(E，Rk)创造了术语“拟阵”。拟阵理论已经发展成为一个非常活跃的研究领域，在编码论、信息论、组合优化、电气工程和理论计算机科学中都有重要的应用。 1970年，罗塔提出了一个猜想：对于每个有限域，在域上存在表示的有限障碍列表。Rota猜想是拟阵理论中最著名的公开问题，在过去40年中对拟阵表示理论的发展起到了重要的作用。 罗塔的猜想让人想起库拉托夫斯基的定理，库拉托夫斯基定理表明，在平面上嵌入一个图有两个极小的障碍。该定理是Robertson和Seymour关于次闭图类的特殊结果的特例。这个建议的目的是将图-子集的结果推广到拟阵的背景下，以解决Rota猜想。这项提议是吉姆·吉伦、伯特·杰拉德和杰夫·惠特尔之间长期合作项目的一部分。

This proposal is related to a fundamental problem in combinatorial geometry posed by Whitney in his seminal paper on matroid theorey in 1935. We are interested in embedding points from a finite set E into a space (more specifically, a vector space over a field F) such that each subset A of E spans a subspace of some prescribed dimension rk(A). Such an embedding is called a representation of (E, rk) over F. Whitney asked which such pairs (E, rk) admit embeddings over F. He gave necessary conditions for the existence of such embeddings, and coined the term "matroid" for the pairs (E, rk) that satisfy these conditions. Matroid theory has since grown into a highly active research area with significant applications in coding theory, information theory, combinatorial optimization, electrical engineering, and theoretical computer science. In 1970, Rota posed a conjecture that: for each finite field, there is a finite list of obstructions for representability over the field. Rota's conjecture is the most well-known open problem in matroid theory and has played a significant role in the development of the theory of matroid representation over the past 40 years. Rota's Conjecture is reminiscent of Kuratowski's theorem which shows that there are two minor-minimal obstructions for embedding a graph in the plane. This theorem is a special case of the extraordinary results of Robertson and Seymour on minor-closed classes of graphs. The goal of this proposal is to extend the graph-minors results to the context of matroids in order to solve Rota's Conjecture. This proposal is a part of a long term collaborative project between Jim Geelen, Bert Gerards, and Geoff Whittle.