Families of sets with locally bounded width |
| |
Authors: | Emanuel Knill |
| |
Institution: | 1. Los Alamos National Laboratory, Mailstop B265, P.O. Box 1663, 87545, Los Alamos, NM
|
| |
Abstract: | A family of sets ? islocally k- wide if and only if the width (as a poset ordered by inclusion) of ? is at mostk for everyx. The directed covering graph of a locally 1-wide family of sets is a forest of rooted trees. It is shown that if ? is a locallyk-wide family of subsets of {1,...,n}, then |?|≤(2k) k?1 n. The proof involves a counting argument based on families of closed sets associated with theSperner closures in the filters of ?. The Sperner closure ofU in ? is the intersection of the members of the greatest Sperner antichain of ? U = {V ∈ ?|V ?U}. This closure operation is related to a generalization of maximality in posets. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|