User:Leigh.Samphier/Matroids
Matroids (Completed)
- 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 the Rank Function
- 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 6.$ Properties of the rank function
User:Leigh.Samphier/Matroids/Formulation 1 Rank Axioms Implies Rank Function of Matroid
User:Leigh.Samphier/Matroids/Formulation 1 Rank Axioms Implies Rank Function of Matroid/Proof 1
User:Leigh.Samphier/Matroids/Formulation 1 Rank Axioms Implies Rank Function of Matroid/Proof 2
User:Leigh.Samphier/Matroids/Formulation 1 Rank Axioms Implies Rank Function of Matroid/Lemma 1
User:Leigh.Samphier/Matroids/Formulation 1 Rank Axioms Implies Rank Function of Matroid/Lemma 2
User:Leigh.Samphier/Matroids/Formulation 1 Rank Axioms Implies Rank Function of Matroid/Lemma 3
User:Leigh.Samphier/Matroids/Formulation 1 Rank Axioms Implies Rank Function of Matroid/Lemma 4
User:Leigh.Samphier/Matroids/Rank Function of Matroid Satisfies Formulation 1 Rank Axioms
User:Leigh.Samphier/Matroids/Rank Function of Matroid Satisfies Formulation 2 Rank Axioms
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Rank Axioms
User:Leigh.Samphier/Matroids/Matroid Rank Function Iff Matroid Rank Axioms
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 Axiom (Matroid)
User:Leigh.Samphier/Matroids/Axiom:Base Axiom (Matroid)/Formulation 1
User:Leigh.Samphier/Matroids/Axiom:Base Axiom (Matroid)/Formulation 2
User:Leigh.Samphier/Matroids/Axiom:Base Axiom (Matroid)/Formulation 3
User:Leigh.Samphier/Matroids/Axiom:Base Axiom (Matroid)/Formulation 4
User:Leigh.Samphier/Matroids/Axiom:Base Axiom (Matroid)/Formulation 5
User:Leigh.Samphier/Matroids/Axiom:Base Axiom (Matroid)/Formulation 6
User:Leigh.Samphier/Matroids/Axiom:Base Axiom (Matroid)/Formulation 7
User:Leigh.Samphier/Matroids/Set Difference Then Union Equals Union Then Set Difference
User:Leigh.Samphier/Matroids/Set Difference Then Union Equals Union Then Set Difference/Corollary
User:Leigh.Samphier/Matroids/Corollary of Set Difference Then Union Equals Union Then Set Difference.
User:Leigh.Samphier/Matroids/Larger Set has Larger Set Difference
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom/Lemma 1
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom/Lemma 2
User:Leigh.Samphier/Matroids/Matroid Bases Satisfy Formulation 3 of Matroid Base Axiom
User:Leigh.Samphier/Matroids/Matroid Bases Satisfy Formulation 3 of Matroid Base Axiom/Lemma 1
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Formulation 5 of Matroid Base Axiom
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Formulation 5 of Matroid Base Axiom/Lemma 1
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Formulation 5 of Matroid Base Axiom/Lemma 2
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Matroid Base Axiom
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