Matroid
Matroide
- Date
- 1935 · confidence high
- Place
- Cambridge, Massachusetts, United States
- Credited to
- Hassler Whitney
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What was discovered
A combinatorial structure that generalises the notion of linear independence from linear algebra to abstract sets, definable via independent sets, bases, circuits or rank functions. It unifies ideas from graph theory and linear algebra, with applications in combinatorial optimisation.
Defined by Hassler Whitney in 1935; Japanese mathematician Takeo Nakasawa had independently arrived at an equivalent structure around the same time, little recognised until decades later.
What it led to
- matroid theory as its own branch of combinatorics
- combinatorial optimisation algorithms (e.g. the greedy algorithm on matroids)
- applications in network theory and coding theory