Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$52,000.00

Proof Formalization in Matroid Theory

FY 2023-24

Summary
I propose to formalize the foundational, classical and modern aspects of matroid theory using a proof assistant. Matroid theory is an area of discrete mathematics that arose in the first half of the twentieth century. A matroid is a mathematical object that can be thought of a set of points in an abstract geometric space; their definition captures the intuitive notion of independence, simultaneously generalizing matrices and graphs, and finite geometries. Matroids have links to a wide range of areas of mathematics, ranging from optimization and polyhedral theory to structural graph theory and algebraic geometry. The combinatorial theory of matroids has deep ties to graph theory, and has burgeoned in recent decades. Like many other areas of mathematics, proofs in modern matroid theory can become long and technical, potentially stretching to hundreds of pages. Such theorems can be of huge importance to the subject, but checking their correctness is a laborious and often thankless task, sometimes only realistically achievable by a few select experts. Moreover, even with complete diligence and good faith from authors and reviewers, mathematical errors always have a chance of slipping through the cracks. With such long arguments more frequent than ever, a solution is in order. One can be found in the world of proof formalization. A proof formalizer, or 'assistant' (this project focuses on the 'lean' prover developed by Microsoft Research) allows mathematical proofs to be input in a formally specified programming language, so that their correctness can be systematically verified by a computer. The process of preparing mathematics for such a treatment is hard; it requires creativity, craft, persistence, and skill in both research-level mathematics and programming. But its rewards are obvious. A formalized proof of a mathematical theorem gives us not only complete confidence in its correctness, but allows peer-reviewers to focus on merit and impact rather than painstakingly checking proof details, and organizes whole fields of mathematics on a secure logical footing. While the world of proof formalization is growing and has seen many recent high-profile successes, there has been almost no work on formalizing results in matroid theory. My proposed project is to combine my expertise in this field with my increasing experience in proof formalization to bring matroid theory into this new way of thinking about mathematics. This process will begin with the mathematically elementary and foundational, and continue to the very forefront of human knowledge on the subject. Its results will be a firm footing for matroid theory in a very exciting new chapter of mathematical knowledge.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2023-03735
Name nom
Nelson, Alexander
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
2023
Competition year année de concours
2023
Award amount
52000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
803
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer communications
Area of application fr
Téléinformatique
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Combinatorics
Research subject en
Mathématiques pures
Research subject fr
Combinatoire
Application title
Proof Formalization in Matroid Theory
Keyword
Combinatorics; Extremal Combinatorics; Matroid Theory; Proof Formalization; Structural Combinatorics
Application summary
I propose to formalize the foundational, classical and modern aspects of matroid theory using a proof assistant. Matroid theory is an area of discrete mathematics that arose in the first half of the twentieth century. A matroid is a mathematical object that can be thought of a set of points in an abstract geometric space; their definition captures the intuitive notion of independence, simultaneously generalizing matrices and graphs, and finite geometries. Matroids have links to a wide range of areas of mathematics, ranging from optimization and polyhedral theory to structural graph theory and algebraic geometry. The combinatorial theory of matroids has deep ties to graph theory, and has burgeoned in recent decades. Like many other areas of mathematics, proofs in modern matroid theory can become long and technical, potentially stretching to hundreds of pages. Such theorems can be of huge importance to the subject, but checking their correctness is a laborious and often thankless task, sometimes only realistically achievable by a few select experts. Moreover, even with complete diligence and good faith from authors and reviewers, mathematical errors always have a chance of slipping through the cracks. With such long arguments more frequent than ever, a solution is in order. One can be found in the world of proof formalization. A proof formalizer, or 'assistant' (this project focuses on the 'lean' prover developed by Microsoft Research) allows mathematical proofs to be input in a formally specified programming language, so that their correctness can be systematically verified by a computer. The process of preparing mathematics for such a treatment is hard; it requires creativity, craft, persistence, and skill in both research-level mathematics and programming. But its rewards are obvious. A formalized proof of a mathematical theorem gives us not only complete confidence in its correctness, but allows peer-reviewers to focus on merit and impact rather than painstakingly checking proof details, and organizes whole fields of mathematics on a secure logical footing. While the world of proof formalization is growing and has seen many recent high-profile successes, there has been almost no work on formalizing results in matroid theory. My proposed project is to combine my expertise in this field with my increasing experience in proof formalization to bring matroid theory into this new way of thinking about mathematics. This process will begin with the mathematically elementary and foundational, and continue to the very forefront of human knowledge on the subject. Its results will be a firm footing for matroid theory in a very exciting new chapter of mathematical knowledge.