User:Leigh.Samphier/Matroids

Common	List of Templates	Basic Refactoring	Missing Sources	List of Pages

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$

• 2011: James Oxley: Matroid Theory (2nd ed.) Chapter $11$ Submodular Function and Matroid Union $\S 11.3$ Matroid union and its applications, Exercise $10$

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$.

Properties of the Rank Function

• 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 6.$ Properties of the rank function

Equivalence of Definitions of Matroid Rank Axioms/Formulation 2 Implies Formulation 1

Properties of Independent Sets and Bases

• 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 5.$ Properties of independent sets and bases

Matroid Bases Iff Satisfies Formulation 1 of Matroid Base Axiom

The Closure Operator

FIX

User:Leigh.Samphier/Matroids/Replace

Definition:Closure Axioms (Matroid)

Circuits

• 1976: Dominic Welsh: Matroid Theory Chapter $1.$ $\S 9.$ Circuits

Circuits of Matroid iff Matroid Circuit Axioms/Formulation 2 implies Circuits of Matroid

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