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
Additional Information
- Dillon Mayhew
- Affiliation: School of Mathematics and Statistics, Victoria University of Wellington, P.O. Box 600, Wellington 6140, New Zealand
- Email: dillon.mayhew@vuw.ac.nz
- Mike Newman
- Affiliation: Department of Mathematics and Statistics, University of Ottawa, Ottawa, Ontario K1N 6N5, Canada
- MR Author ID: 796233
- Email: mnewman@uottawa.ca
- Geoff Whittle
- Affiliation: School of Mathematics and Statistics, Victoria University of Wellington, P.O. Box 600, Wellington 6140, New Zealand
- MR Author ID: 182520
- Email: geoff.whittle@vuw.ac.nz
- Received by editor(s): January 11, 2015
- Received by editor(s) in revised form: March 1, 2017
- Published electronically: April 17, 2018
- © Copyright 2018 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 370 (2018), 5907-5929
- MSC (2010): Primary 03C13, 05B35
- DOI: https://doi.org/10.1090/tran/7408
- MathSciNet review: 3803151