What does it really mean by independent sets in Matroids?

362 Views Asked by At

My professor said that if a matroid is defined by $M = (S,\mathcal{I})$, then we have $\mathcal{I} \subseteq \mathcal{P}(S)$ such that all $\alpha \in \mathcal{I}$ are independent.

I am confused as to what it really means to be independent since independent means different things in different context, so what is it in Matroids?

2

There are 2 best solutions below

2
On

It's like "open sets" in topology: we say the elements of the topology of a topological space are open sets, by definition. For matroids we say the elements of $\mathcal{I}$ are the independent subsets of $S$. The matroid axioms generalize the notion of linear independence in linear algebra, in the sense that if $S$ is a finite subset of a vector space $V$ and $\mathcal{I}$ is the collection of all linearly independent subsets of $S$ then $(S,\mathcal{I})$ is a matroid.

0
On

what it really means to be independent since independent means different things in different context

Matroids define what it means to be independent when there is no context, precisely because independence is defined differently in different contexts, but in all those contexts it obeys the same theorems.

For example, if we are talking about a set of linearly independent vectors, a set of trees in a graph, or an algebraically independent set, they all satsify the following: every subset of those sets is also independent (with respect to the definition of independence in the appropriate context). This is exactly one of matroid axioms (a subset of an independent set is itself independent).

A matroid is like a blueprint for what independence should mean, or rather, what the sets in a given context that we call independent should satisfy.