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/Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom
User:Leigh.Samphier/Matroids/Equivalence of Definitions of Matroid Base Axioms
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/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 7
User:Leigh.Samphier/Matroids/Matroid Bases Iff Satisfies Matroid Base Axiom/Sufficient Condition
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