Partial fields give a more flexible theory of matroid representation than mere fields. Rather than committing to a field, a partial field allows you to capture several representations at once. They were first introduced by Semple and Whittle [SW96]. The archetypical example is the following theorem by Tutte:

Theorem 1. The following statements are equivalent for a matroid $M$:

1. $M$ is representable over both $\text{GF}(2)$ and $\text{GF}(3)$;
2. $M$ is representable over $\text{GF}(2)$ and some field of characteristic other than $2$;
3. $M$ is representable over $\mathbb{R}$ by a totally unimodular matrix;
4. $M$ is representable over every field.

Matroid representations over partial fields generalize totally unimodular matrices, as we will see below. We know that regular matroids (i.e. the matroids from Theorem 1) possess many interesting properties. Let $\mathcal{M}$ be the class of regular matroids.

1. The excluded minors for $\mathcal{M}$ are $U_{2,4}$, $F_7$, and $F_7^*$.
2. Every regular matroid is uniquely representable over every field (up to row operations and column scaling).
3. All regular matroids can be obtained from graphic matroids and $R_{10}$ by dualizing and 1-, 2-, 3-sums (this is Seymour’s Decomposition Theorem).
4. A simple, regular matroid of rank $r$ has at most ${r+1 \choose 2}$ elements, with equality for the graphic matroids of complete graphs.
5. If $A$ is a totally unimodular matrix of full row rank representing $M$, then $\det(A A^T)$ equals the number of bases of $M$.

For every partial field $\mathbb{P}$, one may ask if analogues of these properties exist for the class of $\mathbb{P}$-representable matroids. This is an area of research with a number of interesting results and many unsolved problems.

In this post I will limit myself to introducing matroid representation over partial fields, linking them to the definition of totally unimodular matrices, and giving some examples. In my next post I will discuss Whittle’s characterization [Whi95, 97] of the representations of ternary matroids.

1. Definitions

The definition of a partial field is straightforward:

Definition 2. A partial field is a pair $\mathbb{P} = (R, G)$, where $R$ is a commutative ring, and $G$ is a subgroup of the invertible elements of $R$ such that $-1 \in G$.

I will introduce matroid representations over partial fields through chain groups. For fields, this corresponds to the row space of the representation matrix. The advantage is a very clean basic theory, plus an extension to noncommutative rings at no extra cost. Incidentally, this is how Tutte himself thought about regular matroids.

Definition 3. Let $R$ be a ring, and $E$ a finite set. A chain group is a subset $C \subseteq R^E$ such that, for $c, d \in C$ and $r \in R$,

1. $0 \in C$;
2. $c+d \in C$;
3. $rc \in C$.

The elements of a chain group are called chains.

Definition 4. The support of a chain $c\in C$ is
$$\| c \| := \{e \in E : c_e \neq 0\}.$$

A nonzero chain with inclusionwise minimal support is called elementary.

Definition 5. Let $G \subseteq R$. A chain $c \in R^E$ is $G$-primitive if $c \in (G\cup\{0\})^E$.

Definition 6. Let $\mathbb{P} = (R, G)$ be a partial field, and $E$ a finite set. A chain group $C \subseteq R^E$ is a $\mathbb{P}$-chain group if, for every elementary chain $c$ there exists an $r\in R$ such that $c = rg$ for some $G$-primitive chain $g$.

I realize this was a fairly long string of definitions, but the payoff is that we can very quickly define matroid representations:

Theorem 7. Let $\mathbb{P}$ be a partial field, and $C$ a $\mathbb{P}$-chain group. Define
$$\mathcal{C}^* := \{ \|c\| : c \in C, \text{ elementary}\}.$$
Then $\mathcal{C}^*$ is the collection of cocircuits of a matroid, $M(C)$.

Proof. We verify the (co)circuit axioms.

1. $\emptyset\not\in \mathcal{C}^*$.
   An elementary chain was defined to be nonzero.
2. If $C, D \in \mathcal{C}^*$ and $C \subseteq D$ then $C = D$.
   The supports of elementary chains are inclusionwise minimal.
