Article collection "Mathematical Problems of Cybernetics" №13, Moscow, 2004

Authors:Andreeva T.V.

Development of the boundary functional method and its applications to combinatorial problems

Abstract:

In the present paper, we develop enumeration problems solution methods and their applications to asymptotic of antichain number in partially ordered sets. We extend the area of application for the boundary functional method invented by A.A.Sapozhenko. We generalize this method to the case of irregular graphs and partial ordered sets as well as to the case of graphs with “weakly growing” degrees of vertices. We obtain an asymptotic for the number of antichains in a partially ordered set, which is a Cartesian power of a k-star for k ≤ 11. We also improve a known lower bound for the number of antichains in a three-valued n-dimensional lattice. An estimate for the ratio of cardinalities of neighbor layers in three-valued n-dimensional lattice is given. Finally, we prove the logarithmic convexity of the layer cardinalities in a k-valued n-dimensional lattice.

Keywords:

boundary functional method, asymptotic, antichain, partial ordered set