matroids

References

Summary

Definitions

Matroid (independence)

A matroid (A,Σ) is a set A and a collection of subsets Σ such that ∅ ∈ Σ If A ⊆ B ∈ Σ then A ∈ Σ. If A, B ∈ Σ and |A| < |B|, there is some b ∈ B such that A ∪ {b} ∈ Σ.

Dependent: Sets in Σ are called independent; all other sets are called dependent

Bases: A maximal set in Σ is called a basis.

Circuits: A minimal dependent set is called a circuit

Matroid (bases)

A matroid (A,ℬ) is a set A and a collection of subsets ℬ such that

ℬ ≠ ∅ If U, V ∈ ℬ and u ∈ U \ V then there is some v ∈ V \ U such that (U\{u}) ∪ {v} ∈ ℬ.

Matroid (closure)

A closure operator on a set A is a function ϕ : P(A) → P(A) such that U ⊆ ϕ(U) ϕ2 = ϕ If U ⊆ V then ϕ(U) ⊆ ϕ(V).

A matroid is a closure operator ϕ : P(A) → P(A) such that If x ∈ ϕ(U∪{y}) \ ϕ(U) then y ∈ ϕ(U∪{x}) \ ϕ(U).

Flats: A set such that ϕ(U) = U is called closed or flat. The set of flats of a closure operator is denoted 𝒞ϕ

Matroid (flats)

A matroid is a closure operator ϕ : P(A) → P(A) such that

A ∈ 𝒞ϕ If U, V ∈ 𝒞ϕ then U ∩ V ∈ 𝒞ϕ. U ∈ 𝒞ϕ then for each x ∈ Uc there is exactly one Vx ∈ 𝒞ϕ such that x ∈ Vx and U ⊆ Vx, where U is maximal in Vx.

Unions: Flats are almost never closed under unions

Matroid (rank)

A matroid is a pair (A,ρ) where ρ : P(A) → ℕ ≥ 0 satisfies

ρ(X) ≤ |X| ρ(X∪Y) + ρ(X∩Y) ≤ ρ(X) + ρ(Y) If X ⊆ Y then ρ(X) ≤ ρ(Y)

We call ρ the rank function.

Nullity: We call |X| − ρ(X) the nullity of X.

Matroid (hyperplanes)

Matroid (graphoid)

Möbius function

Nerve of a poset

Theorems

Lattice of flats

The collection of all flats forms a lattice

Matroids are wedges of spheres up to homotopy

Euler characteristic of a matroid

Matroids are shellable

Chow ring

Chow ring is hard lefschetz

Chow ring is Hodge-Riemann

Differential forms

Examples

Vector matroids

Algebraic matroids

Graphic matroids