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 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 by a bipartite incidence graph with family side . To replace by a new -element set , give every copy the old neighbors of , and adjoin new family vertices, each adjacent to every copy and to no old element.
Let and . Any matching covering in the new graph matches to old family vertices. Hence is independent in the old transversal matroid.
If , the converse follows by matching as before and matching its at most copies injectively to the new family vertices. If , any matching of all copies must send at least one copy to an old family vertex. Its edge, together with the matching of , gives a matching of in the old graph. Conversely, from a matching of , match one copy to the vertex formerly assigned to , and match the other 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 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.