2011
An obstacle to a decomposition theorem for near-regular matroids
Publication
Publication
SIAM Journal on Discrete Mathematics , Volume 25 - Issue 1 p. 271- 279
Seymour's decomposition theorem [J. Combin. Theory Ser. B, 28 (1980), pp. 305–359] for regular matroids states that any matroid representable over both $\mathrm{GF}(2)$ and $\mathrm{GF}(3)$ can be obtained from matroids that are graphic, cographic, or isomorphic to $R_{10}$ by 1-, 2-, and 3-sums. It is hoped that similar characterizations hold for other classes of matroids, notably for the class of near-regular matroids. Suppose that all near-regular matroids can be obtained from matroids that belong to a few basic classes through $k$-sums. Also suppose that these basic classes are such that, whenever a class contains all graphic matroids, it does not contain all cographic matroids. We show that, in that case, 3-sums will not suffice.
Additional Metadata | |
---|---|
, , | |
S.I.A.M. | |
SIAM Journal on Discrete Mathematics | |
Matroid Structure for Efficiency | |
Organisation | Networks and Optimization |
Mayhew, D., Whittle, G., & van Zwam, S. (2011). An obstacle to a decomposition theorem for near-regular matroids. SIAM Journal on Discrete Mathematics, 25(1), 271–279. |