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).<\/p>\n\n\n\n
We use $\\mathcal{M}(\\mathbb{F})$ to denote the matroids representable over a field $\\mathbb{F}$.<\/p>\n\n\n\n
For finite fields, we of course have the following result announced by Geelen, Gerards, and Whittle:<\/p>\n\n\n\n
Theorem (Geelen, Gerards, Whittle [GGW14]):<\/strong> For each finite field $\\mathbb{F}$, there are finitely many excluded minors for $\\mathcal{M}(\\mathbb{F})$.<\/em><\/p>\n\n\n\n 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.<\/p>\n\n\n\n In contrast, Mayhew, Newman, and Whittle showed that [MNW09]:<\/p>\n\n\n\n Theorem (Mayhew, Newman, Whittle [MNW09]): <\/strong>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})$.<\/em><\/p>\n\n\n\n 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<\/em>. 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<\/em> 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:<\/p>\n\n\n\n Problem:<\/strong> For each infinite field $\\mathbb{F}$, is the class $\\mathcal{M}(\\mathbb{F})$ is fractal?<\/em><\/p>\n\n\n\n One of the most significant recent results in matroid representability theory is due to Nelson:<\/p>\n\n\n\n Theorem (Nelson [N18]):<\/strong> For $n\\geq 12$, there are at most $2^{n^3\/4}$ representable matroids on ground set $[n]$.<\/em><\/p>\n\n\n\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:<\/p>\n\n\n\n Conjecture:<\/strong>\u00a0Taking $d(n)=(\\lfloor\\frac{n}{2}\\rfloor-1)(\\lceil\\frac{n}{2}\\rceil-1)$, we have the following:<\/em><\/p>\n 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”. 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<\/em>, 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.<\/p>\n\n\n\n Problem:<\/strong> Are all proper natural classes swamped?<\/em><\/p>\n\n\n\n Problem:<\/strong> Are all proper natural classes fractal? Or are Gammoids swamped but not fragile<\/em>?<\/p>\n\n\n\n Problem:<\/strong>\u00a0Are asymptotically almost all representable matroids\u00a0<\/em>gammoids?<\/i><\/p>\n\n\n\n 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:<\/p>\n\n\n\n Problem:<\/strong> 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: 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.<\/p>\n\n\n\n I thank Geoff Whittle and Jim Geelen for helpful discussion on this post.<\/p>\n\n\n\n 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 … Continue reading \n
The problem presented above is also interesting under the assumption that Nelson’s conjecture holds.<\/p>\n\n\n\nNatural Classes<\/h2>\n\n\n\n
Efficient Discription<\/h2>\n\n\n\n
<\/em><\/p>\n\n
References<\/pre>\n\n\n\n
\n