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
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
partially ordered set
0 references
largest antichain
0 references
level
0 references