Stefan van Zwam | The Matroid Union

Oscar Vega recently informed me of the following vacancy at California State University Fresno:

The Department of Mathematics in the College of Science and Mathematics at California State University, Fresno seeks applicants for a tenure- track, academic year position starting at the level of Assistant Professor. The successful candidate will teach, supervise and advise undergraduate and graduate students according to departmental needs; conduct scholarly research in the area(s) of Combinatorial/Discrete Geometry or Algebraic Geometry resulting in peer-reviewed publications, presentations and external grant submissions; and engage in service-related activities. Primary teaching responsibilities include mathematics courses at both the undergraduate and at the graduate level, and project/thesis advising of students in the Masters of Arts in Mathematics program. Special consideration will be given to applicants with research interests overlapping current areas of research in the department.

[…]

all applicants must submit an application online at

http://www.fresnostate.edu/adminserv/hr/jobs/

no later than December 1, 2016, when we begin reviewing applications.

Interested individuals can find out more about California State University, Fresno by going to the university website at

http://www.fresnostate.edu.

The university also has a website for New/Prospective Faculty at

http://www.fresnostate.edu/adminserv/hr/jobs/valley/index.html

that provides information not only on the university but also on the greater Fresno-Clovis Metropolitan Area. Vacancy announcements for all full-time faculty positions can be located at

http://www.fresnostate.edu/adminserv/hr/jobs/.

Representable matroids are an attractive subclass of matroids, because in their study you have access to an extra tool: a matrix representing this matroid. This is a concise way to describe a matroid: $O(n^2)$ numbers as opposed to $O(2^{2^n})$ bits declaring which subsets are (in)dependent. Let $M$ be a matroid, and $A$ a representation matrix of $M$. The following operations do not change the matroid:

Add a multiple of a row of $A$ to another row of $A$;
Scale a row of $A$ by a nonzero constant;
Scale a column of $A$ by a nonzero constant;
Add or remove all-zero rows;
Apply a field automorphism to each entry of $A$.

If a matrix $A_1$ can be turned into a matrix $A_2$ through such operations, then we say $A_1$ and $A_2$ are equivalent. If we don’t use any field automorphisms, then we say they are projectively equivalent. Generally, a matroid can have multiple inequivalent representations over a field. The exceptions are the finite fields $\textrm{GF}(2)$ and $\textrm{GF}(3)$ (shown in [BL]).

When we try to prove some theorem about a matroid or class of matroids, inequivalent representations can be a major complicating factor. For instance, the excluded-minor characterization of ternary matroids can be proven in under five pages [Oxley, pp. 380-385], whereas the excluded-minor characterization of quaternary matroids takes over fifty [GGK]. It is not surprising, then, that significant efforts have been made to get a handle on inequivalent representations. In this post I will focus on one such effort, namely a very attractive theorem by Geoff Whittle, who recently celebrated his 65th birthday with a wonderful workshop. First, a definition.

Definition. Let $\mathbb{F}$ be a field, and $\mathcal{M}$ a minor-closed class of $\mathbb{F}$-representable matroids. Let $N \in \mathcal{M}$. We say $N$ is a stabilizer for $\mathcal{M}$ if, for every 3-connected matroid $M \in \mathcal{M}$ that has $N$ as a minor, each representation of $N$ (over $\mathbb{F}$) extends to at most one representation of $M$ (up to the equivalence defined above).

In other words, once we select a representation for $N$, we have uniquely determined a representation of $M$. A small example: let $\mathbb{F} = \textrm{GF}(5)$, let $\mathcal{M}$ be the set of all minors of the non-Fano matroid $F_7^-$, and let $N$ be the rank-3 wheel. Now $N$ has the following representation:

$$
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 1 & 1 & 0\\
0 & 0 & 1 & 0 & 1 & a
\end{bmatrix}
$$

where $a \in \{1, 2, 3\}$. The only 3-connected matroids in $\mathcal{M}$ that have $N$ as a minor are $N$ itself and $F_7^-$. We need to check that each representation of $N$ extends to at most one representation of $F_7^-$. Up to equivalence, the latter representation must look like

