Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Hello everyone! First time poster, long time lurker here. I have a really basic question that has been bugging me for sometime. Specifically, I'm not exactly sure what the 'correct' category theoretic definition of a matroid should be. The only definition I know involves heavy use of set-theory, and is kind of clumsy:

Given a set $E$, a matroid $\mathcal{I} \subseteq 2^E$ is a non-empty collection of subsets which satisfy the following axioms:

  1. (Heredity) If $X \in \mathcal{I}$ and $X' \subset X$, then $X' \in \mathcal{I}$.

  2. (Exchange) If $X, Y \in \mathcal{I}$ and $|X| > |Y|$, then there exists some $b \in X \backslash Y$ such that $Y \cup \{ b \} \in \mathcal{I}$.

Given that both categories and matroids were introduced around the same time and both were studied by MacLane, it stands to reason that someone ought to have thought about this before. Also it is obvious from the Heredity axiom that each matroid is a category, since the containment relation is reflexive and transitive. The second property is a bit more difficult to model, as I am not sure how to get rid of the ugly element / cardinality operators.

In the optimal solution, it would be nice to get rid of the set $E$ entirely, and instead view the specific interpretation of the abstract matroid as a functor from $\mathcal{I} \to 2^E$, the power-set lattice. This would also suggest a functorial interpretation of the graph theoretic and linear algebra applications of matroids. I strongly suspect that someone has already done this, but am having great difficulty locating any references. (Of course I may also be totally wrong headed here too...)

share|improve this question
7  
Matroids were introduced by Hassler Whitney in 1935: jstor.org/stable/2371182 –  Igor Pak Mar 15 '10 at 2:13
2  
Why is what you gave not a category-theoretic definition of a matroid? I would think of a matroid as structure on E, just like a group or a vector space. Even to a category theorist, such a structure always has an underlying set and the definition of the structure involves elements of that set. –  Mike Shulman Mar 15 '10 at 3:12
1  
Using Yoneda's lemma, we can almost always reduce definitions of algebraic objects in a category to set-theoretic conditions on their hom-sets. (See, for example, the definition of a group object in Vistoli's notes on descent, where it is discussed as the first application of the Yoneda lemma in chapter 2). –  Harry Gindi Mar 15 '10 at 6:27
3  
@fpqc, "we can almost always reduce...": that's the kind of general statement that provides essentially no information! Can you do it in this case? –  Mariano Suárez-Alvarez Mar 15 '10 at 16:24
2  
"we can almost always reduce" - the statement in question is miles away from an algebraic statement like the ones about groups; it involves powersets and elements and thus a priori only makes sense in toposes (or quasitoposes or such things) i.e. in an environment where you can make sense of about any set theoretical (or mathematical) statement. The question however seemed to aim at a more low level formulation, i.e. something which makes sense in any category with products, or some other more modest doctrine like that. This might be possible but is far beyond some simple Yoneda application... –  Peter Arndt Mar 16 '10 at 3:45

1 Answer 1

up vote 8 down vote accepted

If I understand your question correctly, I believe that the problem is still open. That is, if we let $\mathcal{M}$ be the category of (simple) matroids, where the morphism are given by strong maps, then it is still open how to describe $\mathcal{M}$ by a nice set of axioms. However, partial progress has been made in this paper.

share|improve this answer
    
Thanks! This is exactly what I was looking for! I am somewhat shocked that this is still an open issue, since it seems like something that ought to have been sorted out long ago. –  Mikola Mar 16 '10 at 1:54
    
As an addendum, after reading the paper more carefully I realize that this is not properly an answer to the question, but I suppose it is probably the best that one can hope for now. –  Mikola Mar 16 '10 at 2:36
    
I was actually asking myself the same question, I also think it is a disgrace that there is no answer. But it looks as a general disgrace when you try to use the light of category theory on combinatorics. I'll be glad to know if you share the same feeling. –  Jérôme JEAN-CHARLES Nov 1 '10 at 1:56

Your Answer

 
discard

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.