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 pp. 152–153 (published PDF).

Statement. Series replacement by k≥1k\ge1 copies, adjoining coloops, and restriction to a subset of the ground set all preserve the class of finite transversal matroids.

Proof. Present the transversal matroid on EE by a bipartite incidence graph with family side II. To replace ee by a new kk-element set SS, give every copy the old neighbors of ee, and adjoin k−1k-1 new family vertices, each adjacent to every copy and to no old element.

Let A⊆E∖{e}A\subseteq E\setminus\{e\} and T⊆ST\subseteq S. Any matching covering A∪TA\cup T in the new graph matches AA to old family vertices. Hence AA is independent in the old transversal matroid.

If T≠ST\ne S, the converse follows by matching AA as before and matching its at most k−1k-1 copies injectively to the new family vertices. If T=ST=S, any matching of all kk copies must send at least one copy to an old family vertex. Its edge, together with the matching of AA, gives a matching of A∪{e}A\cup\{e\} in the old graph. Conversely, from a matching of A∪{e}A\cup\{e\}, match one copy to the vertex formerly assigned to ee, and match the other k−1k-1 copies to the new family vertices.

Thus the independent sets in the new graph obey exactly condition (1) for series extension. This proves the first assertion, including k=1k=1 when no new family vertex is added.

To adjoin a coloop, add one new ground element and one new family vertex joined only to each other. A ground subset in the resulting graph is independent exactly when its old part is independent; the new element can always be added. It therefore belongs to every base. Repeating this constructs any finite set of added coloops.

For restriction, delete the unwanted ground vertices from the representing bipartite graph, retaining the family side. The matchings witnessing independence of the remaining subsets are unchanged. Hence the restricted matroid is again transversal. □\square