3. If $C, D \in \mathcal{C}^*$ are distinct, and $e \in C \cap D$ then there is a member $F \in \mathcal{C}^*$ with $F \subseteq (C\cup D) – \{e\}$.
   Let $c, d$ be chains with $\|c\| = C$ and $\|d\| = D$. Since these chains are elementary, we may assume they are $G$-primitive, i.e. every nonzero entry is invertible. Now write
   $$g := c_e^{-1} c – d_e^{-1} d.$$
   Then $g$ is nonzero, and therefore there is an elementary chain $f$ whose support is contained in that of $g$. We simply take $F = \|f\|$. $\square$

Definition 8. We say a matroid $M$ is $\mathbb{P}$-representable if there exists a $\mathbb{P}$-chain group $C$ such that $M = M(C)$.

One thing to note is that everything above holds even if we don’t assume $R$ to be commutative. This theory of skew partial fields was explored in [PZ13]. For the remainder of this post we’ll stick to the commutative case, though.

2. Restrictions on determinants

If you’ve seen totally unimodular matrices defined, you’ve probably seen a definition involving determinants. This also works for partial fields:

Definition 9. Let $\mathbb{P} = (R, G)$ be a partial field. A $\mathbb{P}$-matrix is a matrix $A$ with entries in $R$ such that each square submatrix has a determinant in $G \cup \{0\}$.

We denote by $A[X]$ the submatrix of $A$ with columns indexed by $X$.

Theorem 10. Let $\mathbb{P} = (R, G)$ be a partial field, and $A$ a $\mathbb{P}$-matrix with $r$ rows and columns indexed by $E$. Define
$$\mathcal{B}_A := \{ X \subseteq E : |X| = r \text{ and } \det(A[X]) \neq 0\}.$$
If this set is nonempty, then $\mathcal{B}_A$ is the set of bases of a matroid, $M[A]$.

Proof. We use a trick from commutative algebra. Let $I$ be a maximal ideal of $R$. Such an ideal is guaranteed to exist (assuming the axiom of choice). Then $\mathbb{F} := R/I$ is a field. Consider the ring homomorphism $\phi: R \to \mathbb{F}$ sending $r$ to $r + I$. Since this is a homomorphism, it commutes with addition and multiplication. Hence, if we apply it to the entries of $A$, we preserve the nonzero determinants. Since we have a matroid after applying $\phi$, we must have had a matroid before. $\square$

The link with the previous section is simple:

Theorem 11. Let $C$ be the chain group generated by the rows of a $\mathbb{P}$-matrix $A$. Then $C$ is a $\mathbb{P}$-chain group and $M(C) = M[A]$.

We also have a converse:

Theorem 12. Let $C$ be a $\mathbb{P}$-chain group, let $B$ be a basis of $M(C)$, and let $A$ be the matrix whose rows are $G$-primitive chains such that their supports form the $B$-fundamental cocircuits of $M(C)$. Then $A$ is a $\mathbb{P}$-matrix, and $M[A] = M(C)$.

This post is already getting long, so I will skip the proof and refer to [PZ13, Section 3.4] instead.

3. Examples

The key takeaway from the proof of Theorem 10 is the idea of a homomorphism:

Definition 13. Let $\mathbb{P}_1 = (R_1, G_1)$ and $\mathbb{P}_2 = (R_2, G_2)$ be partial fields, and let $\phi: R_1 \to R_2$ be a ring homomorphism such that $\phi(G_1) \subseteq G_2$. Then $\phi$ is a partial field homomorphism.

Theorem 14. If $\phi$ is as above, then every $\mathbb{P}_1$-representable matroid is also $\mathbb{P}_2$-representable.

We omit the proof, which is only a slight modification of the proof of Theorem 10. Note that we can identify a field $\mathbb{F}$ with the partial field $(\mathbb{F}, \mathbb{F}^*)$.