$$
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 1 & 1\\
0 & 1 & 0 & 1 & 1 & 0 & b\\
0 & 0 & 1 & 0 & 1 & a & c
\end{bmatrix}
$$

and it is readily checked that we must have $b = c = a = 1$. Hence two of the representations of $N$ do not extend to a representation of $M$, whereas one extends uniquely to a representation of $M$. So $N$ is a stabilizer for $\mathcal{M}$.

If $\mathcal{M}$ is an infinite class, we cannot do an exhaustive check as in the example to verify a stabilizer. But Geoff Whittle managed to prove that a finite check still suffices:

Whittle’s Stabilizer Theorem [Whi]. Let $\mathcal{M}$ be a minor-closed class of $\mathbb{F}$-representable matroids, and $N \in \mathcal{M}$ a 3-connected matroid. Exactly one of the following holds:

$N$ is a stabilizer for $\mathcal{M}$ over $\mathbb{F}$;
There is a 3-connected matroid $M \in \mathcal{M}$ such that either:
- $N = M\backslash e$ and some representation of $N$ extends to more than one representation of $M$;
- $N = M / e$ and some representation of $N$ extends to more than one representation of $M$;
- $N = M / e \backslash f$, $M / e$ and $M \backslash f$ are 3-connected, and some representation of $N$ extends to more than one representation of $M$.

I will conclude this post with two applications. I will leave the finite case checks to the reader.

Lemma. The matroid $U_{2,4}$ is a stabilizer for the class of quaternary matroids.

Corollary [Kah]. A 3-connected, quaternary, non-binary matroid has a unique representation over $\textrm{GF}(4)$.

Proof. A non-binary matroid $M$ has a $U_{2,4}$-minor. The matroid $U_{2,4}$ has the following representation:

$$
\begin{bmatrix}
1 & 0 & 1 & 1\\
0 & 1 & 1 & a
\end{bmatrix}
$$
where $a \not\in \{0,1\}$. This leaves two choices for $a$, that are related through a field automorphism. Hence $U_{2,4}$ has (up to equivalence) a unique representation over $\textrm{GF}(4)$. But $U_{2,4}$ is a stabilizer, so $M$ is uniquely representable over $\textrm{GF}(4)$ as well. $\square$

Lemma. The matroids $U_{2,5}$ and $U_{3,5}$ are stabilizers for the class of quinary matroids.

Lemma. The matroid $U_{2,4}$ is a stabilizer for the class of quinary matroids with no minor isomorphic to $U_{2,5}$ and $U_{3,5}$.

Corollary [OVW]. A 3-connected, quinary matroid has at most six inequivalent representations over $\textrm{GF}(5)$.

Proof. $U_{2,5}$ and $U_{3,5}$ have six inequivalent representations and are stabilizers. If $M$ does not have such a minor, then either $M$ is regular (and thus uniquely representable over any field) or $M$ has a $U_{2,4}$-minor, which is has three inequivalent representations. $\square$

References

[BL] Tom Brylawski and Dean Lucas, Uniquely representable combinatorial geometries. In Teorie Combinatorie (proc. 1973 internat. colloq.) pp. 83-104 (1976).
[GGK] Jim Geelen, Bert Gerards, Ajai Kapoor, The excluded minors for $\textrm{GF}(4)$-representable matroids. J. Combin. Th. Ser. B, Vol. 79, pp. 247-299 (2000).
[Kah] Jeff Kahn, On the uniqueness of matroid representations over $\textrm{GF}(4)$. Bull. London Math. Soc. Vol. 20, pp. 5–10 (1988).
[OVW] James Oxley, Dirk Vertigan, Geoff Whittle, On inequivalent representations of matroids over finite fields.J. Combin. Theory Ser. B. Vol. 67, pp. 325–343 (1996).
[Oxley] James Oxley, Matroid Theory, 2nd edition. Oxford University Press (2011).
[Whi] Geoff Whittle, Stabilizers of classes of representable matroids. J. Combin. Theory Ser. B, Vol. 77, pp. 39–72 (1999).