Compatible systems of representatives (Q1336656): Difference between revisions
From MaRDI portal
Latest revision as of 10:10, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Compatible systems of representatives |
scientific article |
Statements
Compatible systems of representatives (English)
0 references
1 May 1995
0 references
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.
0 references
compatible system
0 references
representatives
0 references
matroid
0 references
theorem of Hall
0 references