The regular partial field is $\mathbb{U}_0 = (\mathbb{Z}, \{-1, 1\})$. The $\mathbb{U}_0$-matrices are precisely the totally unimodular matrices. There is clearly a partial field homomorphism to any partial field, so regular matroids are, in fact, representable over every partial field too!

The dyadic partial field is $\mathbb{D} = (\mathbb{Z}[\frac{1}{2}], \langle -1, 2 \rangle)$. This means that we extended the ring of integers with all powers of $\frac{1}{2}$, and consider matrices where all subdeterminants are, in absolute value, a (positive or negative) power of $2$. There is a ring homomorphism to every field of characteristic other than 2.

The golden ratio partial field is $\mathbb{G} = (\mathbb{Z}[\tau], \langle -1, \tau\rangle)$, where $\tau$ is the golden ratio, i.e. the positive root of $x^2 – x – 1 = 0$. There is a homomorphism to a number of fields, notably $\text{GF}(4)$ and $\text{GF}(5)$. In fact, it can be shown that a matroid has a golden ratio representation if and only if it is representable over both $\text{GF}(4)$ and $\text{GF}(5)$.

The partial field $\mathbb{P}_4$ is defined as follows. Let $\alpha$ be an indeterminate, let $G$ be the subgroup of the units of $\mathbb{Q}(\alpha)$ generated by $\{-1, \alpha, \alpha-1, \alpha + 1, \alpha – 2\}$, and let $R$ be the smallest subring of $\mathbb{Q}(\alpha)$ containing $G$. There is a partial field homomorphism to every field with at least four elements (obtained by mapping $\alpha$ to any element other than $0, 1, -1, 2$). Let me end with a conjecture about this partial field:

Conjecture 15. A matroid is representable over all fields with at least four elements if and only if it is representable over $\mathbb{P}_4$.

Note that the partial fields for the corresponding statements for two and three elements are known: they are, respectively, the regular and near-regular partial fields.

For a bigger catalog of partial fields, including a list of homomorphisms between them, I refer to the appendix of my PhD Thesis, [vZ09].

References

[SW96] Charles Semple and Geoff Whittle. Partial fields and matroid representation. Adv. in Appl. Math., 17(2):184–208, 1996.

[PZ13] R.A. Pendavingh, S.H.M. van Zwam. Skew partial fields, multilinear representations of matroids, and a matrix tree theorem. Advances in Applied Mathematics, Vol. 50, Issue 1, pp. 201-227, 2013 (PDF, arXiv, doi).

[Whi95]  Geoff Whittle. A characterisation of the matroids representable over GF(3) and the rationals. J. Combin. Theory Ser. B, 65(2):222–261, 1995.

[Whi97]  Geoff Whittle. On matroids representable over GF(3) and other fields. Trans. Amer. Math. Soc., 349(2):579–603, 1997.

[vZ09] Stefan H. M. van Zwam. Partial Fields in Matroid Theory. PhD thesis, Technische Universiteit Eindhoven, 2009.

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.

Guest post by Jim Geelen.

Bert Gerards, Geoff Whittle and I have deleloped a structure theory for minor-closed classes of matroids representable over a given finite field; our results are of a similar flavour to the Graph Minors Structure Theorem of Robertson and Seymour [RS03]. I believe that a similar structure theory should emerge for any minor-closed class that omits a uniform matroid; see [Gee08]. However, the tools and intuition that we have developed for addressing matroids over finite fields fail when we consider minor-closed classes that contain all uniform matroids. Is this barrier the natural end of structure theory?

This question has led me to the following natural problem.

Problem 1: Describe the class of matroids with no $M(K_4)$-minor.

What kind of description do I want?

This is a complicated question for which I have no good answer. Whitney, himself, got away with posing the vague problem of characterizing the representable matroids, and I’m hoping for similar leniency here.

Pendavingh and van der Pol [PvdP] give a lower bound on the number of $n$-element matroids with no $M(K_4)$-minor that is asymptotic to Knuth’s lower bound [Knu74] on the number $n$-element matroids. In particular, the bound grows faster than $2^{p(n)}$ for any polynomial $p(n)$, making it quite difficult to give a rigorous complexity theoretic definition of a description.

