Sperner''s theorem with constraints |
| |
Authors: | G. F. Clements |
| |
Affiliation: | Department of Mathematics, University of Colorado, Boulder, Colo. 80302, USA |
| |
Abstract: | A set X of subsets of an n-element set S is called an anti-chain if no two elements of X are related by set-wise inclusion. Sperner showed [8] that max |X|=(n[n/2]), where |X| denotes the number of elements in X and the maximum is taken over all anti-chains of subsets of S. Let non-negative integers io<n and mio≠0, mio+1,…mn be given. In this paper we give an algorithm for calculating max |X| where the maximum is taken only over anti-chains containing exactly mi i-element subsets of S for io i n. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|