Matroid minors

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

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.