pith. sign in

arxiv: 2306.14236 · v2 · pith:B72B4HX4new · submitted 2023-06-25 · 🧮 math.CO

Circuit decompositions of binary matroids

classification 🧮 math.CO
keywords circuitsbinaryoperatornamerankmanymatroidminimumnumber
0
0 comments X
read the original abstract

Given a simple Eulerian binary matroid $M$, what is the minimum number of disjoint circuits necessary to decompose $M$? We prove that $|M| / (\operatorname{rank}(M) + 1)$ many circuits suffice if $M = \mathbb F_2^n \setminus \{0\}$ is the complete binary matroid, for certain values of $n$, and that $\mathcal{O}(2^{\operatorname{rank}(M)} / (\operatorname{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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.