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?

  • 4
    I think the notion you're looking for is a [matroid](http://en.wikipedia.org/wiki/Matroid).2011-08-11
  • 1
    @Miha: Write that as an answer, not as a comment. (Since it is in fact the answer to the question asked!)2011-08-11
  • 3
    It's cool you noticed such a striking resemblance. Cool to know. +12011-08-11
  • 1
    @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.2011-08-11
  • 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