Is there a connection between the "independent sets" in matroids and "independent sets" in graph theory?

1.7k Views Asked by At

I've been reading up on matroids recently, which are used in the theory of greedy algorithms. A matroid is a pair $(X, I)$ where $X$ is a set and $I \subseteq \wp(X)$ is a family of sets over $X$ called the independent sets in $X$.

It occurred to me that I'd seen the term "independent set" also used in a graph-theoretic context to refer to a set of nodes in a graph where no two nodes in the set are adjacent.

I'm not immediately seeing a connection between these two kinds of independent sets. Notably, in a matroid, all maximal independent sets are required to have the same cardinality, while in a graph theory context, it's possible for there to be many different maximal independent sets of differing cardinalities.

Is there a connection between these two concepts of "independent sets," or is the terminology just an accident of history?

1

There are 1 best solutions below

1
On BEST ANSWER

Expanding on @Moritz's comment, it seems like the answer comes from a related mathematical structure called an independence system, which is a pair $(X, I)$ where $X$ is a ground set, $I \subseteq \wp(A)$, and $I$ obeys the following properties:

  • $I \ne \emptyset$, and
  • $\forall S \in I. \wp(S) \subseteq I$.

The sets in $I$ are called independent sets. The set of all independent sets in a graph $G$ form an independence system, since there's always at least one independent set (namely, the empty set) and any subset of an independent set is also an independent set.

A matroid is an independence structure that also satisfies the exchange property, which is something that independent sets in a graph-theoretic sense do not obey. So in that sense, the connection between independent sets in graph theory and independent sets in matroids comes from the independence structure of a matroid, not the exchange property.