About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets
type: Item
instance of: scholarly article
title: About the ratio of the size of a maximum antichain to the size of a maximum level in finite partially ordered sets
zbMATH Open document ID: 0596.06001
DOI: 10.1007/BF02579244
author: Konrad Engel
author: N. N. Kuzyurin
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05A20
zbMATH DE Number: 3959492
zbMATH Keywords: partially ordered set
zbMATH Keywords: largest antichain
zbMATH Keywords: level
reviewed by: Daniel J. Kleitman
MaRDI profile type: Publication
cites work: Q3768943
cites work: Q3797242
cites work: An asymptotic formula for the maximum size of an h-family in products of partially ordered sets
cites work: Q4196436
cites work: Q3344243
cites work: Q4085018
cites work: Q3964569
full work available at URL: https://doi.org/10.1007/bf02579244
OpenAlex ID: W2015808943
description: scientific article; zbMATH DE number 3959492