Guest post by Jim Geelen.

$\newcommand{\del}{\,\backslash\,}$ $\newcommand{\con}{/}$ $\newcommand{\cC}{\mathcal{C}}$ $\newcommand{\bF}{\mathbb{F}}$

Anyone who has given significant consideration to the classes of frame matroids and lifted graphic matroids will have been struck by their similarities. The point of this posting is that these classes can be unified in a way that might have significant algorithmic implications. We also prove an amazing result (Theorem 3) concerning representations of matroids in the unified class.

Graphic matroids

The class of graphic matroids is very well understood; for example, the set of excluded minors is known and there is a polynomial-time algorithm for recognizing whether a matroid, given by its rank oracle, is graphic.

There are two key parts to the recognition algorithm. First one needs an algorithm for testing whether a given binary matroid is graphic; see, for example, [BC80]. Second one needs to check, for a given matroid $M$ and graph $G$, whether $M=M(G)$. This second part is solved by the following beautiful result due to Seymour [Sey81].

Theorem 1: Let $M$ be a matroid and let $G$ be a loopless $2$-connected graph with $E(G)=E(M)$. Then $M=M(G)$ if and only if $r(M)\le |V(G)|-1$ and, for each vertex $v$ of $G$, the set of edges incident with $v$ in $G$ forms a cocircuit of $M$.

Bias graphs

In the following three short sections, I will review the frame matroid and the lift matroid associated with a bias graph. These objects were introduced by Zaslavsky [Zas91] and were discussed in Irene Pivotto’s post on August 26.

Let $\cC$ be a set of circuits in a graph $G$. A theta in $G$ is loopless $2$-connected subgraph $H$ with $|E(H)| = |V(H)|+1$. Thus, a theta has two special vertices connected by three internally-disjoint paths, and such graphs have exactly three circuits. We say that $\mathcal C$ has the theta-property if there is no theta in $G$ having exactly two of its three circuits in $\cC$. The pair $(G,\cC)$ is called a bias graph if $\cC$ has the theta-property.

Frame matroids

The frame matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $FM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and for each component of $G[I]$ has at most one circuit.

Zaslavsky showed that a matroid $M$ is a frame matroid if and only if there is a matroid $M’$ and a basis $B$ of $M’$ such that $M$ is a restriction of $M’$ and for each element $e\in E(M’)-B$, the unique circuit of $B\cup\{e\}$ contains at most two elements of $B$.

Lifts of graphic matroids

The lift matroid associated with any bias graph $(G,\cC)$ is a unique matroid, denoted $LM(G,\cC)$, with ground set $E(G)$ such that a set $I\subseteq E(G)$ is independent if an only if no circuit of $G[I]$ is contained in $\cC$ and $G[I]$ contains at most one circuit. Any matroid that is the lift matroid of a bias graph is called a lifted graphic matroid.

Zaslavsky showed that a matroid $M$ is a lifted graphic matroid if and only if there is a matroid $M’$ an element $e\in E(M’)$ such that $M’\del e = M$ and
$M’\con e$ is graphic.

Combining the classes

Let us call a graph $G$ a framework for a matroid $M$ if

• $E(M) = E(G)$,
• $G$ is connected,
• $r(M)\le |V(G)|$, and
• for each vertex $v$ of $G$, the set of edges incident with $v$ is a cocircuit of $M$.

We will call $M$ a framework matroid if it admits a framework representation.

The definition of a framework is motivated by Theorem 1; it has the appealing property that it is constructive. Given a matroid $M$, via a rank oracle, and a graph $G$ one can readily check (in polynomial time) whether or not $G$ is a framework for $M$. This constructive property is in contrast with the following conjectures.

Conjecture 1: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=FM(G,\cC)$.

Conjecture 2: There is no polynomial-time algorithm that, given a matroid $M$ via its rank oracle and a graph $G$, determines whether there is a bias graph $(G,\cC)$ such that $M=LM(G,\cC)$.

