IEICE TRANSACTIONS on Fundamentals
Excluded Minors for ℚ-Representability in Algebraic Extension
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
Latest Issue
Copyrights notice of machine-translated contents
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.
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 -
English
