Definition 2.1. Let E be a finite set and let ℱ ⊆ 2^E. The pair (E,ℱ) is a hereditary set system if

Example 2.2. The following are hereditary set systems.

1.

Let G = (V,E) be a graph and ℱ = {F ⊆ E : F contains no cycle}.

2.

Let G = (V,E) be a graph and ℱ = {M ⊆ E : M is a matching}.

3.

Let G = (V,E) be a graph and ℱ = {S ⊆ V : S induces a clique}.

4.

Let G = (V,E) be a graph and ℱ = {S ⊆ V : S is an independent set}.

5.

Let E = {1,…,n} and fix an integer k. Define ℱ = {S ⊆ E : |S|≤ k}.

6.

Let E = {1,…,n} and define ℱ = S ⊆ E : ∑ _i∈Si ≤ 10.

However, this need not be a matroid. For example, {10},{4,5}∈ℱ with |{10}| < |{4,5}|, yet neither {10,4} nor {10,5} belongs to ℱ, so the exchange property fails.

Definition 3.1. A matroid is a pair M = (E,ℐ), where E is a finite set and ℐ⊆ 2^E is a collection of independent sets, satisfying:

(i)

∅∈ℐ.

(ii)

If I ∈ℐ and I′⊆ I, then I′∈ℐ.

(iii)

(Exchange axiom) If I₁,I₂ ∈ ℐ and |I₁| < |I₂|, then there exists e ∈ I₂ ∖ I₁ such that I₁ ∪{e}∈ℐ.

Example 3.2. Let

and let E = {1,2,3,4}, where element i corresponds to the i-th column of A. Define ℐ to consist of those S ⊆ E for which the columns indexed by S are linearly independent.

Then (E,ℐ) is a matroid. For example, {1,2}, {1,4}, and {2,3} are independent, while {1,2,3} is dependent. For instance:

Proposition 3.3. Let A be a matrix with column set E, and let ℐ = {S ⊆ E : S is linearly independent}. Then (E,ℐ) is a matroid.

Definition 4.1. A set B ∈ℐ is a basis of a matroid M = (E,ℐ) if it is maximal with respect to inclusion, i.e. B ∪{e}ℐ for all e ∈ E ∖ B.

Proposition 4.2. All bases of a matroid have the same cardinality.

Theorem 4.3. Let ℬ⊆ 2^E be a nonempty collection of subsets of E. Then ℬ is the collection of bases of a matroid if and only if:

(i)

|B₁| = |B₂| for all B₁,B₂ ∈ℬ.

(ii)

For all B₁,B₂ ∈ℬ and e ∈ B₁ ∖B₂, there exists f ∈ B₂ ∖B₁ such that (B₁ ∖{e}) ∪{f}∈ℬ.

Example 4.4. Let G = (V,E) be a graph and ℬ be the collection of spanning forests of G.

(i)

All spanning forests have the same size |V |−c(G), where c(G) denotes the number of connected components.

(ii)

Let F₁,F₂ ∈ℬ and e ∈ F₁ ∖ F₂. Removing e from F₁ splits one tree into two components A and B. Since F₂ is a spanning forest, there must exist f ∈ F₂ ∖ F₁ with one endpoint in A and the other in B; then (F₁ ∖{e}) ∪{f} is again a spanning forest.

Hence the spanning forests of G form the bases of a matroid whose independent sets are exactly the acyclic edge subsets of G.

Example 4.5 (Uniform Matroids). Let E be a finite set and k a nonnegative integer. The pair

is a matroid, called the uniform matroid U_k,E.

Example 4.6 (Transversal Matroids). Let A₁,…,A_m ⊆ E. A subset S ⊆ E is independent if it admits a system of distinct representatives from A₁,…,A_m. The resulting matroid is called a transversal matroid.

Theorem 5.1. Let (E,ℐ) be a hereditary set system with ℐ≠∅. Then

Definition 6.1. A matroid M = (E,ℐ) is representable over a field 𝔽 if there exists a matrix A over 𝔽 with columns indexed by E such that S ⊆ E is independent in M if and only if the corresponding columns of A are linearly independent.

Definition 6.2. Let G = (V,E) be a graph. The graphic matroid of G is the matroid whose independent sets are the acyclic subsets of E.

Theorem 6.3. Every graphic matroid is representable over ℝ.

Definition 6.4. A matroid is regular if it is representable over every field.

Remark 6.5. The proof above works over any field (replace −1 by the additive inverse of 1), so every graphic matroid is regular.

Example 6.6 (Uniform Matroids). The uniform matroid U_k,n is representable over sufficiently large fields. For instance, U_2,4 is represented over ℝ by

since every pair of columns is linearly independent. More generally, over an infinite field, choose n distinct points on the moment curve (1,t,t²,…,t^k−1); any k corresponding columns are linearly independent.

Example 6.7. Uniform matroids need not be regular. U_2,4 would require four nonzero vectors in 𝔽₂² such that every pair is linearly independent, but 𝔽₂² contains only three nonzero vectors: (1,0), (0,1), (1,1). Hence U_2,4 is not representable over 𝔽₂.

Theorem 7.1. M|A is a matroid on ground set A.

Theorem 7.2 (Edmonds’ Matroid Union Theorem). (E,ℐ) is a matroid. More generally, the union of finitely many matroids on E is a matroid.

Remark 7.3. The set-theoretic union ℐ₁ ∪ℐ₂ of two independence families is not necessarily a matroid; the correct construction is the family of unions of independent sets as defined above.

Example 7.4 (Partition Matroid). Let E = E₁ ⊔E₂ ⊔⊔E_k and fix integers 0 ≤ r_i ≤|E_i|. Call I ⊆ E independent if |I ∩ E_i|≤ r_i for all i. The resulting matroid is called a partition matroid.

For example, let E = {a,b,c,d,e,f}, E₁ = {a,b}, E₂ = {c,d,e,f}, r₁ = 1, r₂ = 2. Then {a,c,d} is independent, while {a,b,c} is not.

A partition matroid arises by taking the uniform matroid U_ri,E for each block, restricting it to E_i, and forming the union of these restricted matroids — so it is indeed a matroid by the preceding results.