# Definition:Matroid

## Definition

Let $M = \struct {S, \mathscr I}$ be an independence system.

### Definition 1

$M$ is called a **matroid on $S$** if and only if $M$ also satisfies:

\((\text I 3)\) | $:$ | \(\ds \forall U, V \in \mathscr I:\) | \(\ds \size V < \size U \implies \exists x \in U \setminus V : V \cup \set x \in \mathscr I \) |

### Definition 2

$M$ is called a **matroid on $S$** if and only if $M$ also satisfies:

\((\text I 3')\) | $:$ | \(\ds \forall U, V \in \mathscr I:\) | \(\ds \size U = \size V + 1 \implies \exists x \in U \setminus V : V \cup \set x \in \mathscr I \) |

### Definition 3

$M$ is called a **matroid on $S$** if and only if $M$ also satisfies:

\((\text I 3'')\) | $:$ | \(\ds \forall U, V \in \mathscr I:\) | \(\ds \size V < \size U \implies \exists Z \subseteq U \setminus V : \paren {V \cup Z \in \mathscr I} \land \paren {\size {V \cup Z} = \size U} \) |

### Definition 4

$M$ is called a **matroid on $S$** if and only if $M$ also satisfies:

\((\text I 3''')\) | $:$ | \(\ds \forall A \subseteq S:\) | \(\ds \text {all maximal subsets $Y \subseteq A$ with $Y \in \mathscr I$ have the same cardinality} \) |

## Also known as

When the context is obvious, $M = \struct {S, \mathscr I}$ is simply called a **matroid**.

## Independent Set

An element of $\mathscr I$ is called an **independent set** of $M$.

## Dependent Set

A subset of $S$ that is not an element of $\mathscr I$ is called a **dependent set** of $M$.

## Examples of Matroids

### Uniform Matroid

Let $S$ be a finite set of cardinality $n$.

Let $\mathscr I_{k,n}$ be the set of all subsets of $S$ of cardinality less than or equal to $k$.

Then the ordered pair $\struct {S, \mathscr I_{k, n} }$ is called the **uniform matroid of rank $k$** and is denoted $U_{k,n}$.

### Free Matroid

Let $S$ be a finite set.

Let $\mathscr I = \powerset S$ be the power set of $S$.

That is, let $\mathscr I$ be the set of all subsets of $S$:

- $\mathscr I := \set {X: X \subseteq S}$

Then the ordered pair $\struct{S, \mathscr I}$ is called the **free matroid of $S$**.

### Matroid Induced by Linear Independence in Vector Space

Let $V$ be a vector space.

Let $S$ be a finite subset of $V$.

Let $\mathscr I$ be the set of linearly independent subsets of $S$.

Then the ordered pair $\struct{S, \mathscr I}$ is called a **matroid induced on $S$ by linear independence in $V$**.

### Cycle Matroid

Let $G$ be a graph.

Let $E$ be the edge set of $G$.

Let $\mathscr I$ be the set of edge sets of subgraphs of $G$ that contain no cycles.

Then the ordered pair $\struct{E, \mathscr I}$ is called the **cycle matroid** of the graph $G$.

### Matroid Induced by Algebraic Independence

Let $L / K$ be a field extension.

Let $S \subseteq L$ be a finite subset of $L$.

Let $\mathscr I$ be the set of algebraically independent subsets of $S$.

Then $\struct {S, \mathscr I}$ is called the **matroid induced by algebraic independence over $K$ on $S$**.

### Matroid Induced by Affine Independence

Let $\R^n$ be the $n$-dimensional real Euclidean space.

Let $S = \set{x_1, \dots, x_r}$ be a finite subset of $\R^n$.

Let $\mathscr I$ be the set of affinely independent subsets of $S$.

Then $\struct{S, \mathscr I}$ is called the **matroid induced by affine independence on $S$**.

### Matroid Induced by Linear Independence in Abelian Group

Let $\struct{G, +}$ be a torsion-free Abelian group.

Let $\struct{G, +, \times}$ be the $\Z$-module associated with $G$.

Let $S$ be a finite subset of $G$.

Let $\mathscr I$ be the set of linearly independent subsets of $S$.

Then the ordered pair $\struct{S, \mathscr I}$ is called the **matroid induced by linear independence in $G$ on $S$**.