No label defined (Q3688403)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3910407
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3910407 |
Statements
1984
0 references
Intersecting subsets
0 references
crossing
0 references
minimum weight covering
0 references
directed cuts
0 references
edge weighted digraph
0 references
matroid polyhedra intersection theorem
0 references
0.9231322
0 references
0 references
0.8986498
0 references
[For the entire collection see Zbl 0559.00001.] The subsets A, B of a finite set S are intersecting if none of \(A\cap B\), A-B and B-A is empty. Intersecting subsets are crossing if their union is not S. A family \({\mathfrak F}\) of subsets of S are intersecting (or crossing) if \(A\cap B\in {\mathfrak F}\) and \(A\cup B\in {\mathfrak F}\) are implied for all intersecting (resp. crossing) pairs A, B from \({\mathfrak F}\). The subsets I with \(| I\cap X| \leq f(X)\) for every \(X\in {\mathfrak B}\) are the independent sets of a matroid if \({\mathfrak B}\) is an intersecting family of subsets and f is submodular on \({\mathfrak B}\) [\textit{J. Edmonds}, Submodular functions, matroids and certain polyhedra, Combinat. Struct. Appl., Proc. Calgary internat. Conf. combinat. Struct. Appl., Calgary 1969, 69-87 (1970; Zbl 0268.05019)]. This is not true for crossing families. The authors prove that the subsets B with \(| B| =k\), \(| B\cap X| \leq f(X)\) for every \(X\in {\mathfrak F}\) are the bases of a matroid if \({\mathfrak F}\) is a crossig family and f is submodular on \({\mathfrak F}\). They apply it to show how a minimum weight covering of directed cuts in an edge weighted digraph can be obtained if a weighted matroid intersection algorithm is available; and also deduce an orientation theorem of Nash-Williams from the matroid polyhedra intersection theorem.
0 references