Weak orientability of matroids and polynomial equations

DOI10.1016/J.EJC.2015.03.018MaRDI QIDQ491739zbMATH OpenOpenAlexFDO

Authors Jon Lee, Jesús A. De Loera, Susan Margulies, Jacob Miller

Publication date 19 August 2015

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Bland-Jensen equationsBland-Jensen systemnon-weakly-orientable matroids

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: This paper studies systems of polynomial equations that provide information about orientability of matroids. First, we study systems of linear equations over GF(2), originally alluded to by Bland and Jensen in their seminal paper on weak orientability. The Bland-Jensen linear equations for a matroid M have a solution if and only if M is weakly orientable. We use the Bland-Jensen system to determine weak orientability for all matroids on at most nine elements and all matroids between ten and twelve elements having rank three. Our experiments indicate that for small rank, about half the time, when a simple matroid is not orientable, it is already non-weakly orientable. Thus, about half of the small simple non-orientable matroids of rank three are not representable over fields having order congruent to three modulo four. For binary matroids, the Bland-Jensen linear systems provide a practical way to check orientability. Second, we present two extensions of the Bland-Jensen equations to slightly larger systems of non-linear polynomial equations. Our systems of polynomial equations have a solution if and only if the associated matroid M is orientable. The systems come in two versions, one directly extending the Bland-Jensen system for GF(2), and a different system working over other fields. We study some basic algebraic properties of these systems. Finally, we present an infinite family of non-weakly-orientable matroids, with growing rank and co-rank. We conjecture that these matroids are minor-minimal non-weakly-orientable matroids.

Recommendations

• Invariant theory-like theorems for matroids and oriented matroids
• Reconstruction of the orientation class of an oriented matroid
• Some minimal non-orientable matroids of rank three
• On minimal non-orientable matroids with 2n elements and rank n
• scientific article; zbMATH DE number 46368

Cites work

• A characterization of the orientations of ternary matroids
• Algebraic varieties characterizing matroids and oriented matroids
• Algorithmic versus axiomatic definitions of matroids
• Computational synthetic geometry
• Computing infeasibility certificates for combinatorial problems through Hilbert's Nullstellensatz
• Decomposition of regular matroids
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 704831 (Why is no real title available?)
• scientific article; zbMATH DE number 1182899 (Why is no real title available?)
• scientific article; zbMATH DE number 5873618 (Why is no real title available?)
• scientific article; zbMATH DE number 3227800 (Why is no real title available?)
• Matroid Complexity and Nonsuccinct Descriptions
• Matroid enumeration for incidence geometry
• Matroids with nine elements
• Nonrealizability proofs in computational geometry
• Orientability of matroids
• Oriented Matroids
• Oriented matroids
• Orienting matroids representable over both GF(3) and GF(5)
• Some minimal non-orientable matroids of rank three
• Testing orientability for matroids is NP-complete
• The Forbidden Minors of Binary Clutters
• The incidence structure of subspaces with well-scaled frames
• The Tutte group of a weakly orientable matroid

Cited in

(4)

• Invariant theory-like theorems for matroids and oriented matroids
• Graphs with large girth and chromatic number are hard for Nullstellensatz
• Ramsey numbers through the lenses of polynomial ideals and Nullstellensätze
• An algebraic perspective on Ramsey numbers

This page was built for publication: Weak orientability of matroids and polynomial equations

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