I further believe that the recognition problem is intractable for both the class of frame matroids and the class of lifted graphic matroids. In contrast, I think that one can recognize framework matroids.

Conjecture 3: There is a polynomial-time algorithm that, given a matroid $M$ via its rank oracle, determines whether $M$ is a framework matroid.

Technical details

Let us call a graph $G$ a weak framework for a matroid $M$ if

• $E(M) = E(G)$,
• $r(M)\le |V(G)|$,
• for each vertex $v$ of $G$, the set of edges incident with $v$ is the union of a collection of cocircuits of $M$ and a set of loops of $M$, and
• each loop of $M$ is a loop of $G$.

This weakened notion behaves nicely with respect to our three classes.

• If $G$ is a graph, the $G$ is a weak framework for $M(G)$.
• If $M$ is the frame matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.
• If $M$ is the lift matroid for the bias graph $(G,\cC)$, then $G$ is a weak framework for $M(G)$.

Lemma 1: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $H$ is a subgraph of $G$, then $H$ is a weak framework of $M| E(H)$.

Proof. Note that for any edge $e$ of $G$, $G-e$ is a weak framework of $M-e$. Now consider a vertex $v$ of $G$ and let $X$ denote the set of edges incident with $v$. If there is a nonloop edge $e$ of $G$ that is incident with $v$, then there is a cocircuit $C^*$ of $M$ such that $e\in C^*\subseteq X$. Then $r(E(G-v)) \le r(E(G)) – 1 \le |V(G)|-1 = |V(G-v)|$. Hence $G-v$ is a weak framework of $M\del X$. Now the result follows by deleting the vertices $V(G)-V(H)$, in an appropriately chosen order, and then deleting the edges in $E(G[V(H)]) – E(H)$. $\Box$

Lemma 2: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, then $r(M)\ge |V(G)|-1$ and equality holds if and only if $M$ is the cycle matroid of $G$.

Proof. Order the vertices of $G$ in the order $(v_1,v_2,\ldots,v_n)$ such that, for each $i\ge 2$, the vertex $v_i$ has a neighbour among $\{v_1,\ldots,v_{i-1}\}$. The sets $E(G[\{v_1,v_2,\ldots,v_n\}]),\, E(G[\{v_1,v_2,\ldots,v_n\}]),\,\ldots, \,E(G[\{v_1\}])$ have strictly decreasing rank in $M$, so $r(M)\ge |V(G)|-1$.

Equality clearly holds when $M=M(G)$. Conversely suppose that equality holds. A routine variation on the proof of Lemma 1 proves that, for each subgraph $H$ of $G$, we have $r(E(H)) \le |V(H)|-1$. Then, by the first part of the proof, for each connected subgraph $H$ of $G$ we have $r(E(H)) = |V(H)|-1$. In particular, if $H$ is a circuit of $G$, then $E(H)$ is a circuit of $M$, and, if $H$ is a tree of $G$, then $E(H)$ is independent in $M$. Thus $M = M(G)$. $\Box$

The following result is an easy application of Lemmas 1 and 2.

Lemma 3: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected and $M$ is $3$-connected, then $G$ is $2$-connected.

Lemma 4: Let $G$ be a weak framework for a matroid $M$. If $G$ is connected, $M$ is $3$-connected, and $|E(M)|\ge 4$, then $M$ is a framework matroid.

Proof. We may assume that among all connected weak frameworks for $M$ we have chosen $G$ with as many loops as possible. Since $M$ has no loops, if $G$ is not itself a framework of $M$, then there is a vertex $v$ of $G$ such that the set $X$ of edges incident with $v$ is the union of at least two distinct cocircuits of $G$. By Lemma 1 and the fact that $M$ is simple, there is at most one loop at $v$. Choose a cocircuit $C^*\subseteq X$ so that $X-C^*$ contains no loop of $G$. Now define $G’$ by replacing each edge $e=vw$ of $X-C^*$ with a loop at $w$. Note that $G’$ is a weak framework of $M$ and, since $G$ is $2$-connected, $G’$ is connected. However, this contradicts our choice of $G$ and that completes the proof.$\Box$

