Yes, the “missing axiom” of matroid theory is lost forever

Mayhew, Dillon; Newman, Mike; Whittle, Geoff

doi:10.1090/tran/7408

Yes, the “missing axiom” of matroid theory is lost forever
HTML articles powered by AMS MathViewer

by Dillon Mayhew, Mike Newman and Geoff Whittle PDF

Trans. Amer. Math. Soc. 370 (2018), 5907-5929 Request permission

Abstract:

We prove there is no sentence in the monadic second-order language $MS_{0}$ that characterises when a matroid is representable over at least one field, and no sentence that characterises when a matroid is $\mathbb {K}$-representable, for any infinite field $\mathbb {K}$. By way of contrast, because Rota’s Conjecture is true, there is a sentence that characterises $\mathbb {F}$-representable matroids, for any finite field $\mathbb {F}$.

References

Martin Aigner, Combinatorial theory, Classics in Mathematics, Springer-Verlag, Berlin, 1997. Reprint of the 1979 original. MR 1434477, DOI 10.1007/978-3-642-59101-3
Bruno Courcelle, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput. 85 (1990), no. 1, 12–75. MR 1042649, DOI 10.1016/0890-5401(90)90043-H
Heinz-Dieter Ebbinghaus and Jörg Flum, Finite model theory, Second revised and enlarged edition, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2006. MR 2177676
Jim Geelen, Some open problems on excluding a uniform matroid, Adv. in Appl. Math. 41 (2008), no. 4, 628–637. MR 2459453, DOI 10.1016/j.aam.2008.05.002
Jim Geelen, Bert Gerards, and Geoff Whittle, Solving Rota’s conjecture, Notices Amer. Math. Soc. 61 (2014), no. 7, 736–743. MR 3221124, DOI 10.1090/noti1139
Petr Hliněný, On matroid properties definable in the MSO logic, Mathematical foundations of computer science 2003, Lecture Notes in Comput. Sci., vol. 2747, Springer, Berlin, 2003, pp. 470–479. MR 2081597, DOI 10.1007/978-3-540-45138-9_{4}1
Thomas Lengauer and Egon Wanke, Efficient analysis of graph properties on context-free graph languages (extended abstract), Automata, languages and programming (Tampere, 1988) Lecture Notes in Comput. Sci., vol. 317, Springer, Berlin, 1988, pp. 379–393. MR 1023649, DOI 10.1007/3-540-19488-6_{1}29
Leonid Libkin, Elements of finite model theory, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2004. MR 2102513, DOI 10.1007/978-3-662-07003-1
Dillon Mayhew, Geoff Whittle, and Mike Newman, Is the missing axiom of matroid theory lost forever?, Q. J. Math. 65 (2014), no. 4, 1397–1415. MR 3285777, DOI 10.1093/qmath/hat031
A. Nerode, Linear automaton transformations, Proc. Amer. Math. Soc. 9 (1958), 541–544. MR 135681, DOI 10.1090/S0002-9939-1958-0135681-9
James Oxley, Matroid theory, 2nd ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011. MR 2849819, DOI 10.1093/acprof:oso/9780198566946.001.0001
P. Vámos, The missing axiom of matroid theory is lost forever, J. London Math. Soc. (2) 18 (1978), no. 3, 403–408. MR 518224, DOI 10.1112/jlms/s2-18.3.403
Hassler Whitney, On the Abstract Properties of Linear Dependence, Amer. J. Math. 57 (1935), no. 3, 509–533. MR 1507091, DOI 10.2307/2371182
Thomas Zaslavsky, Biased graphs. IV. Geometrical realizations, J. Combin. Theory Ser. B 89 (2003), no. 2, 231–297. MR 2017726, DOI 10.1016/S0095-8956(03)00035-2