Excluded Minors for ℚ-Representability in Algebraic Extension

Hidefumi HIRAISHI; Sonoko MORIYAMA

doi:10.1587/transfun.E102.A.1017

Excluded Minors for ℚ-Representability in Algebraic Extension

Hidefumi HIRAISHI, Sonoko MORIYAMA

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E102-A No.9 pp.1017-1021

Publication Date: 2019/09/01

Publicized

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

Authors

Hidefumi HIRAISHI
The University of Tokyo
Sonoko MORIYAMA
Nihon University

Keyword

matroid, representable matroid, matroid minor

Cite this

Copy

Hidefumi HIRAISHI, Sonoko MORIYAMA, "Excluded Minors for ℚ-Representability in Algebraic Extension" in IEICE TRANSACTIONS on Fundamentals, vol. E102-A, no. 9, pp. 1017-1021, September 2019, doi: 10.1587/transfun.E102.A.1017.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E102.A.1017/_p

Copy

@ARTICLE{e102-a_9_1017,
author={Hidefumi HIRAISHI, Sonoko MORIYAMA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Excluded Minors for ℚ-Representability in Algebraic Extension},
year={2019},
volume={E102-A},
number={9},
pages={1017-1021},
abstract={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.},
keywords={},
doi={10.1587/transfun.E102.A.1017},
ISSN={1745-1337},
month={September},}

Copy

TY - JOUR
TI - Excluded Minors for ℚ-Representability in Algebraic Extension
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1017
EP - 1021
AU - Hidefumi HIRAISHI
AU - Sonoko MORIYAMA
PY - 2019
DO - 10.1587/transfun.E102.A.1017
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E102-A
IS - 9
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - September 2019
AB - 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.
ER -