What do we know?

Let $EX(M(K_4))$ denote the class of matroids with no $M(K_4)$-minor. Obviously $EX(M(K_4))$ is closed under minors, duality, direct sums, and $2$-sums.

Let $e$ be an element of a matroid $M$ and let $F$ be a flat of $M\backslash e$. If $F\cup \{e\}$ is a cyclic flat of $M$ and each cyclic flat of $M$ that contains $e$ also contains $F$, then we call $M$ a principal extension of $M\backslash e$. The following result implies that $EX(M(K_4))$ contains all transversal matroids and, hence, all gammoids.

Lemma 1: $EX(M(K_4))$ is closed under principal extension.

Proof.
Suppose that $M$ is obtained from $M\backslash e$ by principal extension into the flat $F$ and that $M\backslash e$ has no $M(K_4)$-minor. Toward a contradiction suppose that $D$ and $C$ are disjoint sets such that $M\backslash D/ C$ is isomorphic to $M(K_4)$. By possibly removing elements we may assume that $C\subseteq \{e\}$ and that $D\subseteq F$. Since one cannot obtain an $M(K_4)$-minor by parallel-extension, $r_M(F)\ge 2$. Each element of $M(K_4)$ is on the intersection of two triangles but $e$ is not, so $C=\{e\}$.

Consider a triangle $T$ of $M(K_4)$. If $T$ is independent in $M$, then $F$ is contained in the closure of $T\cup \{e\}$. Since $r(F)\ge 2$, at most two of the triangles of $M(K_4)$ become independent in $M$. Thus at least two of the triangles remain. Since $M(K_4)$ is not a restriction of $M\backslash e$, exactly two of the triangles remain. Let $f$ be the unique point not on one of those two triangles. Now it is easy to check that $\{e,f\}$ spans $F$ and $M/ f\backslash e$ has an $M(K_4)$-minor. $\Box$

The constructions described so far preserve representability, here is a construction that does not; the proof is obvious and omitted.

Lemma 2: $EX(M(K_4))$ is closed under the relaxation of circuit hyperplanes.

This is close to all that I know about the class.

Connectivity does not help

Matroid structure theory is built upon the founding principal that structure smooths out with increased connectivity. Unfortunately, this is just not the case for the class of matroids with no $M(K_4)$-minor. For each matroid $M$ we can construct, via principal extension, a round matroid $M’$ such that $M$ has an $M(K_4)$-minor if and only if $M’$ does. (A round matroid is one with infinite vertical connectivity.)

I don’t really know where to go from here, but we may learn something by retreating into some easier classes.

Sparse paving matroids

Motivated by the conjecture that almost all matroids are sparse paving and by the result in [PvdP] that there are many sparse paving matroids with no $M(K_4)$-minor, this seems to be a natural class to consider.

Problem 2: Describe the class of sparse paving matroids with no $M(K_4)$-minor.

This problem looks complicated, even in rank 3. In higher rank, there are quite subtle constructions. Let $k$, $n$, and $m$ be positive integers with $k\le m$ and let $S(k,m,n)$ be the collection of all $k$-element subsets of $\{1,\ldots,n\}$ whose elements sum to $m$ modulo $n$. Now let $M(k,m,n)$ be the rank-$k$ matroid on $\{1,\ldots,n\}$ whose nonspanning circuits are $S(k,m,n)$. Now $M(k,m,n)$ is clearly a sparse paving matroid. Pendavingh and van der Pol prove that, if $n$ is odd, then
$M(k,m,n)$ has no $M(K_4)$-minor. This construction leads to an enormous number of $n$-element sparse paving matroids with no $M(K_4)$-minor since we can relax any subset of the circuit-hyperplanes $S(k,m,n)$ in $M(k,m,n)$.

This diversion into the class of sparse paving matroids does not look that promising. However, sparse paving matroids are, themselves, highly structured. They are both a single lift of a uniform matroid and a single projection of a uniform matroid. It might be necessary to take the class of sparse paving matroids with no $M(K_4)$-minor as one of the building blocks for $EX(M(K_4))$.

