Some remarks on normalized matching

DOI10.1016/0097-3165(83)90015-8MaRDI QIDQ787981zbMATH OpenOpenAlexFDO

Authors Douglas B. West, Lawrence H. Harper, David E. Daykin

Publication date 1983

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0097-3165(83)90015-8

zbMATH Keywords

LYM ordernumber of distinct chainsranked partial orderregular coveringsequences of integers

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial aspects of packing and covering (05B40) Partial orders, general (06A06)

Review text

An LYM order is a ranked partial order in which for each j, if there are a elements of rank j and b of rank \(j+1\) then there is a mapping from b copies of rank j to a copies of rank \(j+1\) such that each element is less than its image. This paper contains proofs of three results: 1. Let \(A_ 1,...,A_ r\) be a chain among subsets of an n element set S, and let \(a_ i\) and \(b_ i\) be two nondecreasing sequences of integers with \(a_ i\leq b_ i\) for each i. Then those subsets of S whose intersection with each \(A_ i\) has cardinality between \(a_ i\) and \(b_ i\) form a LYM order. (The order here is inclusion.) 2. In any LYM order P one can find a set of chains that contain each element of any given rank the same number of times. The minimum size of such a set of chains is here shown to be the least common multiple of the rank sizes (which are the number of elements of each rank). 3. Such a set of chains can always be obtained using at most a number of distinct chains given by the number of elements of P less the number of its ranks plus one.

Recommendations

• scientific article; zbMATH DE number 3880765
• A class of LYM orders in divisor lattices
• On the average rank of LYM-sets
• Matchings, cutsets, and chain partitions in graded posets
• Investigating posets via their maximal chains

Cites work

• A short proof of Sperner's lemma
• Collections of Subsets with the Sperner Property
• Generalization of Sperner’s Theorem on the Number of Subsets of a Finite Set
• scientific article; zbMATH DE number 3786783 (Why is no real title available?)
• scientific article; zbMATH DE number 3465294 (Why is no real title available?)
• scientific article; zbMATH DE number 3636041 (Why is no real title available?)
• Logarithmic order of free distributive lattice
• Normalized Matching in Direct Products of Partial Orders
• Some Results on Matching in Bipartite Graphs
• Sperner families over a subset
• Sufficient Conditions for a Symmetric Chain Order
• The morphology of partially ordered sets
• The structure of Sperner k-families

Cited in

(12)

• Methods for nesting rank 3 normalized matching rank-unimodal posets
• Some methods for ``normalizing patterns
• On the average rank of LYM-sets
• Matchings, cutsets, and chain partitions in graded posets
• Order-matchings in the partition lattice
• The normalized matching property in random and pseudorandom bipartite graphs
• On a conjecture of Füredi.
• Decompositions of the Boolean lattice into rank-symmetric chains.
• scientific article; zbMATH DE number 3880765 (Why is no real title available?)
• A normal law for matchings
• On nested chain decompositions of normalized matching posets of rank 3
• A class of LYM orders in divisor lattices

This page was built for publication: Some remarks on normalized matching

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