This proves that:

Theorem 2: The class of framework matroids contains all $3$-connected frame matroids and all $3$-connected lifted graphic matroids.

Represented matroids

A matrix with at most two nonzero nonzero entries in each column is called a frame matrix. Let $A_1$ and $A_2$ be matrices over a field $\bF$ with a common set $E$ of column indices. We say that $A_1$ and $A_2$ are row equivalent if $A_1$ can be obtained from $A_2$ by elementary row operations.

Problem 1: Given as input a matrix $A$, decide whether $A$ is row equivalent to a frame matrix.

Note that, if a matrix $A$ is row-equivalent to a frame matrix, then $M(A)$ is a frame matroid.

Conjecture 4: There is a polynomial-time algorithm that solves Problem 1.

We say that $A_1$ and $A_2$ are projectively equivalent if $A_1$ is row equivalent to a matrix $A_3$ that can be obtained from $A_2$ by column scaling. A signed incidence matrix is a frame matrix with entries in $\{0,\pm 1\}$ such that each column sums to zero. A lift of a matrix is a matrix obtained by appending a new row. A lifted signed-incidence matrix is a lift of a signed-incidence matrix.

Problem 2: Given as input a matrix $A$, decide whether $A$ is projectively equivalent to a lifted signed-incidence matrix.

Note that, if a matrix $A$ is projectively equivalent to a lifted signed-incidence matrix, then $M(A)$ is a lift of a graphic matroid.

Conjecture 5: There is a polynomial-time algorithm that solves Problem 2.

The amazing theorem

Let $A\in \bF^{V\times E}$ be a frame matrix with no all-zero column. The support of $A$ is the graph $G=(V,E)$ such that a vertex $v\in V$ is incident with an edge $e\in E$ if and only if the $(v,e)$-entry of $A$ is nonzero. If $A$ is a signed-incidence matrix with support $G$, then we say that $A$ is a signed incidence matrix of $G$.

The following remarkable fact came out of discussions with Bert Gerards and Geoff Whittle.

Theorem 3: Let $A$ be a matrix and let $M=M(A)$ be a framework matroid with framework $G$. Then either

• $A$ is projectively equivalent to a lift of the signed-incidence matrix of $G$, or
• $A$ is row equivalent to a frame matrix whose support is $G$.

Proof. By Lemma 2, we may assume that $r(M) = |V(G)|$. For each cocircuit $C$ of $M$ there is a vector $v$ in the row space of $A$ whose support is $C$. Therefore there is a frame matrix $A’$ whose support is $G$ and whose row space is contained in the row space of $A$. Now $G$ is a weak framework for $M(A’)$, so the rank of $A’$ is either $|V(G)|$ or $|V(G)|-1$. If $A’$ has rank $|V(G)|$, then $A$ is row equivalent to the frame matrix $A’$, as required. Thus we may assume that $A’$ has rank $|V(G)|-1$. Then, by Lemma 2, $M(A’)= M(G)$ and hence $A’$ is projectively equivalent to the signed incidence matrix of $G$. Finally, since the row space of $A’$ is contained in the row space of $A$ and $rank(A) = rank(A’)+1$, $A$ is row equivalent to a lift of $A’$. $\Box$

Theorem 3 some interesting consequences; the first of these is a striking converse to Theorem 2.

Corollary 1: For any field $\bF$, if $M$ is an $\bF$-representable framework matroid, then $M$ is either a frame matroid or a lifted graphic matroid.

Corollary 2: If $M$ is a $3$-connected matroid that has a representation by a frame matrix, then every representation of $M$ is either row equivalent to a frame matrix or is projectively equivalent to a lifted signed incidence matrix.

Corollary 3: If $M$ is a $3$-connected matroid that has a representation by a lifted signed incidence matrix, then every representation of $M$ is either projectively equivalent to a lifted signed incidence matrix or is row equivalent to a frame matrix.

