Matroid packing and covering with circuits through an element

摘要

In 1981, Seymour proved a conjecture of Welsh that, in a connected matroid M, the sum of the maximum number of disjoint circuits and the minimum number of circuits needed to cover M is at most r * (M) + 1. This paper considers the set C-e (M) of circuits through a fixed element e such that M/e is connected. Let v(e) (M) be the maximum size of a subset of C, (M) in which any two distinct members meet only in {e}, and let theta(e)(M) be the minimum size of a subset of C-e(M) that covers M. The main result proves that v,(M) + theta(e)(M) <= r*(M) + 2 and that if M has no Fano-minor using e, then v(e) (M) + theta(e) (M) <= r* (M) + 1. Seymour's result follows without difficulty from this theorem and there are also some interesting applications to graphs. (c) 2005 Elsevier Inc. All rights reserved.