×

An asymptotic formula for the maximum size of an h-family in products of partially ordered sets. (English) Zbl 0553.05012

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.
Reviewer: D.Kleitman

MSC:

05A99 Enumerative combinatorics
60C05 Combinatorial probability
06A06 Partial orders, general
Full Text: DOI

References:

[1] Aigner, M., Kombinatorik, II (1976), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York · Zbl 0373.05002
[2] Alekseev, V. B., O čisle monotonnych \(k\)-značnych funkcij, Problemy Kibernet., 28, 5-24 (1974) · Zbl 0293.02014
[3] K. Engel; K. Engel · Zbl 0651.05014
[4] Ford, L.; Fulkerson, D., Potoki v setjach (1966), Mir: Mir Moscow
[5] Greene, C.; Kleitman, D. J., The structure of Sperner \(k\)-families, J. Combin. Theory Ser. A, 20, 41-68 (1976) · Zbl 0363.05006
[6] Greene, C.; Kleitman, D. J., Proof techniques in the theory of finite sets, (Rota, G.-C, Studies in Combinatorics. Studies in Combinatorics, MAA Studies in Mathematics 17 (1978)), 22-79, Washington, D.C. · Zbl 0409.05012
[7] Ore, O., Teorija grafov (1980), Nauka: Nauka Moscow
[8] Petrov, V. V., Sums of Independent Random Variables (1975), Akademie-Verlag: Akademie-Verlag Berlin · Zbl 0322.60043
[9] Saks, M., Dilworth numbers, incidence maps and product partial orders, SIAM J. Algebra Discrete Methods, 1, 211-215 (1980) · Zbl 0501.06003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.