Compatible systems of representatives (Q1336656): Difference between revisions

The author introduces the concept of \((M_ S, M_ T)\)-system of representatives and generalizes a result of Astration connected with the concept of a compatible system of representatives. If \(G\) is a bipartite graph then for any vertex \(v\) of \(G\) a matroid is given on the set of edges adjacent to \(v\). This is a so-called ``strongly base orderable'' matroid. A subgraph of \(G\) is a system of representatives of \(G\) if the neighborhood of each vertex of this sus subgraph is independent in the corresponding matroid. Two systems of representatives are compatible if they have no common edge. The main result of this paper is connected with the classical theorem of Hall on distinct representatives and gives a necessary and sufficient condition for \(G\) to have \(k\) pairwise compatible systems of representatives. The condition of the theorem is not sufficient for arbitrary matroids. Important is that the matroid is a strongly base orderable one.