Antichains on three levels

Paulette Lieby

The electronic journal of combinatorics, Tome 11 (2004) no. 1

Résumé

An antichain is a collection of sets in which no two sets are comparable under set inclusion. An antichain ${\cal A}$ is flat if there exists an integer $k\geq 0$ such that every set in ${\cal A}$ has cardinality either $k$ or $k+1$. The size of ${\cal A}$ is $|{\cal A}|$ and the volume of ${\cal A}$ is $\sum_{A\in{\cal A}}|A|$. The flat antichain theorem states that for any antichain ${\cal A}$ on $[n]=\{1,2,\ldots,n\}$ there exists a flat antichain on $[n]$ with the same size and volume as ${\cal 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\geq 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, Á. Kisvölcsey 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 ${\cal A}$ consist of $p$ subsets of $[n]$ of size $k+1$ such that, in the squashed order, these subsets are consecutive. Let ${\cal B}$ consist of any $p$ subsets of $[n]$ of size $k-1$. Let $|\triangle_N{\cal A}|$ be the number of subsets of size $k$ of the sets in ${\cal A}$ which are not subsets of any set of size $k+1$ preceding the sets in ${\cal A}$ in the squashed order. Let $|{\bigtriangledown}{\cal B}|$ be the number of supersets of size $k$ of the sets in ${\cal B}$. We show that $|\triangle_N{\cal A}| + |{\bigtriangledown}{\cal B}| > 2 p$. 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.

Détail

DOI : 10.37236/1803

Classification : 05D99
Mots-clés : antichain, flat antichain theorem