About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets (Q1078212)

From MaRDI portal
scientific article
Language Label Description Also known as
English
About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets
scientific article

    Statements

    About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets (English)
    0 references
    0 references
    1985
    0 references
    Given a partially ordered set consisting of k elements, how large a ratio can there be between the size of a largest antichain and the maximum number of elements at the same ''level'' in the order? (The level of an element x is the length of the longest chain of elements with top element x). How many orders achieve this bound? Given the n-fold product of copies of a k element order, how large can that same ratio be in the limit as n goes to infinity? and which orders achieve this bound? This paper contains answers to these questions. The first result is quite simple, and the answer is \(([k/2]+1)/2\). The configuration for even k is a chain of length k/2 with a disconnected vertex and one that covers each element of the chain except its top. The result for products uses results of Alexeev and of Korobkov on such products and some nontrivial argument. A perhaps interesting question not addressed is: how large can the ratio of largest antichain size be to the sum of the largest level as defined here and the same as defined with the order relation reversed, again for an ordered set with k elements.
    0 references
    0 references
    partially ordered set
    0 references
    largest antichain
    0 references
    level
    0 references