Circuit decompositions of binary matroids

2023/06/25 by Bryce Frederickson, Frederickson, Bryce, Lukas Michel +1
Computer Science · Mathematics · #05B35 (Primary) 05C38 #05C70 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Commutative Algebra and Its Applications #FOS: Mathematics #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.2306.14236

openalex publication_date 2023/06/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a simple Eulerian binary matroid M, what is the minimum number of disjoint circuits necessary to decompose M? We prove that |M| / (rank(M) + 1) many circuits suffice if M = \mathbb F₂ⁿ ∖ \0\ is the complete binary matroid, for certain values of n, and that O(2^rank(M) / (rank(M) + 1)) many circuits suffice for general M. We also determine the asymptotic behaviour of the minimum number of circuits in an odd-cover of M.

Related

• On the Number of Circuits in Regular Matroids (with Connections to Lattices and Codes)
• The k-fold circuit property for matroids
• Efficient Algorithms for Maximal Matroid Degenerations and Irreducible Decompositions of Circuit Varieties
• Odd circuits in dense binary matroids
• Minimal matroids in dependency posets: algorithms and applications to computing irreducible decompositions of circuit varieties