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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. of Math.51, 161–166 (1950)
Dilworth, R.P.: Some combinatorial problems on partially ordered sets. In Combinatorial Analysis, Proc. Symp. Appl. Math. (American Mathematical Society, Providence, R.I., 1960) 85
Greene, C, Kleitman, DJ.: The structure of Sperner k-families. J. Comb. Theory Ser. A20, 41–68 (1976)
Grimaldi, R.P.: Discrete and Combinatorial Mathematics, an Applied Introduction, 2nd ed., (Addison-Wesley Pub. Reading, Massachusetts, 1989)
Kendig, K.: Elementary Algebraic Geometry (Springer Verlag, New York, 1977)
Knill, E.: Generalized degrees and densities for families of sets, Ph.D. Thesis, University of Colorado, Boulder, CO, 1991
Knill, E.: Extreme k-families. Eur. J. Comb. (to be published)
Stanley, R.P.: Enumerative Combinatorics, Vol I, Wadsworth&Brooks/Cole, Monterey, Cal., 1986
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Knill, E. Families of sets with locally bounded width. Graphs and Combinatorics 10, 145–157 (1994). https://doi.org/10.1007/BF02986659
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02986659