TU Wien:Diskrete Mathematik für Informatik VU (Rubey)/Beispiel17

From VoWi
Jump to navigation Jump to search

Let be an undirected graph. Set where .

Show that is the set of independent sets of a matroid! In particular, the set of spanning forests of an undirected graph is the set of independent sets of a matroid.

I think the OP means to say that is a matroid on the ground set with being the family of independent sets. I assume here that is a finite graph (so and are finite sets). I don't know how to deal with infinite matroids. The second part of the task is simply showing that is a matroid, which is implied by the first part.

From here, there are three checkpoints. For the first one, it is easy to see that , since and gives .

For the hereditary property, let and . Write and . Then, the edge induced subgraph of is a forest, and . So, is in .

For the augmentation property, let be such that . WLOG, assume that and . In the case , things are pretty easy. Pick an element . We have So, is in . If , then we must have Because , Therefore, the forest has more connected components than (recalling that the number of connected components in a forest on vertices and edges is ). Therefore, there exists a connected component of with vertices from at least two connected components of . Therefore, there is an edge of that connects two distinct connected components of . Note that is still a forest. So, .

Quelle: https://math.stackexchange.com/questions/2995272/show-that-m-kg-is-the-set-of-independent-sets-of-a-matroid