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...)

  • 11
    Matroids were introduced by Hassler Whitney in 1935: jstor.org/stable/2371182 – Igor Pak Mar 15 '10 at 2:13
  • 5
    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
  • 4
    @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-Álvarez Mar 15 '10 at 16:24
  • 4
    "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
  • 3
    It seems that the operation of closure is more convenient for modelling it in categorical terms. We may think of the ground set of the matroid as a category (the objects are subsets of the ground set), and than the closure operation can be thought as an endofunctor CL, such that there is a natural transformation Id -> CL (that corresponds to the fact that a set is always a subset of its closure), and CL^2 = CL. Of course, it is just a rough idea, and there is lots of work to do. – Max Karev May 18 '13 at 17:58
up vote 15 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.

  • 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
  • 1
    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

I have come to the conclusion that a lot of mathematical structure on sets (e.g. constructs) can be defined through (combinations of) relations

$ (1) \quad S_X^F\subset F(X)\times X^{I} $

for some underlying set X, some functor $F$: Rel $\rightarrow$ Rel and some set $I$.

Examples:

  • Magmas (monoids, groups,...) are defined through functions $S\subset X^2\times X$.
  • Graphs are defined through relations $S\subset X\times X$.
  • Metric spaces could be defined through relations $S\subset (\mathbb{R}\times X)\times X$, where $((r,x),x')\in S\Leftrightarrow d(x,x')=r$. Or better: through $d(x,x')\le r$, since the category Met have retractions as morphisms.
  • Topological spaces could be defined by $S\subset 2^X\times X$, where $(M,x)\in S\Leftrightarrow x\in M\in\tau$ or by the closure $x\in \overline M$.
  • Uniform spaces could be defined through relations $S\subset 2^{X\times X}\times X^2$, where $(U,(x,y))\in S \Leftrightarrow (x,y)$ is U-close. (Wikipedia)

(See Can any construct be characterized as a relation?)

This works for any construct I know and there even seems to be a general rule to generate the morphisms between the constructs, showed by the (in general not commuting, if the relations not are functions) diagram of sets and relations: $\require{AMScd}$ \begin{CD} F(X) @>F(f)>> F(Y)\\ @V S_X^F V V(2) @VV S_Y^F V\\ X^{I} @>>f^{I}> Y^{I} \end{CD} $(2)\quad (\phi_X,\phi_Y)\in F(f)\Rightarrow [(\phi_X,(x_i)_I)\in S_X^F \Rightarrow (\phi_Y,((f(x_i))_I)\in S_Y^F]$.

Example: If $I=1$, $F$ is the (contravariant) functor defined as $2^X\overset{2^f}\longrightarrow 2^Y$, where $ (M,M')\in 2^f\Leftrightarrow M=f^{-1}(M')$ and $S_X^F$ is defined as $(M,x)\in S_X^{F}\Leftrightarrow x\in \overline{M}$.

Then due to $(2)$:

$M=f^{-1}(M')\Rightarrow (x\in \overline{M}\Rightarrow f(x)\in \overline{M\,'})$, so $x\in \overline{f^{-1}(M\,')}\Rightarrow f(x)\in \overline{M\,'}$. (Continuity).

In case of matroids $(X,\mathcal I)$ I can see two possibilities that fits into my scheme:

  1. $(A,x)\in S\Leftrightarrow x\in A\in\mathcal I$, that gives a condition for morphisms $f^{-1}(A')\in\mathcal I\Rightarrow A'\in\mathcal I'$;
  2. $(A,x)\in S\Leftrightarrow x\in cl(A)$, that gives the condition $r(f^{-1}(A'))=r(f^{-1}(A')\cup\{x\})\Rightarrow r(A')=r(A'\cup\{f(x)\})$, where $cl(A)=\{x\in X|r(A)=r(A\cup\{x\})\}$ and $r$ is the rank function.

It seems to me as the former definition of a morphism is more natural, given the scheme, since the exchange axiom doesn't have to affect the form of the morphism more than associativity affect the form of the group homomorphism. So my primary candidate is:

A function $f:X\rightarrow X'$, where $(X,\mathcal I)$ and $(X',\mathcal I')$ are matroids, is a morphism if it holds for any set $A'\subseteq X'$ that $f^{-1}(A')\in\mathcal I \Rightarrow A'\in\mathcal I'$.

I don't claim that this is the answer and I can't evaluate the result because of lack of experience of matroids, but this is what I got from the empirical scheme.

The following related article was recently published:

Heunen, C. & Patta, V. Appl Categor Struct (2018) 26: 205. https://doi.org/10.1007/s10485-017-9490-2

In section 9, the authors give a categorical characterization of matroids based on the "greedy algorithm characterization"; very roughly speaking, the optimality of the greedy algorithm for all possible weight functions is encoded as the property that the limits of certain diagrams are all the same. The paper also begins with a nice discussion of the various properties of the category of matroids and strong maps mentioned in Tony Huynh's answer.

Before attempting to categorify Matroids, we need to bear in mind the entirety of their structural properties.

The class of Matroids is the intersection of the class of Greedoids with the class of Independence (i.e. Hereditary) systems. If we abstract the independent sets as points in a finite poset, then Independence systems are just Downsets. Greedoids have a more complicated description. If we can form a category of sub-posets of these sorts, then that may be a way forward.

Categorifying Independence systems (E, I) is, however, already an interesting challenge: not only do they have the customary isomorphisms mapping elements to elements (E1->E2), they also have cryptomorphisms (if I may steal and narrow the application of a term), generated by the (complementary) dual (c) and blocker (b) operations, which commute with the isomorphisms. Since c and b are involutions on independence systems, the cryptomorphisms are invertible and therefore preserve structure, but do so in a non-obvious way. The map from the set of bases to the set of circuits is one such cryptomorphism; its inverse maps the set of bases to the set of hyperplanes.

These cryptomorphisms are operations mapping sets to sets, not elements to elements, and so are set-theoretically higher-order isomorphisms. What is the best category theory model for this? Since these maps are well-defined on the class of all independence systems, are they best-described as functors? If so, can category theory deduce them? If not, does category theory need subsuming into a more powerful instrument of mathematical abstraction?

But if category theory can deduce b and c, then can we use it to discover cryptomorphic operations other than those generated by {b, c}?

  • If you have a new question (as suggested by the last two paragraphs of your post), then ask it on a new page, not as an answer. – Alex M. Aug 12 '17 at 11:37
  • If you have a new question, please ask it by clicking the Ask Question button. Include a link to this question if it helps provide context. - From Review – abx Aug 12 '17 at 12:54
  • @abx: I have reviewed and flagged this as "not an answer", but "a moderator reviewed your flag, but found no evidence to support it". Do moderators read flagged posts before making a decision? Maybe try your chances and flag it too? – Alex M. Aug 12 '17 at 15:21
  • So far as I know, these are structurally important, but open, questions pertinent to the original enquiry. I raised them in the hope of prompting further research. – Zoe Porphyrogenita Sep 7 '17 at 17:00
  • @ZoePorphyrogenita the point of the comments above is that on this site, questions should be asked separately, not posted as answers. – j.c. Sep 14 '17 at 23:01

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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