Back to finite fields

Having failed to come up with any significant general insights into matroids with no $M(K_4)$-minor, I will return to the comfort of finite fields, where we know considerably more. This is not likely to shed much light on the general problem, but interesting questions remain nonetheless.

For binary and ternary matroids we have exact characterizations due to Tutte and Oxley, respectively. Note that it suffices to characterize the $3$-connected matroids in the class.

Theorem 1: Every $3$-connected binary matroid with at least $4$ elements has an $M(K_4)$-minor.

Theorem 2: If $M$ is a $3$-connected ternary matroid with no $M(K_4)$-minor, then either $M$ is a whirl or $M$ is isomorphic to a minor of a particular $12$-element matroid $S(5,6,12)$.

For arbitrary finite fields we have a bound on the branch-width [GGW07].

Theorem 3: For each finite field $\mathbb{F}$ there is an integer $k$ such that, if $M$ is an $\mathbb{F}$-representable matroid with no $M(K_4)$-minor, then $M$ has branch-width at most $k$.

That theorem holds more generally with $K_4$ replaced with any planar graph. One would hope to be able to say more for $K_4$.

Conjecture: For each finite field $\mathbb{F}$ there are only finitely many vertically $4$-connected $\mathbb{F}$-representable matroids with no $M(K_4)$-minor.

In fact, I hope for even more, one should be able to describe how to construct all $3$-connected $\mathbb{F}$-representable matroids with no $M(K_4)$-minor. The construction should involve some thin infinite classes, a finite set of exceptional matroids, and a $3$-sum operation. One important thin class is the set of free spikes, and the matroids obtained from these by adding other points freely to the legs. Another thin class is constructed in a similar way from whirls. The $3$-sum operation needs to be carefully defined so that it does not construct $M(K_4)$-minors. For example, suppose that $M_1$ and $M_2$ are matroids, $E(M_1)\cap E(M_2) = L$, and $a,b\in L$ such that $L$ is a line of both $M_1$ and $M_2$, $L$ is modular in $M_2$, each point of $M_2$ in $L-\{a,b\}$ is freely placed on $L$, and neither $M_1$ nor $M_2\backslash (L-\{a,b\})$ has an $M(K_4)$-minor. Now let $M$ be obtained from the modular sum of $M_1$ and $M_2$ on $L$ by deleting $L-\{a,b\}$. Then $M$ has no $M(K_4)$-minor.

References

[Gee08]
J. Geelen,
Some open problems on excluding a uniform matroid,
Adv. in Appl. Math. 41 (2008), 628-637.

[GGW07]
J. Geelen, B. Gerards, G. Whittle,
Excluding a planar graph from GF$(q)$-representable matroids,
J. Combin. Theory, Ser. B 97 (2007), 971-998.

[Knu74]
D.E. Knuth,
The asymptitic number of geometries,
J. Combin. Theory, Ser. A 17 (1974), 398-400.

[RS03]
N. Robertson, P.D. Seymour,
Graph Minors. XVI. Excluding a non-planar graph,
J. Combin. Theory, Ser. B 89 (2003), 43-76.

[PvdP]
R.A. Pendavingh, J.G. van der Pol,
Counting matroids in minor-closed classes,
arXiv:1302.1315v3 [math.CO].

In this post I will define some matroids on graphs and give some examples. Such examples include graphic matroids, bicircular matroids and Dowling geometries. These matroids arise in different contexts and this led to a profusion (and confusion) of terminology. As a consequence, it’s really difficult to look up literature and see what has or hasn’t been done in the area. I’ll try to give a road map of the terminology and the main results. For now I’ll mostly give basic definitions and examples, leaving results for the next post.

1. Biased graphs

All graphs in this post are allowed parallel edges and loops. I’ll constantly talk about cycles of a graph: as is common in graph theory, by a cycle I mean a nonempty connected subgraph in which every vertex has degree two. In various contexts these are also called polygons, circuits, circles… I’ll stick to the word “cycle”. I’ll also abuse terminology and use the word “cycle” to mean the set of edges of a cycle. By a nonempty path I mean a path with at least one edge. Let’s start by defining our general universe.

