The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Alors que le théorème des graphes mineurs de Robertson et Seymour assure que toute classe de graphes fermée à un mineur peut être caractérisée par une liste finie de mineurs exclus, une caractérisation aussi succincte par des mineurs exclus n'est pas toujours possible dans les matroïdes qui sont une abstraction combinatoire des graphes. La classe des matroïdes représentables sur un champ infini donné est connue pour avoir un nombre infini de mineurs exclus. Dans cet article, nous montrons que, pour tout élément algébrique x sur le corps rationnel ℚ dont le degré du polynôme minimal est 2, il existe une infinité de ℚ[x]-représentables exclus les mineurs de rang 3 pour la ℚ-représentabilité. Cela implique que le fait de savoir qu'un matroïde donné est F-représentable où F est un champ plus grand que ℚ ne diminue pas la difficulté de la caractérisation de la ℚ-représentabilité par les mineurs exclus.
Hidefumi HIRAISHI
The University of Tokyo
Sonoko MORIYAMA
Nihon University
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
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
Copier
@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},}
Copier
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 -