On Matroid Representability and Minor Problems

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

HLINĚNÝ Petr

Year of publication 2006
Type Article in Proceedings
Conference 31st International Symposium, MFCS 2006
MU Faculty or unit

Faculty of Informatics

Citation
Web http://www.mfcs.sk/mfcs2006/
Field Informatics
Keywords crossing number; crossing minimization; planarization; crossing-critical graphs
Description In this paper we look at complexity aspects of the following problem (matroid representability) which seems to play an important role in structural matroid theory: Given a rational matrix representing the matroid $M$, the question is whether $M$ can be represented also over another specific finite field. We prove this problem is hard, and so is the related problem of minor testing in rational matroids. The results hold even if we restrict to matroids of branch-width three.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.