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
    0 references
    0 references
    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

    Identifiers