{"id":180,"date":"2013-09-09T17:53:13","date_gmt":"2013-09-09T21:53:13","guid":{"rendered":"http:\/\/matroidunion.org\/?p=180"},"modified":"2013-09-09T17:53:13","modified_gmt":"2013-09-09T21:53:13","slug":"non-matroidal-matroids-i","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=180","title":{"rendered":"Non-matroidal matroids I"},"content":{"rendered":"

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<\/em>, symplectic matroids<\/em>, Coxeter matroids<\/em>, 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<\/em>, by Borovik, Gelfand, and White.<\/p>\n

I’ll start with something fairly simple: flag matroids<\/em>. 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<\/em> 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$.<\/p>\n

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$.<\/p>\n

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
\n\\begin{multline*}
\nw^{-1}(a_{1}) < w^{-1}(a_{2}) < \\cdots < w^{-1}(a_{k})\\quad\n\\text{and}\\\\\nw^{-1}(b_{1}) < w^{-1}(b_{2}) < \\cdots < w^{-1}(b_{k}).\n\\end{multline*}\nThen 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:\n\nTheorem.<\/strong> 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}$.<\/p>\n

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<\/em> to mean a subset $B\\in \\mathcal{B}$ such that $A\\leq^{w} B$ for every $A\\in\\mathcal{B}$. By maximal member<\/em>, I mean a subset $B\\in \\mathcal{B}$ such that $A\\in \\mathcal{B}$ and $B\\leq^{w} A$ implies $A=B$.<\/p>\n

Proof.<\/em> 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$.<\/p>\n

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$<\/p>\n

Now let us a define a flag<\/em> 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}$.<\/p>\n

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.<\/p>\n

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.<\/p>\n","protected":false},"excerpt":{"rendered":"

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, … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-180","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/180","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=180"}],"version-history":[{"count":53,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/180\/revisions"}],"predecessor-version":[{"id":236,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/180\/revisions\/236"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=180"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=180"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=180"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}