The Structure of Sperner k-families

Document Type

Journal Article

Role

Author

Standard Number

0097-3165

Journal Title

Journal of Combinatorial Theory, Series A

Volume

20

Issue

1

First Page

41

Last Page

68

Publication Date

1976

Abstract

If P is a partially ordered set, a k-family of P is a subset which contains no chains of length k + 1. This paper examines the structure of the set of k-families of P. An extension of Dilworth's theorem is obtained by relating the maximum size of a k-family to certain partitions of P into chains. A natural lattice ordering on k-families is defined and analyzed, and a number of strong intersection properties are obtained. Finally, thek-families of P are used to define a class of submodular set functions on P, which can be used to generalize a number of results in transversal theory.

Share

COinS