Circuit decompositions of binary matroids
| Autor: | Frederickson, Bryce, Michel, Lukas |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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$. Comment: 10 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|