Consider, for example, the matroid $R_{10}$. It is represented over GF$(3)$ by the “unsigned” incidence matrix of $K_5$. However, over GF$(2)$ it is represented by a lift of a signed incidence matrix of $K_5$.

References

[BC80] R.E. Bixby, W.H. Cunningham, Converting linear programs to network problems, Math. Oper. Res. 5 (1980), 321-357.
[Sey81] P.D. Seymour, Recognizing graphic matroids, Combinatorica 1 (1981), 75-78.
[Zas91] T. Zaslavsky, Biased graphs. II. The three matroids, J. Combin. Theory, Ser. B 51 (1991), 46-72.

$\newcommand{\cM}{\mathcal{M}}$

This entry continues on from my last, which concerns the growth rates of matroids in minor-closed classes. A one-line recap of my notation is that, if $\cM$ is a minor-closed class of matroids, then $h_{\cM}(n)$ denotes the ($\mathbb{Z} \cup \{\infty\}$)-valued function whose value at each integer $n$ is the maximum number of elements in a simple matroid in the class of rank at most $n$. Last time I finished with the growth rate theorem of Geelen, Kabell, Kung and Whittle – here it is again.

Growth Rate Theorem
Let $\cM$ be a minor-closed class of matroids. Either

1.  $h_{\cM}(n) \le c_{\cM}n$ for all $n$,
2. $\binom{n+1}{2} \le h_{\cM}(n) \le c_{\cM}n^2$ for all $n$, and $\cM$ contains all graphic matroids,
3. $\frac{q^n-1}{q-1} \le h_{\cM}(n) \le c_{\cM}q^n$ for all $n \ge 2$ and some prime power $q$, and $\cM$ contains all GF$(q)$-representable matroids, or
4. $h_{\cM}(n) = \infty$ for all $n \ge 2$, and $\cM$ contains all simple rank-$2$ matroids.

