Matroid matching with Dilworth truncation
The main theorem of the paper under review states that, given a hypergraph \(H=(V,E)\), if the rank function of the \((k,l)\)-matroid (also called \((k,l)\)-sparsity matroid) on the ground set \(E\) satisfies \(r(E(X)= \max(k| X| -l, 0)\) for every \(X\subseteq V\), then the matroid has the double circuit property as defined by \textit{A. Dress} and \textit{L. Lovász} in [``On some combinatorial properties of algebraic matroids, Combinatorica 7, 39--48 (1987; Zbl 0627.05016)]. From this, together with results from [\textit{L. Lovász}, ``Matroid matching and some applications, J. Comb. Theory, Ser. B 28, 208--236 (1980; Zbl 0444.05031)] the author concludes that L. Lovász's max-min formula for matroid matchings holds for those sparsity matroids. It is pointed out that the result includes, as special case among others, the Tutte-Berge formula and solves, moreover, the maximum matching problem in the two-dimensional generic rigidity matroid. The proofs exploit the structure of double circuits.
- Matroid matching with Dilworth truncation
- Generalized matroid matching
- Strict matching matroids and matroid algorithms
- Matching as the Intersection of Matroids
- Matching, matroids, and extensions
- Matroid matching in pseudomodular lattices
- Matroid matching via mixed skew-symmetric matrices
- Matroid matching: the power of local search
- Matroid matching: the power of local search
- Structural properties of matroid matchings
- A new characterization of the maximum genus of a graph
- An augmenting path algorithm for linear matroid parity
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity of Matroid Property Algorithms
- scientific article; zbMATH DE number 3141016 (Why is no real title available?)
- scientific article; zbMATH DE number 3902670 (Why is no real title available?)
- scientific article; zbMATH DE number 4047745 (Why is no real title available?)
- scientific article; zbMATH DE number 3703542 (Why is no real title available?)
- scientific article; zbMATH DE number 3750968 (Why is no real title available?)
- scientific article; zbMATH DE number 3561367 (Why is no real title available?)
- Matroid matching and some applications
- Matroid matching in pseudomodular lattices
- Matroid matching via mixed skew-symmetric matrices
- On Generic Rigidity in the Plane
- On graphs and rigidity of plane skeletal structures
- On some combinatorial properties of algebraic matroids
- Solving the linear matroid parity problem as a sequence of matroid intersection problems
- The linear delta-matroid parity problem
- The weak series reduction property implies pseudomodularity
This page was built for publication: Matroid matching with Dilworth truncation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476281)
