While a there have been remarkable techniques and discoveries for representability over finite fields (see [GGW14; W05] for a selection), not much has been said about representability over infinite fields — except perhaps how badly our existing techniques fail. This blogpost will cover some of these failures and some hopeful conjectures (or future pathologies).

We use $\mathcal{M}(\mathbb{F})$ to denote the matroids representable over a field $\mathbb{F}$.

Excluded minors

For finite fields, we of course have the following result announced by Geelen, Gerards, and Whittle:

Theorem (Geelen, Gerards, Whittle [GGW14]): For each finite field $\mathbb{F}$, there are finitely many excluded minors for $\mathcal{M}(\mathbb{F})$.

This has many useful consequences. For each finite field $\mathbb{F}$, there is a constant time certificate when a matroid is not $\mathbb{F}$-representable and there is a finite second-order logical sentence for $\mathbb{F}$-representability using a predicate for independence.

In contrast, Mayhew, Newman, and Whittle showed that [MNW09]:

Theorem (Mayhew, Newman, Whittle [MNW09]): For each infinite field $\mathbb{F}$, each element of $\mathcal{M}(\mathbb{F})$ is a minor of an excluded minor for $\mathcal{M}(\mathbb{F})$.

In essence, the set of excluded minors for $\mathcal{M}(\mathbb{F})$ is as wild as $\mathcal{M}(\mathbb{F})$ itself. When the set of excluded minors for a class $\mathcal{C}$ contain $\mathcal{C}$ in its downwards-closure like this, we say that $\mathcal{C}$ is swamped. Another way in which the set of excluded minors for a class can be seen as “worse” then the class itself is when they dominate in quantity on a given number of elements. Taking $e_n$ to be the number of non-isomorphic excluded minors for $\mathcal{C}$ on at most $n$ elements and $c_n$ to be the number of non-isomorphic members of $\mathcal{C}$ on at most $n$ elements, we say that $\mathcal{C}$ is fractal when $\lim_{n\to\infty}\frac{e_n}{c_n}=\infty$. Mayhew, Newman, and Whittle show that for any integer $k\geq 3$, the class $\mathcal{C}$ of sparse paving matroids with at most $k$ circuit-hyperplanes is fractal [MNW2]. However, they leave the following open:

Problem: For each infinite field $\mathbb{F}$, is the class $\mathcal{M}(\mathbb{F})$ is fractal?

One of the most significant recent results in matroid representability theory is due to Nelson:

Theorem (Nelson [N18]): For $n\geq 12$, there are at most $2^{n^3/4}$ representable matroids on ground set $[n]$.

Combining this with Knuth’s upper bound ($2^{2^n/\text{poly}(n)}$) on the number of matroids on $[n]$, it gives us that asymptotically almost all matroids are non-representable. Along with this result, Nelson also gave one of the most significant conjectures in matroid representation theory:

Conjecture: Taking $d(n)=(\lfloor\frac{n}{2}\rfloor-1)(\lceil\frac{n}{2}\rceil-1)$, we have the following:

• Asymptotically almost all representable matroids on $[n]$ have rank in $\{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil\}$ and has exactly $d(n)-1$ nonbases.
• Asymptotically almost all matroids on $[n]$ with rank in $\{\lfloor\frac{n}{2}\rfloor,\lceil\frac{n}{2}\rceil\}$ and exactly $d(n)-1$ nonbases are representable.

The value $d(n)-1$, is the maximum number of non-bases that can exist without enforcing a non-trivial algebraic relation and by only having points placed “generically”.
The problem presented above is also interesting under the assumption that Nelson’s conjecture holds.

Natural Classes

Representability over any field is closed under minors and direct sums. However, a significant difference between finite and infinite fields is that with infinite fields we can place points in “general position”; matroid representability over an infinite field is closed under principal extension (i.e. freely placing an element into a flat). In general, we we say a class is natural, when it contains $U_{1,1}$ and is closed under the following: isomorphism, minors, direct sums, and principal extensions. It is the freedom of principal extension that seems to make natural classes wild. Besides, $\mathcal{M}(\mathbb{F})$ for $\mathbb{F}$ infinite, other natural classes include algebraic matroids over a given field, orientable matroids, and arbitrary intersections of natural classes. Also of particular note, is the class of Gammoids (matroids given by a linkage function in a directed graph), the smallest natural class. It is known that all of the above classes are swamped.

Problem: Are all proper natural classes swamped?

Problem: Are all proper natural classes fractal? Or are Gammoids swamped but not fragile?

Problem: Are asymptotically almost all representable matroids gammoids?

Efficient Discription

In fact it is open whether or not we have compact, efficient discription of matroids representable over a fixed infinite field. Considering the case of complex representable matroids:

Problem: Is there an algorithm $\mathcal{A}$ and polynomials $s$ and $t$, so that given a complex representable matroid $M=(E,r)$ there is a binary string description $\mathbf{D}_M$ (encoding $M$ in whatever which way), so that:

• $\mathbf{D}_M$ has length at most $s(|E|)$, and
• for any $X\subseteq E$, when $\mathcal{A}$ is given $(\mathcal{D}_M,X)$, it computes $r(X)$ in time at most $t(|E|)$.

For example, it would be sufficient to show that each complex representable matroid $M=(E,r)$ is representable by a matrix whose entries are algebraic with minimal polynomials whose degrees and coefficients are bounded by a polynomial in $|E|$. The best known bound on the degree is $2^{2^{2|E|^2}}$ given by Bell, Funk, Kim, and Mayhew [BFKW20]. Note that if $\mathbf{D}_M$ is a naive encoding of $r:2^E\to \mathbb{Z}$ (say as its list of outputs), then the running time $t$ is indeed polynomial, but the size $s$ is exponential. Alternatively, we can make the size $s$ polynomial with an enumeration of the complex representable matroids (but then $\mathcal{A}$ would certainly not run in polynomial time as it would have to reconstruct all prior matroids, and check each of these exponentially many rank evaluations). However, note that with a positive resolution to Nelson’s conjecture, we would be able to resolve this problem for almost all representable matroids by simply providing the size, rank, and nonbases.

I thank Geoff Whittle and Jim Geelen for helpful discussion on this post.

References

• [BFKW20] B. Jason, F. Daryl, B. D. Kim, D. Mayhew, Effective Versions of Two Theorems of RADO, Quarterly J. Math. 71 (2020), 599–618.
• [GGW14] J. Geelen, B. Gerards, G. Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc. 61 (2014), 736–743.
• [MNW09] D. Mayhew, M. Newman, G. Whittle, On excluded minors for real representability, J. Combin. Theory Ser. B 99 (2009), 685–689.
• [MNW21] D. Mayhew, M. Newman, G. Whittle, Fractal classes of matroids, Adv. in Appl. Math. 126 (2021), 101995.
• [N18] P. Nelson, Almost all matroids are nonrepresentable, Bull. London Math. Soc. 50 (2018), 245-248.
• [W05] G. Whittle, Recent work in matroid representation theory, Discrete Math. 302 (2005), 285–296.