Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Source. Section 6, printed p. 152 (published PDF), describes the bases and circuits of this construction and explicitly omits the general matroid verification. The following is a compilation-supplied expansion of that same construction.

Statement. Let M=(E,F)M=(E,\mathcal F) be a finite matroid, e∈Ee\in E, and let SS be a disjoint new set of k≥1k\ge1 elements. On E′=(E∖{e})∪SE'=(E\setminus\{e\})\cup S, declare A∪TA\cup T independent, where A⊆E∖{e}A\subseteq E\setminus\{e\} and T⊆ST\subseteq S, exactly when

A∈F,T≠S or A∪{e}∈F.(1)A\in\mathcal F,\qquad T\ne S\ \text{or}\ A\cup\{e\}\in\mathcal F. \tag{1}

This defines a matroid. Its bases are exactly

{(B∖{e})∪S,B a base of M, e∈B,B∪(S∖{s}),B a base of M, e∉B, s∈S.(2)\begin{cases} (B\setminus\{e\})\cup S,& B\text{ a base of }M,\ e\in B,\\ B\cup(S\setminus\{s\}),& B\text{ a base of }M,\ e\notin B,\ s\in S. \end{cases} \tag{2}

Its circuits are the old circuits omitting ee and the sets (C∖{e})∪S(C\setminus\{e\})\cup S for old circuits CC containing ee. Thus the new elements are in series, and k=1k=1 simply relabels ee.

Proof. Condition (1) contains the empty set and is hereditary. We verify augmentation and then use its equivalence to the finite matroid axiom. Let A∪TA\cup T and B∪UB\cup U satisfy (1), with

∣A∣+∣T∣<∣B∣+∣U∣.(3)|A|+|T|<|B|+|U|. \tag{3}

First suppose T≠ST\ne S. If ∣B∣>∣A∣|B|>|A|, augment AA by an element of B∖AB\setminus A in MM; the new-copy part is still proper in SS, so this also augments A∪TA\cup T under (1). If ∣B∣≤∣A∣|B|\le|A|, then (3) gives ∣U∣>∣T∣|U|>|T|. Choose s∈U∖Ts\in U\setminus T. It can be added if T∪{s}≠ST\cup\{s\}\ne S, and can also be added if A∪{e}A\cup\{e\} is independent.

The only remaining subcase has ∣T∣=k−1|T|=k-1, U=SU=S, and A∪{e}A\cup\{e\} dependent. Inequality (3) and ∣B∣≤∣A∣|B|\le|A| now force ∣B∣=∣A∣|B|=|A|. Since B∪UB\cup U satisfies (1), B∪{e}B\cup\{e\} is independent and has size ∣A∣+1|A|+1. Augment AA by an element of (B∪{e})∖A(B\cup\{e\})\setminus A. The augmenting element cannot be ee, which was assumed not to augment AA. It therefore lies in B∖AB\setminus A, and augments A∪TA\cup T under (1).

Now suppose T=ST=S, so A∪{e}A\cup\{e\} is independent. If U=SU=S, then B∪{e}B\cup\{e\} is independent and ∣B∣>∣A∣|B|>|A|. Augmentation between these two old independent sets adds an element of B∖AB\setminus A to A∪{e}A\cup\{e\}, as required by (1). If U≠SU\ne S, (3) instead gives ∣B∣≥∣A∣+2|B|\ge|A|+2. Augment the independent set A∪{e}A\cup\{e\} by the larger independent set BB. Again the added element is in B∖AB\setminus A and preserves (1) with all copies present. This proves augmentation in every case and hence the matroid property.

For the bases, an independent set with fewer than k−1k-1 copies can still take a copy. If exactly k−1k-1 copies are present, maximality requires that AA cannot be augmented by an old element and cannot take ee in MM. These conditions say exactly that AA is an old base omitting ee. If all kk copies are present, maximality says that A∪{e}A\cup\{e\} is an old base containing ee. Conversely, each set in (2) is independent by (1), and any further addition would augment its old base. Thus (2) lists precisely all bases.

Finally consider a minimal dependent set A∪TA\cup T. If AA is dependent in MM, minimality makes T=∅T=\varnothing and AA an old circuit omitting ee. Otherwise AA is independent, so dependence in (1) requires T=ST=S and A∪{e}A\cup\{e\} dependent. Its circuit contains ee; minimality then forces A=C∖{e}A=C\setminus\{e\} for that circuit CC. Conversely, a set of this latter form is dependent; deleting a copy makes TT proper, and deleting an old element makes the corresponding subset of CC independent. It is therefore a circuit. This proves the asserted circuit list, and the circuit characterization gives the series property. The proof includes an old loop or coloop. □\square

This fills the paper's stated local omission. It is not attributed to an author-issued erratum or to a separate published proof.