A unique factorization theorem for matroids

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:112

Article

Crapo, H ; Schmitt, W

关键词: matroid;    free product;    unique factorization;    minor coalgebra;    cofree coalgebra;    free algebra;   

DOI  :  10.1016/j.jcta.2005.02.004

来源: Elsevier

【 摘 要 】

We study the combinatorial, algebraic and geometric properties of the free product operation on matroids. After giving cryptomorphic definitions of free product in terms of independent sets, bases, circuits, closure, flats and rank function, we show that free product, which is a noncommutative operation, is associative and respects matroid duality. The free product of matroids M and N is maximal with respect to the weak order among matroids having M as a submatroid, with complementary contraction equal to N. Any minor of the free product of M and N is a free product of a repeated truncation of the corresponding minor of M with a repeated Higgs lift of the corresponding minor of N. We characterize, in terms of their cyclic flats, matroids that are irreducible with respect to free product, and prove that the factorization of a matroid into a free product of irreducibles is unique up to isomorphism. We use these results to determine, for K a field of characteristic zero, the structure of the minor coalgebra K{M} of a family of matroids M that is closed under formation of minors and free products: namely, K {M} is cofree, cogenerated by the set of irreducible matroids belonging to M. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free