Dominik Farhan

Why should you study matroids?

short answer: Because you need to pass your exams.

long answer (according to Chat): Venturing into the study of matroids opens a world where disparate mathematical structures converge in fascinating ways. As the backbone of combinatorial optimization, matroids simplify complex problems and power efficient algorithms. Their study deepens your understanding of abstract structures, enhances problem-solving skills, and offers a window into cutting-edge research across various fields. Dive into matroids, enrich your mathematical journey, and unlock a world of intellectual discovery.

Deinitions

Matroid is a pair $(X, S)$ where $S \subseteq P(X)$ satysfying the following properties:

$\emptyset \in S$
$\forall B \subset A: A \in S \implies B \in S$
$\forall A, B \in S: |A| < |B| \implies \exists x \in B \setminus A: \{x \} \cup A \in S$

Matroid is any hereditary system with the third property.

Interestingly the third property is equivalent to saying that

Definition ( $3'$ ). Let

Z \subseteq X

and

A, B \subseteq Z

such that they are maximal (with regard to inclusion) independent. Then

|A| = |B|

Let's now prove the previous equivalence.

Solution ( $3 \implies 3'$ )

Proof. Assume that

3

holds and

3'

does not. Let

A, B

be maximal with regard to inclusion and WLOG

|A| < |B|

. By

3

we can add an element from

B

A

making it larger which contradicts the assumption that

A

is maximal with regard to the inclusion.

Solution ( $3' \implies 3$ )

Proof. Let there be

A, B

s.t.

|A| < |B|

that violates

3

. Then take

Z = A\cup B

and by

3

all maximal independet subsets of

Z

have the same size. Now

A

is clearly not maximal because of

|A| < |B|

so there is an element in

Z

and not in

A

which we can add to

A

Definition (Base). Base is maximal independent subset (think of bases of vector spaces).

Examples

Matroids are attemp to generalize the notion of independence in vector spaces and also some concepts from graph theory. It is often quite useful to think about specific examples.

Vectors

Let $X$ be a vector space. Let $S$ constist of subsets of $X$ such that they are linearly independent. $3$ by the Steinitz exchange lemma.

Graphs

We can take $(E, S)$ and $A \in S$ whenever $G[ A ]$ is acyclic. $1, 2$ are easy. Maximal independent set is alwyas as spanning forest which gives us $3$ .

Fanno plane

Bases are those triplets that are not on the same line.

Uniform matroid

We don't care about elements but only sizes. For some $k$ we take any set of size $\leq k$ to be independent.

Special cases:

trivial matroid $S = \{ \emptyset \}$
complete matroid $k = |X|$

Truncated matrod

We can limit rank of any matroid by truncating at some number

k

(rank is discussed in the following chapter).

Excercises to check your understanding

For the set system defined by $(X, S) = (\{1, 2\}, \{∅, \{1\}, \{2\}, \{1, 2\}\})$ , does it form a matroid? Justify your answer based on the three properties of matroids.

Solution (1)
All properties are satisfied. Btw. this is a complete matroid.
Given the set system defined by $(X, S) = (\mathbb{R}^3, S)$ , where $S$ is the set of all linearly independent subsets of $\mathbb{R}^3$ , prove that this set system forms a matroid using the properties of matroids.
Solution (2)
- Empty set is linearly independent.
- If set is linearly independent also its subsets are.
- Let $A, B$ be two linearly independent set and $|A| < |B|$ . If each of elements of $B$ could be generated by elements of $A$ then $B$ wouldn't be independent. Thus, there is at least one element that cannot be generated by elements of $A$ . We can add this element to $B$ .
Consider a graph with nodes {A, B, C, D} and edges {AB, BC, CD, DA}. Let X be the edge set and S be the set of all subsets of X that form acyclic subgraphs. Prove that (X, S) forms a matroid.
Solution (3)
- No edges are surely acyclic
- If graph is acyclic then also its subgraph is acyclic.
- We can use the property $3'$ . All maximal independent subsets are spanning trees. All spanning trees have surely $4 - 1$ edges.
Let $G = (V, E)$ be a graph. Let the ground set be $E$ and $S$ be a set of all paths. Is this a matroid?
Solution (4)
The first two properties hold (if we assume the empty set to be a trivial path from vertex to iteself). However, the third property is not satisfied. It is not guaranteed that we can add an edge from a longer path to some shorter so that the result is still a path.
Imagine you are working in a Tesla factory. The factory can produce different car parts. Some parts cannot be produced at once becuase some parts depend on others. Let the ground set be the set of all parts. Call a subset of the ground set independent if all parts in it can be produced in parallel. Decide if you are dealing with a matroid.

Matroids: Examples and definitions