scientific article; zbMATH DE number 3910407

From MaRDI portal
Publication:3688403





[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.











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)