Grant: Discovery Grants Program - Individual
University of Waterloo
$18,000.00
Matroid minors
EF 2012-13
Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
203110-2011
Name nom
Geelen, James
Department département
Combinatorics and Optimization
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2011
Award amount
18000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1508
Committee name en
Mathematics and Statistics
Committee name fr
Mathématiques et statistique
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
2
Nb partie
5
Application title
Matroid minors
Keyword
NSERC
Application summary
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.