Matroid

Definition

Matroid

A matroid is a pair where is a ground set, a finite non-empty set, and is a family of independent sets satisfying three axioms:

1. Non-emptiness: .
2. Heredity: If and , then .
3. Exchangeability: If and , then there exists such that .

A set is a dependent set if . A maximal independent set is a basis of .

The diagram is a Hasse diagram for the partial order on the power set .

Ground Set

Definition

Ground Set (Matroid)

In a matroid , the ground set is the finite non-empty set whose subsets are classified as independent or dependent by the family . It is the universe of objects the matroid reasons about — the raw elements from which independent sets are drawn.

The family is the collection of subsets of declared independent. It is the rule that decides, for each subset of the ground set, whether it counts as independent or not. The matroid structure is determined not by alone, but by the choice of on it: the same ground set can carry different matroids.

Link to original

Family

Definition

Family

A family of elements of a set indexed by an index set is a function

Writing , the family is denoted

The index set labels the elements; the codomain says where they live. The function viewpoint lets the same element appear for several indices, so a family need not be a set: it carries indexing and repetition that a set does not.

Link to original

Axioms

Non-emptiness

Definition

Non-emptiness (Matroid)

The non-emptiness axiom for a matroid states that

Equivalently, at least one subset of the ground set, namely the empty set, is an independent set.

Link to original

Heredity

Definition

Heredity (Matroid)

The heredity axiom (also called the monotonicity property) for a matroid states that

Every subset of an independent set is independent.

Link to original

Exchangeability

Definition

Exchangeability (Matroid)

The exchangeability axiom (also called the exchange property) for a matroid states that

A smaller independent set can always be extended by some element of a larger independent set while staying independent.

Link to original

Interpretation

A matroid captures the abstract notion of “independence” common to several settings. It strips away whether the objects are vectors, edges, or anything else, and keeps only the combinatorial shape of which subsets count as independent.

The three axioms isolate exactly the behaviour needed for a greedy algorithm to work. Matroids are the shape behind greedy.

Rank

Definition

Rank (Matroid)

The rank of a matroid is defined as the cardinality of any basis of , i.e.,

Link to original

Examples

Vector Matroid

Definition

Linear Matroid

A linear matroid is a matroid for which there exists a field and a matrix

over with one column for each element , such that for every subset ,

In other words, a matroid is linear if its abstract notion of independence can be represented exactly as linear independence of column vectors of a matrix over some field.

If the field is fixed, then is also called representable over .

Link to original

Graphic Matroid

Definition

Graphic Matroid

A graphic matroid (also called a cycle matroid) is a matroid whose ground set is the edge set of an undirected graph , and whose independent sets are the acyclic edge sets, that is, the forests:

Link to original

Uniform Matroid

Definition

Uniform Matroid

A matroid over an -element ground set is a uniform matroid if the family of independent sets is

for some constant . A subset is independent exactly when its size is at most .

Link to original