Def. A biased graph is a pair $(G,\mathcal{B})$ where $\mathcal{B}$ is a set of cycles of $G$ satisfying the following property:

Theta property: for every two cycles $C_1$ and $C_2$ in $\mathcal{B}$ intersecting in a nonempty path, the third cycle in $C_1 \cup C_2$ is also in $\mathcal{B}$.

The cycles in $\mathcal{B}$ are called balanced, and the other cycles are unbalanced. Two cycles sharing a non-empty path form a theta; a theta with all cycles unbalanced is an unbalanced theta.

The theta property guarantees that the matroids defined in the next two sections are indeed matroids. In particular, this property guarantees that the third circuit axiom is satisfied.

Here are some important examples of biased graphs (the importance will become clear in the next sections):

• Biased graphs having only balanced cycles.
• Biased graphs having only unbalanced cycles.
• Signed graphs: consider a graph $G$ and a set of edges $F$ of $G$. Then we declare a cycle of $G$ to be balanced if it contains an even number of edges in $F$, and unbalanced otherwise. The resulting biased graph is called a signed graph. Balanced cycles in signed graphs are also called even or positive in the literature, while unbalanced cycles are also called odd or negative.
• Group labelled graphs: consider a graph $G$ and a (say multiplicative) group $\Gamma$. Orient every edge of $G$ and assign to every oriented edge a value from $\Gamma$. This is how we obtain group labelled graphs. Group labelled graphs are also called gain graphs or voltage graphs. From a group labelled graph we obtain a biased graph as follows. Pick any cycle $C$ of $G$ and choose an orientation for $C$. Traverse $C$ with this orientation and multiply the values on the traversed edges, where backward edges will get the inverse value (so if $(u,v)$ is an oriented edge with value $g$ and this edge appears as $(v,u)$ in the orientation of $C$, the value for this edge will be $g^{-1}$). If the total value along the cycle is $1$, then the cycle is declared to be balanced, otherwise it is unbalanced. Changing the orientation of a cycle only changes the value to its inverse, so this assignment is well defined. It is easy to see that this assignment of balanced/unbalanced cycles satisfies the theta property, so we obtain a biased graph from our group labelled graph. I’ll often abuse terminology and call this biased graph a group labelled graph. Signed graphs are special cases of group labelled graphs, obtained by labelling the edges of a graph with elements from $GF(2)$ or, equivalently, from the multiplicative group of the ternary field. I set them aside because they are relevant on their own.

Following are the two main matroids arising from biased graphs. This general setting was first introduced by Zaslavsky (see [Zas89] and [Zas91]).

2. Frame matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the frame matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

1. A balanced cycle.
2. Two unbalanced cycles sharing a vertex.
3. Two vertex-disjoint unbalanced cycles together with a minimal path joining them.
4. An unbalanced theta.

Circuits of frame matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

The circuits in 2. and 3. are called handcuffs (respectively tight and loose). 

Zaslavsky [Zas91] calls these matroids biased matroids, but recently the term “frame matroids” has become more common. Originally, a frame matroid was defined to be a matroid $M$ to which a basis $B$ could be added so that every element of $M$ is spanned by two elements in $B$. Zaslavsky showed that this definition is equivalent to the one coming from biased graphs. Consider a frame matroid $M$ represented by a biased graph $\Omega$. Form a new biased graph $\Omega’$ by adding an unbalanced loop to every vertex of $\Omega$ and call $B$ the set of these unbalanced loops. Then $B$ is a basis of the frame matroid $M’$ of $\Omega’$ and $M$ is a restriction of $M’$. Every loop of $\Omega$ is either balanced (hence spanned by the empty set), or unbalanced (so in parallel to the element of $B$ incident to the same vertex). Moreover, every edge of $\Omega$ that is not a loop is spanned by the two loops of $B$ at its endpoints.