This is surprising – up to a constant factor, the growth rate function for an arbitrary minor-closed class has just four possible types and, if the class has superlinear growth rate function then the function is `explained’ by the class containing a natural class with which its growth rate function agrees asymptotically. In this entry and the next, we’ll discuss some questions related to this theorem, starting with the scariest.

Structure

Thinking as we did with Mader’s theorem (Theorem 1 in my last entry), the burning question is why growth rate functions are restricted in this way. In the case of graphs, growth rate functions are controlled because of the structure guaranteed by the graph minors structure theorem. For this purpose, we can only really hope to describe classes satisfying outcomes 1-3 of the theorem, so we exclude some rank-$2$ uniform matroid to gain traction, and pose the following question:

Problem 1: Given an integer $n$, find a structural description for minor-closed classes of matroids not containing $U_{2,n}$.

An solution to this problem would yield a theorem that implies the growth rate theorem (and much more) very easily.

This problem is probably extremely difficult in general, but the case where the matroids are representable over a fixed finite field GF($q$) has been solved. As a major part of their work on the recently vanquished Rota’s Conjecture, Geelen, Gerards and Whittle have proved (but unfortunately not quite written yet – see [GGW07]) a structure theorem for the matroids in arbitrary minor-closed class of GF$(q)$-representable matroids. The representable case of the growth rate theorem falls out of their theorem without much effort.

However, the non-representable case has genuine difficulties not arising from representable matroids that make a structure theorem much harder to dream up. Spikes, for example, cause a special type of trouble that doesn’t crop up over finite fields (see [G08] for a discussion). Problem 1 in its full generality is still very much open.

Zooming In

Something that seems more approachable is to ask more exact questions about how growth rate functions behave. It is one thing to know that $h_{\cM}(n)$ is bounded above and below by, say, a quadratic in $n$, but it is another thing to know the asymptotic or exact behaviour of the function itself. In some cases, this is trivial; there are no prizes for working out the answer if $\cM$ is the class of graphic matroids, for example. In some cases, it seems very hard – even the class of graphic matroids with no $M(K_t)$-minor for general $t$ has a growth rate function that is only partially understood (it is a linear function whose gradient is known asymptotically in $t$, but not known for any fixed $t > 9$ (edit: corrected – thanks Jim), see Thomason [T01]).

However, for many specific classes, the problem is interesting and some results are known. Kung, Mayhew, Pivotto and Royle [KMPR13] recently showed that the growth rate function for the binary matroids with no AG$(3,2)$-minor is the same as that of the graphic matroids for all $n \ge 5$. Geelen and I [GN10] showed that, for sufficiently large $n$, the growth rate function for the class of matroids with no $U_{2,\ell+2}$-minor is equal to that of the GF$(q)$-representable matroids, where $q$ is the largest prime power not exceeding $\ell$. We also have shown, (and will write someday) that every minor-closed class $\cM$ whose growth rate function is exponential in $n$ satisfies $h_{\cM}(n) = \frac{q^{n+k}-1}{q-1} – qd$ for all sufficiently large $n$, where $k$ and $d$ are nonnegative integers with $d \le \frac{q^{2k}-1}{q^2-1}$.

Many questions of this sort are still open. Here is one in quite a general form:

Problem 2: Let $\mathfrak{F}$ be a set of fields containing at least one finite field, and $\cM$ be the class of matroids representable over all fields in $\mathfrak{F}$. Determine $h_{\cM}(n)$.

This determination could be asymptotic, exact, or exact for all large $n$. Some cases are easy; if $\mathfrak{F}$ contains GF$(2)$ then it is either the class of binary matroids or regular matroids. If $\mathfrak{F}$ contains GF$(3)$ then the answer will follow from Whittle’s characterisation of ternary matroids [W97]. If all fields in $\mathfrak{F}$ share a common subfield that is not itself in $\mathfrak{F}$, then $\cM$ has exponential growth rate function and the (eventually exact) answer probably follows from our theorem above. If $\mathfrak{F} = \{\mathrm{GF}(4), \mathrm{GF}(5)\}$ then $\cM$ is the class of golden-mean matroids and there is a conjectured answer of Archer [A05] confirmed in some cases by Welsh [W11]. The case where $\mathfrak{F}$ contains $\mathbb{C}$ and one other field GF$(q)$ is very interesting and the extremal examples are probably all Dowling geometries over GF$(q)$. Here is a concrete conjecture to that effect:

Conjecture 1: Let $q$ be a prime power. The class $\cM$ of matroids representable over $\mathbb{C}$ and GF$(q)$ has growth rate function $h_{\cM}(n) = n + (q-1)\binom{n}{2}$ for all sufficiently large $n$.

One could modify this conjecture to the case where $\cM$ is the class of $\mathbb{C}$-representable matroids with no $U_{2,t}$-minor for some integer $t \ge 4$. In this case, the extremal examples are still probably the Dowling geometries, but again not much is known.

Next time, we’ll talk about generalisations of $h_{\cM}(n)$ applying to classes that do contain all simple rank-$2$ matroids. See you then.

References

[A05] S. Archer. Near varieties and extremal matroids, PhD thesis, Victoria University of Wellington, 2005.

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

[GGW07] J. Geelen, B. Gerards, G. Whittle. Towards a matroid-minor structure theory. In Combinatorics, complexity and chance, vol. 34 of Oxford Lecture Ser. Math. Applic. 72-92. Oxford Univ. Press, Oxford, 2007.

[GN10] J. Geelen, P. Nelson. The number of points in a matroid with no $n$-point line as a minor. J. Combin. Theory Ser. B, 100(6):625-630, 2010

[KMPR13] J. Kung, D. Mayhew, I. Pivotto, G. Royle. Maximum size binary matroids with no AG(3,2)-minor are graphic. arXiv:1304.2448 [math.CO]

[T01] A. Thomason. The extremal function for complete minors. J. Combin. Theory Ser.B 81:318-338, 2001

[W11] M. Welsh. Golden mean and secret sharing matroids. Master’s thesis, Victoria University of Wellington, 2011.

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

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.