co.combinatorics – Is matroid realizability computable?


Contra my suspicions, the Internet is telling me that Vámos proved in “A necessary and sufficient condition for a matroid to be linear” (citation below) that it is decidable if a matroid is representable over a field. See quote on pg. 3 of Solving Rota’s Conjecture which says “The first exception is the algorithmic problem of determining when a given matroid is representable over an unspecified field, which was proved to be decidable by Vámos (28).”

Vamos, P., A necessary and sufficient condition for a matroid to be linear, Möbius Algebras, Conf. Proc. Waterloo 1971, 162-169 (1975). ZBL0374.05017.