Certifying non-representability of matroids over prime fields

DOI10.1016/J.JCTB.2015.11.005zbMATH Open1330.05032arXiv1101.4691OpenAlexW1683401792MaRDI QIDQ905894FDOQ905894

Authors: Jim Geelen, Geoff Whittle 

Publication date: 28 January 2016

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: It is proved that, for a prime number $p$, showing that an $n$-element matroid is not representable over $GF(p)$ requires only $O(n^2)$ rank evaluations.

Full work available at URL: https://arxiv.org/abs/1101.4691

zbMATH Keywords

matroidprime fieldrepresentable

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On Rota's conjecture and nested separations in matroids
• Title not available (Why is that?)
• The excluded minors for GF(4)-representable matroids
• Recognizing graphic matroids
• On the Uniqueness of Matroid Representations Over GF(4)
• Inequivalent representations of matroids over prime fields
• A short proof of non-GF(5)-representability of matroids
• On inequivalent representations of matroids over finite fields
• Title not available (Why is that?)
• Matroid representation over GF(3)
• On Reid's characterization of the ternary matroids
• On Forbidden Minors for GF(3)

Cited In (2)

• Representing matroids over the reals is \(\exists \mathbb{R}\)-complete
• Inequivalent representations of matroids over prime fields

This page was built for publication: Certifying non-representability of matroids over prime fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905894)