Matroid Theory

• Generalizes Linear Algebra and Graph Theory by observing special constructs that involve the notion of ”linear independence”
• To give an example.

Construct	Graph Theory	Linear Algebra
Independent Set	Subgraphs	Linearly Independent Sets
Basis	Spanning Forests	Basis
Cycles	Cycles	Linearly Dependent Sets
Rank	Cut-set Rank	Rank
Corank	Cycle Rank	Nullity
Loops	Loop Edges	Null Spaces

Notation Guide §

• - a generic matroid
• - matroid dual

---

• - the underlying set of a matroid.
• - cycle (default), co-independent set
• - cocycle
• - basis
• - cobasis
• - independent set
• - rank of .
• - rank function
• - rank function of the dual

---

• - graphic matroid
• - cographic matroid.
• - Transversal Matroid
• - -uniform matroid over a set of elements

---

• - Matroid contraction
• - Matroid restriction
• - union of two matroids

Topics §

• Transversal Theory
• Matroid Definitions and Constructs
• Basic Properties of Matroids
• Matroid Types
• Matroid Duals

Links §

• Introduction To Graph Theory by Wilson