The missing axiom conjecture for matroid representability in MSOL

Let a finite matroid be a finite set EME^{\mathcal{M}} equipped with a rank function

rM ⁣:P(EM)Z+{0}.r^{\mathcal{M}}\colon \mathcal{P}(E^{\mathcal{M}})\to\mathbb{Z}^{+}\cup\{0\}.

Let MSOL denote monadic second-order logic for matroids, whose structures use finite ground sets, subsets, cardinalities, and rank functions. Missing axiom conjecture. There is no finite set of sentences, K\mathcal{K}, in MSOL such that (EM,rM)(E^{\mathcal{M}},r^{\mathcal{M}}) is a representable matroid if and only if it satisfies the rank axioms and every sentence in K\mathcal{K}. This formalizes the claim that representability cannot be finitely axiomatized in MSOL. The paper proves finite axiomatizability for representability over fixed finite fields conditional on Rota's conjecture, while proving non-finite-axiomatizability over any fixed infinite field within the relevant framework; the general representability conjecture remains open.

Sources & referencesView supporting material

Primary source

Dillon Mayhew, Mike Newman and Geoff Whittle, “Is the missing axiom of matroid theory lost forever?”, arXiv:1204.3365 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.