My PhD student, Nate Vaduthala, and I have been working on a paper about flag matroids that will (hopefully) hit the arXiv in the next week or two. In this blog post, I will give an introduction to flag matroids with particular attention to representability questions, and then state one of our results about flag matroids that are representable over the field of order 2.
Given a field $\mathbb{K}$ and a finite set $E$, we let $\mathbb{K}^E$ denote the $\mathbb{K}$-vector space with a distinguished set of coordinates indexed by $E$. Each $S \subseteq E$ gives a coordinate projection $\pi_S: \mathbb{K}^E \rightarrow \mathbb{K}^S$ that sends each $(x_e)_{e \in E}$ to $(x_e)_{e \in S}$. Each linear subspace $L \subseteq \mathbb{K}^E$ defines a representable matroid $\mathcal{M}_L$ where $S \subseteq E$ is independent whenever $\pi_S(L)$ has dimension $|S|$. Thus one can view matroids as a combinatorial abstraction of linear subspaces.
Now suppose we have two nested linear subspaces $L_1 \subsetneq L_2 \subseteq \mathbb{K}^E$. Then every flat of $\mathcal{M}_{L_2}$ is a flat of $\mathcal{M}_{L_1}$, as the reader might be able to deduce. In light of this, given two matroids $\mathcal{M}$ and $\mathcal{N}$ on the same ground set $E$, one says that $\mathcal{N}$ is a lift of $\mathcal{M}$ if every flat of $\mathcal{N}$ is a flat of $\mathcal{M}$.
Finally, suppose we have a flag, i.e. a sequence of nested linear subspaces $L_1 \subsetneq \dots \subsetneq L_k \subseteq \mathbb{K}^E$. Then $\mathcal{M}_{L_{i+1}}$ is a lift of $\mathcal{M}_{L_i}$ for each $i$. Then, a sequence of matroids $\mathfrak{F} = (M_1,\dots,M_k)$ on the same ground set $E$ is called a flag matroid if $M_{i+1}$ is a lift of $M_i$ for each $i$. This implies that ${\rm rank}(M_i) < {\rm rank}(M_{i+1})$. If ${\rm rank}(M_{i+1}) = {\rm rank}(M_i) + 1$ for each $i$, then we say that $\mathfrak{F}$ is saturated. A flag matroid $\mathfrak{F}$ that can be expressed as $\mathcal{M}_{L_1},\dots,\mathcal{M}_{L_k}$ for a flag $L_1 \subsetneq \dots \subsetneq L_k$ of subspaces of a $\mathbb{K}$-vector space are called $\mathbb{K}$-representable and the corresponding sequence of linear spaces is called a $\mathbb{K}$-representation of $\mathfrak{F}$.
On a concrete level, a $\mathbb{K}$-representation of a flag matroid $\mathfrak{F} = (M_1,\dots,M_k)$ is a matrix $A \in \mathbb{K}^{r\times n}$ such that the first ${\rm rank}(M_i)$ rows of $A$ are a representation of $M_i$ for each $i$. For example, recall that $U_{r,n}$ denotes the uniform matroid of rank $r$ on $n$ elements and consider the flag matroid
$\mathfrak{F} = (U_{1,3},U_{2,3})$.
Then if $\mathbb{K}$ is a field with at least three elements, the following is a $\mathbb{K}$-representation of $\mathfrak{F}$
$\begin{pmatrix}1 & 1 & 1 \\ 0 & 1 & 2\end{pmatrix}$.
Note that if $\mathbb{K}$ is the field with two elements, then there is no $\mathbb{K}$-representation of $\mathfrak{F}$ even though both $U_{1,3}$ and $U_{2,3}$ are both $\mathbb{K}$-representable as matroids. Indeed, since the first row of such a matrix has to be a representation of $U_{1,3}$, this implies that the first row must be all ones, which will then imply that at least two of the columns are the same so the full matrix will not be a representation of $U_{2,3}$.
Given a field $\mathbb{K}$, one can ask: does there exist a “nice” characterization of the $\mathbb{K}$-representable flag matroids? Just as with matroids, we can do this by establishing a theory of minors for flag matroids, and then give a forbidden minor characterization. So far, we have been able to do this for saturated flag matroids that are representable over the fields with two and three elements.
Duals and Minors of flag matroids
The notions of deletion, contraction, and duality extend to flag matroids. Let $\mathfrak{F} = (M_1,\dots,M_k)$ be a flag matroid on ground set $E$. The dual of $\mathfrak{F}$, denoted $\mathfrak{F}^*$, is $(M_k^*,\dots,M_1^*)$ where $M^*$ denotes the dual of a matroid $M$. Given $e \in E$, we define the deletion and contraction $\mathfrak{F}\setminus e$ and $\mathfrak{F} / e$ by doing the corresponding operations on their constituent matroids, i.e.
$\mathfrak{F} \setminus e := (M_1 \setminus e, \dots, M_k \setminus e)$
and
$\mathfrak{F} / e := (M_1 /e, \dots, M_k / e)$.
If two constituent matroids become the same after deleting or contracting an element, we remove that matroid and reindex. Just as with matroids, contraction and deletion are dual operations, i.e.
$\mathfrak{F} / e = (\mathfrak{F}^*\setminus e)^*$.
Our theory of minors for flag matroids requires one more operation that does not have an analogue in the matroid setting. In particular, a flag matroid obtained from $\mathfrak{F}$ by removing a constituent matroid is called a chopping. Note that a chopping of a saturated flag matroid will only be saturated if the highest or lowest matroid is removed. Any flag matroid obtained from $\mathfrak{F}$ via a sequence of deletion, contraction, and chopping operations is called a minor of $\mathfrak{F}$.
Proposition. Let $\mathfrak{F}$ be a flag matroid and let $\mathbb{K}$ be a field. Then if $\mathfrak{F}$ is $\mathbb{K}$-representable, so is $\mathfrak{F}^*$ and any minor of $\mathfrak{F}$.
In principle, the above proposition allows us to characterize the class of $\mathbb{K}$-representable flag matroids by giving a list of minimally non-$\mathbb{K}$-representable minors. When $\mathbb{K}$ has two elements, we have the following forbidden minor characterization of the $\mathbb{K}$-representable flag matroids.
Theorem: Let $\mathfrak{F}$ be a saturated flag matroid. Then $\mathfrak{F}$ is representable over the two-element field if and only if $\mathfrak{F}$ has no minors of the form $(U_{1,3},U_{2,3})$ or $U_{2,4}$.
We also have a forbidden-minor characterization for the saturated flag matroids that are representable over the field with three elements. We use the notation $F_7$ to denote the fano matroid and $F_7^*$ to denote its dual.
Theorem: Let $\mathfrak{F}$ be a saturated flag matroid. Then $\mathfrak{F}$ is representable over the three element field if and only if $\mathfrak{F}$ has no minors of the form $R$ or $(R/e, R \setminus e)$ where $R \in \{U_{2,5},U_{3,5},F_7,F_7^*\}$.
Within the next week or two, we hope to have our preprint on the arXiv, so stay tuned! Flag matroids are an interesting and potentially quite fruitful line of research for matroid theorists, as many of the same questions about representability can be asked.