Antichains on three levels

Paulette Lieby

    Research output: Contribution to journalComment/debate

    Abstract

    An antichain is a collection of sets in which no two sets are comparable under set inclusion. An antichain A is flat if there exists an integer k greater than or equal to 0 such that every set in A has cardinality either k or k + 1. The size of A is -A- and the volume of A is Sigma(Ais an element ofA) -A-. The flat antichain theorem states that for any antichain A on [n] = {1, 2,..., n} there exists a flat antichain on [n] with the same size and volume as A. In this paper we present a key part of the proof of the flat antichain theorem, namely we show that the theorem holds for antichains on three consecutive levels; that is, in which every set has cardinality k+1, k or k-1 for some integer k greater than or equal to 1. In fact we prove a stronger result which should be of independent interest. Using the fact that the flat antichain theorem holds for antichains on three consecutive levels, together with an unpublished result by the author and A. Woods showing that the theorem also holds for antichains on four consecutive levels, A. Kisvolcsey completed the proof of the flat antichain theorem. This proof is to appear in Combinatorica. The squashed ( or colex) order on sets is the set ordering with the property that the number of subsets of a collection of sets of size k is minimised when the collection consists of an initial segment of sets of size k in squashed order. Let p be a positive integer, and let A consist of p subsets of [ n] of size k + 1 such that, in the squashed order, these subsets are consecutive. Let B consist of any p subsets of [ n] of size k-1. Let -Delta(N)A- be the number of subsets of size k of the sets in A which are not subsets of any set of size k+1 preceding the sets in A in the squashed order. Let -delB- be the number of supersets of size k of the sets in B. We show that -Delta(N)A-+-delB- > 2p. We call this result the 3-levels result. The 3-levels result implies that the flat antichain theorem is true for antichains on at most three, consecutive, levels.
    Original languageEnglish
    Pages (from-to)R50-
    JournalJournal of Combinatorics
    Volume11
    Issue number2
    Publication statusPublished - 2004

    Fingerprint

    Dive into the research topics of 'Antichains on three levels'. Together they form a unique fingerprint.

    Cite this