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 [K74] lower 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 fractal?
Problem: Are asymptotically almost all representable matroids gammoids?
Efficient Discription
In fact it is open whether or not we have compact, efficient description of matroids representable over an infinite field:
Problem: For each representable matroid $M=(E,r)$, is there an algorithm $\mathcal{A}_M$ that computes $r(X)$ in time polynomial in $|E|$?
For example, it would be sufficient to show that each 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|$. However, the best known bound on the degree is $2^{2^{2|E|^2}}$ given by Bell, Funk, Kim, and Mayhew [BFKW20]. By Knuth’s [K74] lower bound ($2^{2^n/\text{poly}(n)}$) on the number of matroids, we cannot have a such an algorithms $\mathcal{A}_M$ for all (representable and non-representable) matroids, while Nelson’s [N18] upper bound $2^{n^3/4}$ leaves it open for representable matroids. Also 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 using the size, rank, and nonbases to construct $\mathcal{A}_M.
I thank Geoff Whittle and Jim Geelen for helpful discussion on this post and Jorn van der Pol for a correction.
References
- [BFKW20] J. Bell, D. Funk, 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.
- [K74] D. Knuth, The asymptotic number of geometries, J. Combin. Theory. Ser. A 16 (1974), 398–400.
- [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.