The cocycle lattice of binary matroids

DOI10.1006/EUJC.1993.1027MaRDI QIDQ1260774zbMATH OpenOpenAlexFDO

Authors Ákos Seress, László Lovász

Publication date 25 August 1993

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

Full work available at URL https://doi.org/10.1006/eujc.1993.1027

zbMATH Keywords

binary matroidboundscocycle latticedenominatordual latticepolynomial algorithm

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35)

Review text

If the weight of every cut in an edge-weighted simple graph is an integer, then the weight of every edge is an integer or a half-integer. This property \(P\) does not generalize to all binary matroids (but it does if the matroid has no parallel elements or Fano minors). The authors study the lattice (grid) generated by the incidence vectors of cocycles of a binary simple matroid, and the dual lattice. Among other results they give a polynomial algorithm to decide whether a binary matroid has the above property \(P\), and prove that every denominator in the dual lattice is a power of 2, deriving upper and lower bounds for the largest exponent.

Recommendations

• The cocycle lattice of binary matroids. II
• scientific article; zbMATH DE number 1341911
• Short cocircuits in binary matroids
• A construction for binary matroids
• Some New Matroids on Graphs: Cut Sets and the Max Cut Problem

Cited in

(8)

• Short cocircuits in binary matroids
• A construction for binary matroids
• Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions
• Weight distribution of the bases of a binary matroid
• The cocycle lattice of binary matroids. II
• Hilbert bases of cuts
• scientific article; zbMATH DE number 4002189 (Why is no real title available?)
• scientific article; zbMATH DE number 1341911 (Why is no real title available?)

This page was built for publication: The cocycle lattice of binary matroids

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