Some remarks on normalized matching (Q787981)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Some remarks on normalized matching |
scientific article |
Statements
Some remarks on normalized matching (English)
0 references
1983
0 references
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.
0 references
regular covering
0 references
ranked partial order
0 references
sequences of integers
0 references
LYM order
0 references
number of distinct chains
0 references