×

zbMATH — the first resource for mathematics

Yes, the “missing axiom” of matroid theory is lost forever. (English) Zbl 06871590
Summary: 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}\).

MSC:
03C13 Model theory of finite structures
05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aigner, Martin, Combinatorial theory, reprint of the 1979 original, Classics in Mathematics, viii+483 pp., (1997), Springer-Verlag, Berlin · Zbl 0858.05001
[2] Courcelle, Bruno, The monadic second-order logic of graphs. I. Recognizable sets of finite graphs, Inform. and Comput., 85, 1, 12-75, (1990) · Zbl 0722.03008
[3] Ebbinghaus, Heinz-Dieter; Flum, J\"org, Finite model theory, Springer Monographs in Mathematics, xii+360 pp., (2006), Springer-Verlag, Berlin · Zbl 1081.03026
[4] Geelen, Jim, Some open problems on excluding a uniform matroid, Adv. in Appl. Math., 41, 4, 628-637, (2008) · Zbl 1172.05013
[5] Geelen, Jim; Gerards, Bert; Whittle, Geoff, Solving Rota’s conjecture, Notices Amer. Math. Soc., 61, 7, 736-743, (2014) · Zbl 1338.05039
[6] Hlin\v en\'y, Petr, On matroid properties definable in the MSO logic. Mathematical foundations of computer science 2003, Lecture Notes in Comput. Sci. 2747, 470-479, (2003), Springer, Berlin · Zbl 1124.68373
[7] Lengauer, Thomas; Wanke, Egon, Efficient analysis of graph properties on context-free graph languages (extended abstract). Automata, languages and programming, Tampere, 1988, Lecture Notes in Comput. Sci. 317, 379-393, (1988), Springer, Berlin · Zbl 0649.68076
[8] Libkin, Leonid, Elements of finite model theory, Texts in Theoretical Computer Science. An EATCS Series, xiv+315 pp., (2004), Springer-Verlag, Berlin · Zbl 1060.03002
[9] Mayhew, Dillon; Whittle, Geoff; Newman, Mike, Is the missing axiom of matroid theory lost forever?, Q. J. Math., 65, 4, 1397-1415, (2014) · Zbl 1305.05040
[10] Nerode, A., Linear automaton transformations, Proc. Amer. Math. Soc., 9, 541-544, (1958) · Zbl 0089.33403
[11] Oxley, James, Matroid theory, Oxford Graduate Texts in Mathematics 21, xiv+684 pp., (2011), Oxford University Press, Oxford · Zbl 1254.05002
[12] V\'amos, P., The missing axiom of matroid theory is lost forever, J. London Math. Soc. (2), 18, 3, 403-408, (1978) · Zbl 0395.05024
[13] Whitney, Hassler, On the abstract properties of linear dependence, Amer. J. Math., 57, 3, 509-533, (1935) · Zbl 0012.00404
[14] Zaslavsky, Thomas, Biased graphs. IV. Geometrical realizations, J. Combin. Theory Ser. B, 89, 2, 231-297, (2003) · Zbl 1031.05034
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.