Compatible systems of representatives

DOI10.1016/0012-365X(92)00567-BMaRDI QIDQ1336656zbMATH OpenFDO

Authors Martin Kochol

Publication date 1 May 1995

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(92)00567-B

zbMATH Keywords

compatible systemmatroidrepresentativestheorem of Hall

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Graph theory (05C99)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 3914366
• Extending partial systems of distinct representatives
• scientific article; zbMATH DE number 1567836
• Hall's theorem for hypergraphs
• scientific article; zbMATH DE number 4031697

Cites work

• A characterization of transversal independence spaces
• A THEOREM ON INDEPENDENCE RELATIONS
• About a generalization of transversals
• Applications of the notion of independence to problems of combinatorial analysis
• Comments on bases in dependence structures
• Disjoint Common Transversals and Exchange Structures
• Exchange systems, matchings, and transversals
• scientific article; zbMATH DE number 3645097 (Why is no real title available?)
• scientific article; zbMATH DE number 3773596 (Why is no real title available?)
• scientific article; zbMATH DE number 3508509 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Lehmans switching game and a theorem of Tutte and Nash-Williams
• On Representatives of Subsets
• Symmetrized and continuous generalization of transversals
• The notion and basic properties of M-transversals
• Transversal Theory and Matroids
• Transversal theory. An account of some aspects of combinatorial mathematics
• Transversals and matroid partition

Cited in

(4)

• Extending partial systems of distinct representatives
• scientific article; zbMATH DE number 3847414 (Why is no real title available?)
• scientific article; zbMATH DE number 140122 (Why is no real title available?)
• scientific article; zbMATH DE number 1567877 (Why is no real title available?)

This page was built for publication: Compatible systems of representatives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336656)