15
$\begingroup$

A vector space basis is a set of vectors that span the space and is linearly independent.

It is well-known that for finite dimensional vector spaces this is equivalent to:

  1. The set is minimal with respect to being a spanning set.
  2. The set is maximal with respect to being linearly independent.
  3. Every element of the vector space is uniquely represented as a linear combination of the basis' vectors.

Now consider finite trees. A tree is defined as a set of edges (for some fixed vertex set) such that they connect the vertices (e.g. the tree is a connected graph) and the set is "independent" in the sense that there are no cycles.

Again, this is equivalent to:

  1. The set is minimal with respect to the connectedness of the graph.
  2. The set is maximal with respect to the independence (any edge added would create a cycle).
  3. For every two vertices, there is a unique path between them in the tree.

The similarity is very striking, I believe.

My question is - is this simply a coincidence or part of a greater (category-theory?) connection I'm unaware of? And are there more instances in mathematics for sets having this "minimal-maximal-unique" set of defining properties?

  • 3
    @Miha: Well, I disagree, for the reason that questions might appear to be unanswered on the front page, when in fact they have already been perfectly answered. (In this case, I don't see any need for writing an answer with yet another tutorial about matroids. A simple link would suffice to find more information and relevant literature. But it's of course possible for someone to add a longer answer later anyway.)2011-08-11

1 Answers 1

10

The notion you are looking for are matroids.

  • 0
    Well, isn't this embarrassing for me... At least now I have some motivation to read about this subject (which I have known that existed for years but had only a vague idea what it is).2011-08-11