Master polytopes for cycles of binary matroids

DOI10.1016/0024-3795(89)90478-3MaRDI QIDQ1824625zbMATH OpenOpenAlexFDO

Authors Martin Grötschel, Klaus Truemper

Publication date 1989

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0024-3795(89)90478-3

zbMATH Keywords

binary matroidpolyhedral combinatorics

Mathematics Subject Classification ID

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorial aspects of matroids and geometric lattices (05B35)

Review text

L\({}_ k\), the complete binary matroid of order k, is defined by the binary standard representation matrix \([I| A_ k]\) where I is the identity matrix and \(A_ k\) is the 0-1 matrix with k columns that has as rows all possible distinct 0-1 vectors except for the k unit vectors and the 0-vector. For an arbitrary binary matroid P(M) denotes the convex hull of incidence vectors of cycles of M. The authors develop a method to deduce from the facets of \(P(L_ k)\) all facets of P(M) where M is a binary matroid of corank k. Next they apply a lifting procedure to produce for arbitrary binary matroids M a subset of the facets of P(M) using \(P(L_ j)\), \(j\leq k\).

Recommendations

• On the cycle polytope of a binary matroid
• Decomposition and optimization over cycles in binary matroids
• The cocycle lattice of binary matroids. II
• A construction for binary matroids
• scientific article; zbMATH DE number 1168010

Cites work

• Decomposition and optimization over cycles in binary matroids
• Decomposition of regular matroids
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• scientific article; zbMATH DE number 3133252 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• Matching, Euler tours and the Chinese postman
• Matroids and multicommodity flows
• On the cycle polytope of a binary matroid
• The max-cut problem on graphs not contractible to \(K_ 5\)

Cited in

(10)

• On the cycle polytope of a binary matroid
• Decomposition and optimization over cycles in binary matroids
• Determining a matroid polytope by non-Radon partitions
• Cycle bases for lattices of binary matroids with no Fano dual minor and their one-element extensions
• The cocycle lattice of binary matroids. II
• Cyclic flats of binary matroids
• scientific article; zbMATH DE number 3990246 (Why is no real title available?)
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• On a Generalization of the Master Cyclic Group Polyhedron
• Cycle algebras and polytopes of matroids

This page was built for publication: Master polytopes for cycles of binary matroids

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