scientific article; zbMATH DE number 3910407
[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.
- The structure of crossing separations in matroids
- scientific article; zbMATH DE number 67322
- scientific article; zbMATH DE number 1028231
- scientific article; zbMATH DE number 922670
- Matroids
- Matroids
- scientific article; zbMATH DE number 15361
- A characterization of matroidal families of multigraphs
- Families of matroids induced by classes of graphs
- Generalized polymatroids and submodular flows
- Coverings and structure of crossing families
- Intersecting matroids by a hyperplane
- Two matroidal families on the edge set of a graph
- Complexity of packing common bases in matroids
- scientific article; zbMATH DE number 437545 (Why is no real title available?)
- scientific article; zbMATH DE number 3841889 (Why is no real title available?)
- scientific article; zbMATH DE number 4110705 (Why is no real title available?)
- scientific article; zbMATH DE number 1792606 (Why is no real title available?)
- The no-meet matroid
- A cost-scaling algorithm for \(0-1\) submodular flows
- Lattice structure and efficient basis construction for strongly connected orientations
- Packing and covering of crossing families of cuts
- The structure of crossing separations in matroids
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3688403)