It follows immediately from the definition that the independent sets of the frame matroid of $(G,\mathcal{B})$ are the set of edges $F$ such that every component induced by $F$ contains at most one cycle, which will have to be unbalanced.

Here are some examples of frame matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

• Graphic matroids: those are simply the frame matroids of biased graph with all cycles balanced. So frame matroids are a generalization of graphic matroids.
• Bicircular matroids: these are the frame matroids of biased graphs with all cycles unbalanced. Bicircular matroids have been widely studied (more of this in the next post, else no reader will make it to the definition of lift matroids).
• Signed-graphic matroids: these are frame matroids of signed graphs.
• Dowling geometries: first defined by Dowling ([Dow73]) these are frame matroids of group labelled graphs.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the multiplicative group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $e$ be an edge of $\Omega$ with label $g$. If $e$ is a balanced loop (i.e. a loop labelled $1$), then the column for $e$ is an all-zero column; if $e$ is an unbalanced loop incident to vertex $u$, then the column for $e$ has the $u$ entry equal to $g$ and zero everywhere else.  If $e=uv$ is not a loop and $e$ is oriented as (u,v), then the corresponding column for $e$ has a $1$ in position $u$, $-g$ in position $v$ and zero everywhere else. The proof that this is a representation of the frame matroid of $\Omega$ is not obvious, but appears, for example, in [Zas82].

The class of frame matroids (and the subclasses defined above) are minor-closed classes. The same is true for lift matroids, defined in the next section. However, this post is long enough without adding matroid operations for biased graphs. I’ll leave that for the next post as well.

3. Lift matroids

Def. Given a biased graph $\Omega=(G,\mathcal{B})$, the lift matroid represented by $\Omega$ has as elements the edges of $G$ and as circuits the edge sets of subgraphs of the following forms (see the figure below): 

1. A balanced cycle.
2. Two unbalanced cycles sharing a vertex.
3. Two vertex-disjoint unbalanced cycles.
4. An unbalanced theta.

Circuits of lift matroids are subdivisions of these graphs. Unlabelled cycles are unbalanced.

At a first glance lift matroids may look quite similar to frame matroids, but the differences between them emerge as soon as you start working with them. My rule of thumb is that frame matroids are easier to deal with than lift matroids, for some definition of “easier”. Having circuits that are not connected in the graph makes things a lot more complicated in a lot of cases.

From the definition we can easily see that the independent sets of the lift matroid of $(G,\mathcal{B})$ are the set of edges $F$ containing at most one cycle, which will have to be unbalanced.

Here are some examples of lift matroids, arising from different choices for the biased graph $\Omega=(G,\mathcal{B})$.

• Graphic matroids: those are simply the lift matroids of biased graph with all cycles balanced. So lift matroids are also a generalization of graphic matroids.
• Even cycle matroids: these are lift matroids of signed graphs. Even cycle matroids appear in alternative proofs of the list of excluded minors for graphic matroids ([Ger95]) and Seymour’s decomposition of regular matroids ([GG95]). In fact, any binary single element coextension of a graphic matroid is an even cycle matroid.
• Spikes: let $G$ be obtained from the cycle on $n$ edges by doubling every edge. Declare every pair of parallel edges to form an unbalanced cycle. The other cycles of the graph may be declared to be balanced or unbalanced, as long as the theta property is satisfied. The lift matroid of the resulting biased graph is a spike with no tip. To obtain a spike with a tip, add an unbalanced loop to the graph.

If $\mathbb{F}$ is a field and $\Omega$ is a group labelled graph on the additive group of $\mathbb{F}$, then the frame matroid of $\Omega$ is $\mathbb{F}$-representable. A matrix representation is obtained in the following way: let $A$ be the vertex-edge oriented incidence matrix of $G$, with the orientation given in the group labelled graph. Add a row to $A$, where the entry for edge $e$ is the group label of $e$. The reader is invited to check that this is a valid matrix representation for the matroid.

In the next post I’ll survey some problems and results regarding these matroids.

References