On the Impossibility of Decomposing Binary Matroids

2022/06/26 by Marilena Leichter, Benjamin Moseley, Leichter, Marilena +3 · 1 citation
Computer Science · Mathematics · #Advanced Algebra and Logic #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · pdf · doi:10.48550/arxiv.2206.12896

openalex publication_date 2022/06/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We show that there exist k-colorable matroids that are not (b,c)-decomposable when b and c are constants. A matroid is (b,c)-decomposable, if its ground set of elements can be partitioned into sets X₁, X₂, …, X_l with the following two properties. Each set X_i has size at most ck. Moreover, for all sets Y such that |Y ∩ X_i| ≤ 1 it is the case that Y is b-colorable. A (b,c)-decomposition is a strict generalization of a partition decomposition and, thus, our result refutes a conjecture from arXiv:1911.10485v2 .

Cited by

• Efficiently Coloring the Intersection of a General Matroid and Partition Matroids

Related

• Random GF(q)-representable matroids are not (b,c)-decomposable
• Splitters and Decomposers for Binary Matroids
• Matroid Partition Property and the Secretary Problem
• Rainbow and monochromatic circuits and cuts in binary matroids
• The Weak-Map Order and Polytopal Decompositions of Matroid Base Polytopes