IEICE Trans - Excluded Minors for ℚ-Representability in Algebraic Extension

Excluded Minors for ℚ-Representability in Algebraic Extension

Hidefumi HIRAISHI
Sonoko MORIYAMA

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences Vol.E102-A No.9 pp.1017-1021
Publication Date: 2019/09/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E102.A.1017
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: Graph algorithms
Keyword:
matroid, representable matroid, matroid minor,

Full Text: PDF(801.7KB)>>

Summary:
While the graph minor theorem by Robertson and Seymour assures that any minor-closed class of graphs can be characterized by a finite list of excluded minors, such a succinct characterization by excluded minors is not always possible in matroids which are combinatorial abstraction from graphs. The class of matroids representable over a given infinite field is known to have an infinite number of excluded minors. In this paper, we show that, for any algebraic element x over the rational field ℚ the degree of whose minimal polynomial is 2, there exist infinitely many ℚ[x]-representable excluded minors of rank 3 for ℚ-representability. This implies that the knowledge that a given matroid is F-representable where F is a larger field than ℚ does not decrease the difficulty of excluded minors' characterization of ℚ-representability.