An asymptotic formula for the maximum size of an h-family in products of partially ordered sets
type: Item
instance of: scholarly article
title: An asymptotic formula for the maximum size of an h-family in products of partially ordered sets
zbMATH Open document ID: 0553.05012
DOI: 10.1016/0097-3165(84)90054-2
author: Konrad Engel
author: N. N. Kuzyurin
published in: Journal of Combinatorial Theory. Series A
publication date: 1984-01-01T00:00:00Z
review text: This paper contains derivation of an asymptotic formula for the width (maximum size of an unordered subset) of a partial order that is the direct product of n orders each of size less than some bound c, and each having a nonempty set of ordered pairs. The elements of each factor can be represented as real numbers so that ordered pairs differ by at least one. If one gives each element an equal weight and associates with each factor the minimal variance such representation of it, the product of these orders may be corresponded with the sum of these random variables. This sum obeys a central limit theorem, which gives the asymptotic formula: the width of the product order is asymptotic to its size divided by \(\sqrt(2\pi\) times the sum of the factor variances). Moreover for h of the form o(\(\sqrt{n})\), the union of h unordered sets is at most asymptotic to h times this number. That this is a lower bound follows easily by fleshing out the preceding description. That it is a lower bound is proven here by a difficult argument based upon the fact that for sufficiently large n most of the factors must occur very often for bounded c.
Mathematics Subject Classification ID: 05A99
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 06A06
zbMATH DE Number: 3880714
zbMATH Keywords: width of a partial order
zbMATH Keywords: direct product
zbMATH Keywords: asymptotic formula
reviewed by: Daniel J. Kleitman
MaRDI profile type: Publication
full work available at URL: 0097-3165(84)90054-2
OpenAlex ID: W1971147260
cites work: Q4149459
cites work: Q4044544
cites work: Optimal representations of partially ordered sets and a limit Sperner theorem
cites work: The structure of Sperner k-families
cites work: Q4196436
cites work: Q4085018
cites work: Dilworth Numbers, Incidence Maps and Product Partial Orders
description: scientific article; zbMATH DE number 3880714