𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Compatible systems of representatives

✍ Scribed by Martin Kochol

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
691 KB
Volume
132
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The main result of this paper can be quickly described as follows. Let G be a bipartite graph and assume that for any vertex v of G a strongly base orderable matroid is given on the set of edges adjacent with v. Call a subgraph of G a system of representatives of G if the edge neighborhood of each vertex of this subgraph is independent in the corresponding matroid. Two systems of representatives we call compatible if they have no common edge. We give a necessary and sufficient condition for G to have k pairwise compatible systems of representatives with at least d edges. Unfortunately, this condition is not sufficient if we deal with arbitrary matroids. Furthermore, we establish a listing variant of the Edmonds' covering theorem for strongly base orderable matroids.

πŸ“œ SIMILAR VOLUMES

Extending partial systems of distinct re
Extending partial systems of distinct representatives
✍ Peter HorΓ‘k πŸ“‚ Article πŸ“… 1991 πŸ› Elsevier Science 🌐 English βš– 234 KB

Horiik, P., Extending partial systems of distinct representatives, Discrete Mathematics 91 (1991) 95-98. We determine a necessary and sufficient condition for a special class of families of sets to have the property that each partial SDR of cardinahty d can be extended to a total SDR. This result i

Simultaneous systems of representatives
Simultaneous systems of representatives and combinatorial number theory
✍ Melvyn B. Nathanson πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 660 KB

This paper applies a recent theorem about simultaneous systems of representatives for families of finite sets to obtain combinatorial results that are closely related to problems concerning minimal asymptotic bases in additive number theory.

Heights of representative systems
Heights of representative systems
✍ Peter C. Fishburn πŸ“‚ Article πŸ“… 1979 πŸ› Elsevier Science 🌐 English βš– 820 KB
Acyclic systems of representatives and a
Acyclic systems of representatives and acyclic colorings of digraphs
✍ Ron Aharoni; Eli Berger; Ori Kfir πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 161 KB

## Abstract A natural digraph analog of the graph theoretic concept of β€œan independent set” is that of β€œan acyclic set of vertices,” namely a set not spanning a directed cycle. By this token, an analog of the notion of coloring of a graph is that of decomposition of a digraph into acyclic sets. We