Matroid Rank Function Iff Matroid Rank Axioms
Jump to navigation
Jump to search
![]() | This article needs proofreading. Please check it for mathematical errors. If you believe there are none, please remove {{Proofread}} from the code.To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Proofread}} from the code. |
Theorem
Let $S$ be a finite set.
Let $\rho : \powerset S \to \Z$ be a mapping from the power set of $S$ to the integers.
Then:
- $\rho$ is the rank function of a matroid $M = \struct{S, \mathscr I}$.
- $\rho$ satisfies the rank axioms
Proof
Follows immediately from:
Sources
- 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 6.$ Properties of the rank function
- 2018: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (6th ed.) Chapter $13$ Matroids $\S 13.2$ Other Matroid Axion, Theorem $13.10$