Leigh.Samphier/Sandbox/Matroids

From ProofWiki
Jump to navigation Jump to search

Matroids

  • Definitions related to Matroid Theory can be found here.
  • Results about Matroid Theory can be found here.


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 Independent Sets and Bases

All Bases of Matroid have same Cardinality

NOT NEEDED!! Leigh.Samphier/Sandbox/Independent Superset of Dependent Set Minus Singleton Doesn't Contain Singleton


Leigh.Samphier/Sandbox/Matroid Base Substitution From Fundamental Circuit


Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)

Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)/Definition 1

Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)/Definition 2

Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)/Definition 3

Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)/Definition 4

Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)/Definition 5

Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)/Definition 6

Leigh.Samphier/Sandbox/Definition:Base Axiom (Matroid)/Definition 7


Leigh.Samphier/Sandbox/Matroid Base Axiom Implies Sets Have Same Cardinality


Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom

Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Necessary Condition

Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Sufficient Condition

Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Sufficient Condition/Lemma

Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Sufficient Condition/Lemma/Lemma 1

Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Sufficient Condition/Lemma/Lemma 2

Leigh.Samphier/Sandbox/Matroid Satisfies Base Axiom/Sufficient Condition/Lemma/Lemma 3


Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom/Lemma

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom/Definition 1 Iff Definition 3

References:

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom/Definition 1 Iff Definition 4

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom/Definition 4 Iff Definition 5

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom/Definition 4 Iff Definition 5/Lemma

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Base Axiom/Definition 3 Iff Definition 7


Properties of the Rank Function

Leigh.Samphier/Sandbox/Independent Subset is Contained in Maximal Independent Subset/Corollary

Leigh.Samphier/Sandbox/Cardinality of Maximal Independent Subset Equals Rank of Set

Leigh.Samphier/Sandbox/Matroid Satisfies Rank Axioms

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 1 Implies Condition 3

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 1 Implies Condition 3/Lemma 1

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 1 Implies Condition 3/Lemma 2

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 1 Implies Condition 3/Lemma 3

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 3 Implies Condition 2

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Rank Axioms/Condition 2 Implies Condition 1

The Closure Operator

Closed Sets = Flats = Subspaces

Circuits

Leigh.Samphier/Sandbox/Proper Subset of Matroid Circuit is Independent

Leigh.Samphier/Sandbox/Rank of Matroid Circuit is One Less Than Cardinality

Leigh.Samphier/Sandbox/Bound for Cardinality of Matroid Circuit

Leigh.Samphier/Sandbox/Matroid with No Circuits Has Single Base


Leigh.Samphier/Sandbox/Definition:Circuit Axioms (Matroid)

Leigh.Samphier/Sandbox/Definition:Circuit Axioms (Matroid)/Definition 1

Leigh.Samphier/Sandbox/Definition:Circuit Axioms (Matroid)/Definition 2

Leigh.Samphier/Sandbox/Definition:Circuit Axioms (Matroid)/Definition 3


Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Circuit Axioms

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Circuit Axioms/Condition 1 Implies Condition 2

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Circuit Axioms/Condition 2 Implies Condition 3

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Circuit Axioms/Condition 3 Implies Condition 4

Leigh.Samphier/Sandbox/Equivalence of Definitions of Matroid Circuit Axioms/Condition 4 Implies Condition 1


Leigh.Samphier/Sandbox/Matroid Unique Circuit Property

Leigh.Samphier/Sandbox/Matroid Unique Circuit Property/Proof 1

Leigh.Samphier/Sandbox/Matroid Unique Circuit Property/Proof 2

The Cycle Matroid of a Graph

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