For a while now I’ve been curious about some objects in algebraic geometry that have the word “matroid” attached to them, although they are not strictly speaking matroids in Whitney’s sense. There are several varieties of such objects: flag matroids, symplectic matroids, Coxeter matroids, and so on. I’m going to make it my mission to learn about these objects, and seeing as they best way to learn a new topic is to write about it, the fruits of my labours will appear here. For the most part, I’m going to be relying on the book Coxeter Matroids, by Borovik, Gelfand, and White.
I’ll start with something fairly simple: flag matroids. The most straightforward definition (at least from the perspective of an “ordinary matroid” theorist) involves quotients. Let $M$ be an ordinary matroid. We say that the matroid $Q$ is a quotient of $M$ if there exists a matroid, $N$, such that $N\backslash X=M$ for some $X\subseteq E(N)$, and $N/X=Q$. In other words, $Q$ is a quotient of $M$ if it can be obtained from $M$ by extending with a set of elements, and then contracting that set. There are many equivalent conditions for $Q$ to be a quotient of $M$. For example, we could equivalently say that $M$ and $Q$ have the same ground set, and every circuit in $M$ is a union of circuits in $Q$.
Now a flag matroid is easily understood: a flag matroid is a sequence $(M_{1},\ldots, M_{m})$ of ordinary matroids, such that $M_{i}$ is a quotient of $M_{i+1}$ for all $i\in\{1,\ldots, m-1\}$. Note that this implies that $M_{i}$ is a quotient of $M_{j}$ for all $j>i$. An ordinary matroid is therefore just a flag matroid in the case that $m=1$.
Stated in this way, the definition doesn’t seem very appealing. However there is an equivalent characterization (used by Borovik et al. use as their primary definition) which is more promising from the point of view of allowing generalizations. For this characterization, we need to introduce an ordering on $k$-element subsets of a finite set. Let $[n]$ be the set $\{1,\ldots, n\}$, and let $w$ be a permutation of $[n]$. Let $A$ and $B$ be $k$-element subsets of $[n]$. We will assume that $A=\{a_{1},\ldots, a_{k}\}$ and $B=\{b_{1},\ldots, b_{k}\}$, where
\begin{multline*}
w^{-1}(a_{1}) < w^{-1}(a_{2}) < \cdots < w^{-1}(a_{k})\quad
\text{and}\\
w^{-1}(b_{1}) < w^{-1}(b_{2}) < \cdots < w^{-1}(b_{k}).
\end{multline*}
Then we declare that $A\leq^{w} B$ if $w^{-1}(a_{i})\leq w^{-1}(b_{i})$ for all $i\in \{1,\ldots, k\}$. It helps me to conceptualise this definition in the following way: arrange two copies of the sequence $w(1),w(2),\ldots, w(n)$ on top of each other. In the top row, highlight the members of $A$, and in the bottom row highlight the members of $B$. Draw a line from the first member of $A$ to the first member of $B$, from the second member of $A$ to the second member of $B$, and so on. If $A\leq^{w} B$, then all the lines that you have just drawn are either vertical or slope down from left to right. If we use this trick, then it becomes trivial to see that $\leq^{w}$ is a partial order on the $k$-element subsets of $[n]$. In 1968, Gale characterized matroids as follows:
Theorem. Let $\mathcal{B}$ be a collection of $k$-element subsets from $[n]$. Then $\mathcal{B}$ is the family of bases of a matroid if and only if, for every permutation $w$ of $[n]$, there is a subset $B\in \mathcal{B}$ such that $A\leq^{w} B$ for every $A\in \mathcal{B}$.
Gale’s proof is short, and quite pleasant, so I include it. Given $\mathcal{B}$, a collection of $k$-element subsets of $[n]$, and $w$, a permutation of $[n]$, I will use the phrase upper bound to mean a subset $B\in \mathcal{B}$ such that $A\leq^{w} B$ for every $A\in\mathcal{B}$. By maximal member, I mean a subset $B\in \mathcal{B}$ such that $A\in \mathcal{B}$ and $B\leq^{w} A$ implies $A=B$.
Proof. First assume that $\mathcal{B}$ is the family of bases of a matroid, but that there is a permutation, $w$, such that $\mathcal{B}$ has no upper bound under $\leq^{w}$. Because there are only finitely many $k$-element subsets of $[n]$, there exists a maximal member of $\mathcal{B}$ under $\leq^{w}$. In fact, there must be at least two maximal members of $\mathcal{B}$, for if there is only one, then that member is an upper bound. Let $A$ and $B$ be distinct maximal members of $\mathcal{B}$. Let $x$ be the first element in the sequence $w(1),\ldots, w(n)$ that is in the symmetric difference of $A$ and $B$. Without loss of generality we can assume that $x\in A$. By basis-exchange, there is an element $y\in B-A$ such that $(A-x)\cup y$ is in $\mathcal{B}$. However $A\leq^{w} (A-x)\cup y$, so we have a contradiction to the maximality of $A$.
Now we prove the converse. Let $A$ and $B$ be members of $\mathcal{B}$, and let $x$ be in $A-B$. Assume that $t=|B-A|$. Choose the permutation $w$ so that the last $k+t$ elements in the sequence $w(1),\ldots, w(n)$ are $x$, then the $t$ elements of $B-A$, and then the $k-1$ elements of $A-x$. Let $C$ be the upper bound in $\mathcal{B}$ relative to $\leq^{w}$. Because $A\leq^{w} C$ it follows that $A-x\subseteq C$. Because $B\leq^{w} C$ it follows that the element in $C-A$ must be in $B-A$. Therefore $C=(A-x)\cup y$ for some $y\in B-A$, and the basis-exchange property holds.$\quad\square$
Now let us a define a flag on the set $[n]$ to be a sequence, $(F_{1},\ldots, F_{m})$, of subsets such that $F_{1}\subset F_{2}\subset \cdots \subset F_{m}\subseteq [n]$. Let $\mathcal{F}$ be a collection of flags on $[n]$ and assume that there is a sequence of integers, $(k_{1},\ldots, k_{m})$, such that $|F_{i}|=k_{i}$ whenever $(F_{1},\ldots, F_{m})$ is in $\mathcal{F}$ and $i$ is in $\{1,\ldots, m\}$. This means that the $i$-th components of flags in $\mathcal{F}$ all have the same cardinality. If $F=(F_{1},\ldots, F_{m})$ and $G=(G_{1},\ldots, G_{m})$ belong to $\mathcal{F}$, and $w$ is again a permutation of $[n]$, then we say that $F\leq^{w} G$ if $F_{i}\leq^{w} G_{i}$, for every $i\in \{1,\ldots, m\}$. We can define a flag matroid in the following way: $\mathcal{F}$ is a flag matroid if and only if, for every permutation $w$ of $[n]$, there is a flag $G\in \mathcal{F}$ such that $F\leq^{w} G$ for every $F\in \mathcal{F}$.
From this definition and from Gale’s theorem, we see that if we take the $i$-th components of all flags in $\mathcal{F}$, we obtain the family of bases of a matroid, $M_{i}$. The sequence $(M_{1},\ldots, M_{m})$ is the sequence of quotients I referred to earlier. The fact that the definitions are equivalent follows from Theorem 1.7.1 in Borovik et al.
Generalizations such as symplectic matroids and Coxeter matroids arise from this definition by removing the requirement that $w$ comes from the symmetric group $Sym([n])$, and instead using another permutation group. I’ll write more about these generalizations next time.
Those interested in Coxeter matroids might wish to read a review in Mathematical Reviews of the book “Coxeter matroids” as well as a book review in SIAM Review, Volume 56, 577–579. I’ll be happy to email a copy of the review on request.
Joseph,could you please email me a copy of that review?
(Dillon, Stefan, Peter, Irene: very happy to discover your blog!)
You say “Stated in this way, the definition doesn’t seem very appealing,” but in fact I find your first definition more appealing than the second. For instance, using the first definition I can immediately construct an enormous collection of horrific flag matroids, whereas the second definition seems a lot less constructive.
Gale’s theorem is very nice, though!
I haven’t looked at the book, nor Joseph’s review, nor the literature, but your last paragraph immediately sparks the following question: what if you plug a different group into Gale’s result? Is there, for instance, a group that gives you greedoids?
Fair enough; this is obviously pretty subjective. For me though, the first definition seems a bit arbitrary. Why do we choose a sequence of quotients, instead of, say, a sequence of weak maps, or maybe a sequence of truncations? In the second definition, I can see a clearer line to ordinary matroids, so the generalization seems a little more motivated.
I don’t know if you can define greedoids in this way. It would be very nice if you could. This could be a good afternoon-coffee problem.
9-13-2013
Dear Dillon and Stefan,
There are only four infinite families of Coxeter groups, and two of them give the same Coxeter matroids. The way the Coxeter group A_n plugs in to give ordinary matroids is explained in the review in SIAM review, and it seems to me very special [it depends on cosets of parabolic subgroups of A_n being parametrized by subsets]. .
To get Greedoids in this framework would seem to me impossible, but I will be happy to be wrong on this.
Hi Joseph,
I agree, we are probably not going to get greedoids from Coxeter groups. In fact, greedoids may be difficult to deal with in this framework, because they are not defined by their bases. But I wonder if we can alter Gale’s Theorem and still get a characterization of matroids. In particular, I wonder what happens if we no longer restrict ourselves to groups. Gale’s Theorem says that $\mathcal{B}$ is a collection of bases if and only if there is an upper bound in $\mathcal{B}$ relative to $\leq^{w}$, for every $w$ in the symmetric group $\mathrm{Sym}([n])$. So does the theorem still hold if we replace the last clause with ‘for every $w$ in $S$’, where $S$ is just some set of permutations?
I think I would offer 60:40 odds on this being false. This isn’t necessarily based on any intuition, it’s just my preference for what the answer should be. So my conjecture is:
Let $S$ be any proper subset of the symmetric group $\mathrm{Sym}([n])$. There exists a family, $\mathcal{B}$, of $k$-element subsets of $[n]$ such that $\mathcal{B}$ is not the family of bases of a matroid, and yet $\mathcal{B}$ contains an upper bound relative to $\leq^{w}$, for every $w\in S$.
Pingback: Non-matroidal matroids II | The Matroid Union
Pingback: Non_matroidal matroids III | The Matroid Union