𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The Cocycle Lattice of Binary Matroids

✍ Scribed by László Lovász; Ákos Seress

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
330 KB
Volume
14
Category
Article
ISSN
0195-6698

No coin nor oath required. For personal study only.

✦ Synopsis

We study the lattice (grid) generated by the incidence vectors of cocycles of a binary matroid and its dual tattice. We characterize those binary matroids for which the obvious necessary conditions for a vector to belong to the cocycle lattice are also sufficient. This characterization yields a polynomial time algorithm to check whether a matroid has this property, and also to construct a basis in the cocycle lattice. For the general case, we prove that every denominator in the dual lattice is a power of 2 , and derive upper and lower bounds for the largest exponent.

📜 SIMILAR VOLUMES

On the Connectivity Function of a Binary
On the Connectivity Function of a Binary Matroid
✍ Manoel Lemos 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 210 KB

In this paper, we shall consider the following problem: up to duality, is a connected matroid reconstructible from its connectivity function? Cunningham conjectured that this question has an affirmative answer, but Seymour gave a counter-example for it. In the same paper, Seymour proved that a conne

Cycle Bases for Lattices of Binary Matro
Cycle Bases for Lattices of Binary Matroids with No Fano Dual Minor and Their One-Element Extensions
✍ Tamás Fleiner; Winfried Hochstättler; Monique Laurent; Martin Loebl 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 185 KB

In this paper we study the question of existence of a basis consisting only of cycles for the lattice Z(M) generated by the cycles of a binary matroid M. We show that if M has no Fano dual minor, then any set of fundamental circuits can be completed to a cycle basis of Z(M); moreover, for any one-el