User:Leigh.Samphier/Matroids
Matroids
- Definitions related to Matroid Theory can be found here.
- Results about Matroid Theory can be found here.
- 2018: Bernhard H. Korte and Jens Vygen: Combinatorial Optimization: Theory and Algorithms (6th ed.) Chapter $13$ Matroids $\S 13.1$ Independence Systems and Matroids, Definition $13.1$
Let $M = \struct {S, \mathscr I}$ be a matroid.
Let $\rho: \powerset S \to \Z$ denote the rank function of $M$.
Let $\sigma: \powerset S \to \powerset S$ denote the closure operator of $M$.
FIX
Definition:Closure Axioms (Matroid)
Properties of Independent Sets and Bases
- 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 5.$ Properties of independent sets and bases
User:Leigh.Samphier/Matroids/Axiom:Base Axioms (Matroid)
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Axiom B1 Iff Axiom B3
References:
- h94 (https://math.stackexchange.com/users/305691/h94), Given bases $A$, $B$ of a matroid there is a one-to-one mapping $\omega$ from $A$ to $B$ such that $(A - {a}) \cup {\omega(a)}$ is independent, URL (version: 2018-02-09): https://math.stackexchange.com/q/2642822
- 1966: David S. Asche: Minimal dependent sets (Journal of the Australian Mathematical Society Vol. 6, no. 3: pp. 259 – 262)
- 1969: Richard A. Brualdi: Comments on bases in dependence structures (Bulletin of the Australian Mathematical Society Vol. 1, no. 2: pp. 161 – 167)
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Axiom B3 Iff Axiom B7
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Axiom B1 Iff Axiom B4
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Axiom B4 Iff Axiom B5
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 1
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 2
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 3
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 4
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 5
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 6
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms/Lemma 7
Properties of the Rank Function
- 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 6.$ Properties of the rank function
The Closure Operator
Closed Sets = Flats = Subspaces
Circuits
- 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 9.$ Circuits
The Cycle Matroid of a Graph
The Greedy Algorithm
- 1976: Dominic Welsh: Matroid Theory ... (previous) Chapter $19.$ $\S 1.$ The greedy algorithm
Maximization Problem (Greedy Algorithm)
Complete Greedy Algorithm yields Maximal Set
Complete Greedy Algorithm may not yield Maximum Weight
Complete Greedy Algorithm guarantees Maximum Weight iff Matroid