Optimal matchings in posets

DOI10.1016/S0195-6698(83)80025-0MaRDI QIDQ792355zbMATH OpenFDO

Authors U. Faigle

Publication date 1983

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0195-6698(83)80025-0

zbMATH Keywords

distributive supermatroidgreedy algorithmideals of posetslattice of closed idealslattice of subspacesmatchable idealsoptimal matchings

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Partial orders, general (06A06) Lattice ideals, congruence relations (06B10) General theory of linear incidence geometry and projective geometries (51A05)

Review text

From the author's preface: We want to match (order)ideals of posets P and Q with respect to a relation that associates with every element of P an ideal of Q and conversely. The general theory for this distributive analog of classical matching theory is investigated and analogs of classical theorems are obtained. The collection of matchable ideals of P gives rise to a distributive supermatroid whose lattice of closed ideals is representable in the lattice of subspaces of a projective geometry. It is shown that with respect to order reversing weightings on P and Q, optimal matchings may be constructed according to the greedy algorithm for posets. The theory of integral vector linkings is discussed within this context.

Recommendations

• Poset matching---a distributive analog of independent matching
• Antimatroids induced by matchings
• Matching, matroids, and extensions
• Matching theory
• Matroid matching in pseudomodular lattices

Cites work

• Geometries on partially ordered sets
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3600054 (Why is no real title available?)
• scientific article; zbMATH DE number 3204690 (Why is no real title available?)
• scientific article; zbMATH DE number 3225808 (Why is no real title available?)
• Matching in modular lattices
• Matching Theory for Combinatorial Geometries
• Proof of a conjecture on finite modular lattices
• Rado's theorem for polymatroids
• Some Generalizations of the Problem of Distinct Representatives
• The greedy algorithm for partially ordered sets

Cited in

(8)

• Optimal general matchings
• scientific article; zbMATH DE number 6379409 (Why is no real title available?)
• Matchings and Radon transforms in lattices II. Concordant sets
• $n!$ matchings, $n!$ posets
• THE MINIMUM-WEIGHT IDEAL PROBLEM FOR SIGNED POSETS
• Finding a Level Ideal of a Poset
• Computing Optimal Morse Matchings
• Poset matching---a distributive analog of independent matching

This page was built for publication: Optimal matchings in posets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792355)