Independent Set (Matroid)

Definition

Independent Set (Matroid)

Let be a matroid. A set is an independent set of if

The family is the collection of all independent sets, fixed by the three matroid axioms: non-emptiness, heredity, and exchangeability.

Example

What contains

Let the ground set be

Suppose we want the independent sets to be exactly the subsets of size at most . Then the independence family is

Here is not one independent set. It is the full list of all sets that count as independent.

For example,

so is independent. But

so is dependent.

This is the uniform matroid : independence means “choose at most two elements”.

The notation therefore separates two levels:

Symbol	Meaning
	the available elements
	one candidate set of elements
	the family of all candidate sets that are allowed

Thus writing means: the particular subset is one of the allowed independent subsets.