DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Excluded subposets in the Boolean lattice

Gyula O.H. Katona


We are looking for the maximum number of subsets of an n-element set not containing 4 distinct subsets satisfying A ⊂B, C ⊂B, C ⊂D. It is proved that this number is at least the number of the ⌊n / 2⌋-element sets times 1+2 / n, on the other hand an upper bound is given with 4 replaced by the value 2.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional