The search functionality is under construction.

The search functionality is under construction.

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

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.

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 -