Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
I think the notion you're looking for is a matroid. –  Miha Habič Aug 11 '11 at 11:41
@Miha: Write that as an answer, not as a comment. (Since it is in fact the answer to the question asked!) –  Hans Lundmark Aug 11 '11 at 12:11
It's cool you noticed such a striking resemblance. Cool to know. +1 –  Patrick Da Silva Aug 11 '11 at 12:43
@Hans: I feel that an answer should have more content than just a wiki link, especially since Gadi noticed the similarity by himself. I'm sure someone who has more knowledge (i.e. any at all) about matroids than me will write up an informative answer. –  Miha Habič Aug 11 '11 at 13:04
@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.) –  Hans Lundmark Aug 11 '11 at 13:19
add comment

1 Answer

up vote 9 down vote accepted

The notion you are looking for are matroids.

share|improve this answer
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). –  Gadi A Aug 11 '11 at 14:05
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.