Another generalization of Lindstrom's theorem on subcubes of a cube

[摘要] We consider the poset P(N;A(1),A(2),...,A(m)) consisting of all subsets of a finite set N which do not contain any of the A(i)'s, where the A(i)'s are mutually disjoint subsets of N. The elements of P are ordered by inclusion. We show that P belongs to the class of Macaulay posets, i.e. we show a Kruskal-Katona-type theorem for P. For the case that the A(i)'s form a partition of N, the dual P* of P came to be known as the orthogonal product of simplices. Since the property of being a Macaulay poset is preserved by turning to the dual, we show, in particular, that orthogonal products of simplices are Macaulay posets. Besides, we prove that the posets P and P* are additive. (C) 2002 Elsevici Science (USA).

[发布日期] 2002-08-01

[关键词] Macaulay posets;shadow minimization;Kruskal-Katona theorem;orthogonal product of simplices