Flattening Antichains with Respect to the Volume

Ljiljana Brankovic

Department of Computer Science and Software Engineering

The University of Newcastle NSW 2308 Australia

       e-mail: lbrankov@cs.newcastle.edu.au

Paulette Lieby

School of Mathematical and Physical Sciences Northern Territory University, Darwin, NT Australia

            e-mail: paule@it.ntu.edu.au

Mirka Miller

Department of Computer Science and Software Engineering

The University of Newcastle NSW 2308 Australia

         e-mail: mirka@cs.newcastle.edu.au

Submitted: September 10, 1998; Accepted: November 9, 1998.

AMS Subject Classification: 05D99.

Abstract

We say that an antichain A in the boolean lattice B_{n} is flat if there exists an integer k ≥ 0 such that every set in A has cardinality either k or k + 1. Define the volume of A to be ∑_{A∈A} |A|. We prove that for every antichain A in B_{n} there exist an antichain which is flat and has the same volume as A.

1 Introduction

Throughout the paper the universal set is [n] = {1, 2, … n}. A collection A of subsets of [n] is an antichain if for any distinct A, B ∈ A, A ⊈ B. The parameters of an antichain A are the non-negative integers p_{i}, 0 ≤ i ≤ n, such that p_{i} = |A_{i}| where A_{i} = {A : |A| = i, A ∈ A}.

Let A be an antichain. We say that A is flat if, for any A ∈ A, |A| = k or |A| = k+1, for some non-negative integer k. Thus the parameters of A are such that p_{i} = 0 for i ≠ k, k + 1. The size of A is |A| and its volume is V (A) = ∑_{A∈A} |A|.

The concept of flattening an antichain is illustrated in the proof of Sperner’s seminal result which establishes the maximal size an antichain can have. In this proof it is shown that, if A is an antichain of size s, then there exists an antichain consisting of s ⌊\frac{n}{2}⌋-sets.

A result by Kleitman and Milner[5], Clements[2], and more recently by Maire[8], shows that, if A is an antichain whose average set size is an integer, then there exists a flat antichain having the same size and volume as A. The ideal of a collection of sets B is IB = {C : C ⊆ B, B ∈ B}. Clements[2] proved that, given s, an antichain A of size s which achieves minimum (or maximum) volume and minimum (or maximum) ideal is flat.

Lieby[7] conjectured that, if A is an antichain of size s and volume V, then there exists a flat antichain of size s and volume V. Note that the result by Kleitman and Milner[5] and others is a special case of the latter conjecture. In this paper we remove the constraint on s to prove that for every antichain A there exists a flat antichain with same volume as A.

Our main result is:

Theorem 1. If A is an antichain then there exists a flat antichain with volume V (A).

The next section, Section 2, provides the necessary background material; Section 3 establishes preliminary results needed in the proof of Theorem 1 which is presented in Section 4.

2 Background

If B is a collection of k-sets, 0 < k ≤ n, the shadow of B is △B = {C : |C| = k − 1, C ⊂ B, B ∈ B}. Similarly, the shade of B is ▽B = {C : |C| = k + 1, B ⊂ C, B ∈ B}.

Sperner’s lemma gives a relationship between the size of a collection of sets and the sizes of its shadow and shade:

Lemma 1 (Sperner[9]). Let B be a collection of k-subsets of [n]. Then

|△B| ≥ \frac{k}{n − k + 1}|B| if k > 0

and

|▽B| ≥ \frac{n − k}{k + 1} |B| if k < n.

An order relation on sets, the squashed order, denoted by ≤_{S}, is defined: If A and B are any sets, then A ≤_{S} B if the largest element of A + B is in B, where A + B denotes the symmetric difference of A and B. A squashed antichain A is an antichain such that for each i, the sets in A of size i, together with the sets of size i contained in all the larger members of A, constitute an initial segment of the sets of size i in squashed order.

Kruskal[6] and Katona[4] showed that the shadow of a collection of k-sets B is minimised when B is an initial segment of the k-sets in squashed order. One important consequence of this result is

Theorem 2 (Clements[1], Daykin[3]). There exists an antichain with p_{i} i-sets if and only if there exists a squashed antichain with p_{i} i-sets, 0 ≤ i ≤ n.

If B is any collection of consecutive k-sets in squashed order, then the new-shadow of B, denoted by △_{N}B, is the collection of the (k − 1)-sets that belong to the shadow of B but not to the shadow of any k-set that comes before any set of B in the squashed ordering of sets. That is, the new-shadow of B is the contribution of the sets in B to the shadow of the first p k-sets in squashed order, where p is such that the pth set in squashed order is the last set in B.

The new-shade of B, denoted by ▽_{N}B, is defined in a similar way. It consists of the (k + 1)-sets that are in the shade of B but not in the shade of any k-set that comes after any set of B in the squashed ordering of sets.

Formally, if B is a collection of consecutive k-sets in squashed order, then the newshadow of B is △_{N}B = {D : D ∈ △B and D ∉ △C for all C ≤_{S} B, C ∉ B, B ∈ B}. The new-shade of B is ▽_{N}B = {D : D ∈ ▽B and D ∉ ▽C for all C, B ≤_{S} C, C ∉ B, B ∈ B}. Note 1. By Theorem 2 we only need to consider squashed antichains, so that throughout the rest of this paper only squashed antichains will be considered.

Notation. We set K = \frac{n}{2} + 1 for n even and K = \frac{n+1}{2} for n odd.

3 Preliminary Results

This section presents the technical results needed in the proof of Theorem 1. Lemma 2 establishes a relationship between the respective sizes of the volume of a collection of sets in squashed order and the volume of its shadow. Lemma 3 establishes a similar relationship with the volume of its shade.

Lemma 2. Let B be a collection of l-sets. If l > K for n odd or l ≥ K for n even then V (△B) ≥ V (B).

Proof. By Sperner’s lemma |△B| ≥ \frac{l}{n−l+1}|B| so that

V (△B) ≥ (l − 1)\frac{l}{n − l + 1}|B| ≥ l|B| = V (B)

for \frac{l−1}{n−l+1} ≥ 1, that is for l ≥ \frac{n+2}{2}.

Lemma 3. Let B be a collection of l-sets. If l < K then V (▽B) ≥ V (B).

Proof. By Sperner’s lemma |▽B| ≥ \frac{n−l}{l+1}|B| so that

V (▽B) ≥ (l + 1)\frac{n − l}{l + 1}|B| ≥ l|B| = V (B)

for n − l ≥ l, that is for l ≤ \frac{n}{2}.

The next three lemmas give an upper bound for V (A) where A is an antichain satisfying certain conditions. In particular, Lemma 4 says that if A is an antichain whose largest set has size K + 1 and having parameter p_{K+1} > K + 2, then V (A) is bounded above by the volume of the antichain A^{∗} obtained from A by replacing (K + 1)-sets by K-sets so that A^{∗} has exactly (K + 2) (K + 1)-sets.

Lemma 5 says that, for n odd, if A is an antichain whose smallest set has size K − 1 and having parameter p_{K−1} > K + 1, then V (A) is bounded above by the volume of the antichain A^{∗} obtained from A by replacing (K − 1)-sets by K-sets so that A^{∗} has exactly (K + 1) (K − 1)-sets. Lemma 6 says that, for n even, if A is an antichain whose smallest set has size K − 2 and having parameter p_{K−2} > K + 1, then V (A) is bounded above by the volume of the antichain A^{∗} obtained from A by replacing (K − 2)-sets by (K − 1)-sets so that A^{∗} has exactly (K + 1) (K − 2)-sets.

Recall that all antichains are assumed to be squashed, so that “first”and “last” refer to first and last in the context of the squashed ordering of sets.

Lemma 4. For n ≥ 5 let A be an antichain with parameters p_{i} such that p_{i} = 0 for i > K + 1, and p_{K+1} > K + 2. Let A^{∗} be the antichain obtained from A by replacing all the (K + 1)-sets of A but the first (K + 2) (K + 1)-sets by all the K-sets in their new-shadow. Then V (A^{∗}) ≥ V (A).

Proof. We start by describing the list of the (K +1)-sets in squashed order. The idea of the squashed order is to use as few elements as possible when listing the sets. The first (K + 1)-set is \{1, …, K + 1\}. This set is followed by \binom{K+1}{K} sets, each of them being the union of one of the \binom{K+1}{K} K-subsets of [K + 1] with the set \{K + 2\}. This collection is itself followed by \binom{K+2}{K} sets, each of them being the union of one of the \binom{K+2}{K} K-subsets of [K + 2] with the set \{K + 3\}.

Therefore the collection of \binom{n}{K+1} (K + 1)-sets in squashed order can be subdivided into subcollections of size \binom{i}{K} each, K ≤ i ≤ n − 1. For a given i, any set in the subcollection of size \binom{i}{K} is the union of one of the \binom{i}{K} K-subsets of [i] and \{i + 1\}.

Let A be as defined in the statement of the lemma and consider A_{K+1}, the subcollection of A consisting of its (K + 1)-sets. By the introductory remark, A_{K+1} is the union of consecutive collections A^{i} of consecutive (K + 1)-sets in squashed order where for some I, K ≤ I ≤ n − 1, |A^{i}| = \binom{i}{K} for K ≤ i < I, |A^{i}| ≤ \binom{i}{K} for i = I, and |A^{i}| = 0 for i > I.

Let i be given, K ≤ i ≤ I. We have seen that any (K + 1)-set of A^{i} is the union of one of the \binom{i}{K} K-subsets of [i] sets and \{i + 1\}. Therefore the sets in △_{N}A^{i}, i > K, are the union of one of the \binom{i}{K−1} (K − 1)-subsets of [i] and \{i + 1\}. This is the case since any K-set not containing the element i + 1, i > K, must be in the shadow of some set which precedes the sets in A^{i} in squashed order.

Let B^{i} = {B : |B| = K, B ⊂ A, A ∈ A^{i}, i + 1 ∉ B}. Note that

(i) |B^{i}| = |A^{i}| ≤ \binom{i}{K}. (ii) The sets in B^{i} constitute an initial segment of K-subsets of [i] in squashed order, so that |△_{N}A^{i}| = |△B^{i}| for K < i ≤ I.

By Sperner’s lemma we have

|△B^{i}| ≥ \frac{K}{i − K + 1} |B^{i}| .

From (i) and (ii) it follows that

V (△_{N}A^{i}) = K|△_{N}A^{i}| ≥ K \frac{K}{i − K + 1} |A^{i}| ≥ (K + 1) |A^{i}| = V (A^{i})

for K < i ≤ I ≤ n − 1. Also,

|△_{N} (A_{K+1} \ (A^{K} ∪ A^{K+1}))| = ∑_{i=K+2}^{I} |△_{N}A^{i}|

so that

V (△_{N} (A_{K+1} \ (A^{K} ∪ A^{K+1}))) = ∑_{i=K+2}^{I} V (△_{N}A^{i})

≥ ∑_{i=K+2}^{I} V (A^{i})

= V (A_{K+1} \ (A^{K} ∪ A^{K+1})) .

A^{∗} is the antichain obtained from A by replacing all the (K + 1)-sets in A^{i}, K + 2 ≤ i ≤ I, by all the K-sets in △_{N}A^{i}. Note that |A^{K} ∪ A^{K+1}| = K + 2. This implies

V (A^{∗}) = V (A) − V (A_{K+1} \ (A^{K} ∪ A^{K+1}))
+ V (△_{N} (A_{K+1} \ (A^{K} ∪ A^{K+1})))
≥ V (A) .

This proves the lemma.

We now need to establish a similar result to the one stated in the previous lemma in the case where A^{∗} is obtained from A by replacing sets of A by sets in their newshade. The proofs of the following lemmas are similar to the proof of Lemma 4 and we shall try to keep them as short as possible. We need to discuss the cases n odd and n even separately.

Without loss of generality we assume that for any antichain considered below, the sets of smallest size, l say, form a terminal segment of l-sets in squashed order.

Lemma 5. For n odd and n ≥ 5 let A be an antichain with parameters p_{i} such that p_{i} = 0 for i < K − 1 and p_{K−1} > K + 1. Let A^{∗} be the antichain obtained from A by replacing all the (K − 1)-sets but the last (K + 1) (K − 1)-sets by all the K-sets in their new-shade. Then V (A^{∗}) ≥ V (A).

Proof. Let A be as defined in the statement of the lemma and consider A_{K−1}, the subcollection of A consisting of its (K−1)-sets. Then A_{K−1} is the union of consecutive collections A^{i} of consecutive (K − 1)-sets in reverse squashed order where for some I, K − 1 ≤ I ≤ n − 1, |A^{i}| = \binom{i}{i−K+1} for K − 1 ≤ i < I, |A^{i}| ≤ \binom{i}{i−K+1} for i = I, and |A^{i}| = 0 for i > I.

To see this, note that the last (K − 1)-set in squashed order is the set {K + 1, K + 2, …, n\} where n = 2K − 1 as n is odd. This set is preceded by \binom{K}{1} sets, each of them being the union of one of the singletons of [K] with the set {K + 2, …, n}. It is now easy to see that this collection is itself preceded by \binom{K+1}{2} sets, each of them being the union of one of the \binom{K+1}{2} 2-subsets of [K + 1] with the set \{K + 3, …, n\}.

In general, for K − 1 ≤ i ≤ I, any (K − 1)-set of A^{i} is the union of one of the \binom{i}{i−K+1} (i − K + 1)-subsets of [i] and {i + 2, …, n}, so that the sets in ▽_{N}A^{i} are the union of one of the \binom{i}{i−K+2} (i − K + 2)-subsets of [i] and \{i + 2, …, n\}.

Let B^{i} = {B : |B| = i − K + 1, B ⊂ A, A ∈ A^{i}, B ∩ {i + 2, …, n} = ∅}. Note that (i) |B^{i}| = |A^{i}| ≤ \binom{i}{i−K+1}. (ii) The sets in B^{i} constitute a terminal segment of (i − K + 1)-subsets of [i] in squashed order, so that |▽_{N}A^{i}| = |▽B^{i}|.

By Sperner’s lemma we have

|▽B^{i}| ≥ \frac{K − 1}{i − K + 2} |B^{i}| .

From (i) and (ii) it follows that

V (▽_{N}A^{i}) = K|▽_{N}A^{i}| ≥ K \frac{K − 1}{i − K + 2} |A^{i}| ≥ (K − 1) |A^{i}| = V (A^{i})

for K − 1 ≤ i ≤ I ≤ n − 1. Also,

|▽_{N} (A_{K−1} \ (A^{K−1} ∪ A^{K}))| = ∑_{i=K+1}^{I} |▽_{N}A^{i}|

so that

V (▽_{N} (A_{K−1} \ (A^{K−1} ∪ A^{K}))) = ∑_{i=K+1}^{I} V (▽_{N}A^{i})

≥ ∑_{i=K+1}^{I} V (A^{i})

= V (A_{K−1} \ (A^{K−1} ∪ A^{K})) .

Lemma 6. For n even and n ≥ 5 let A be an antichain with parameters p_{i} such that p_{i} = 0 for i < K − 2 and p_{K−2} > K + 1. Let A^{∗} be the antichain obtained from A by replacing all the (K − 2)-sets but the last (K + 1) (K − 2)-sets by all the (K − 1)-sets in their new-shade. Then V (A^{∗}) ≥ V (A).

Proof. Let A be as defined in the statement of the lemma and consider A_{K−2}, the subcollection of A consisting of its (K−2)-sets. Then A_{K−2} is the union of consecutive collections A^{i} of consecutive (K − 2)-sets in reverse squashed order where for some I, K − 1 ≤ I ≤ n − 1, |A^{i}| = \binom{i}{i−K+1} for K − 1 ≤ i < I, |A^{i}| ≤ \binom{i}{i−K+1} for i = I, and |A^{i}| = 0 for i > I.

The same argument as the one used in the proof of Lemma 5 shows that

V (▽_{N} (A_{K−2} \ (A^{K−1} ∪ A^{K}))) ≥ V (A_{K−2} \ (A^{K−1} ∪ A^{K})) .

4 Proof of Theorem 1

To prove Theorem 1 we first prove that there exists a flat antichain with volume V for each V < U_{n}, where U_{n} is defined below. Then, by making use of the results of Section 3, we characterise some antichains whose volume is less than U_{n}, that is, antichains which can be flattened while keeping the volume constant. Consequently, we characterise all antichains whose volume is greater than or equal to U_{n}. The proof the electronic journal of combinatorics 6 (1999), #R1 8

of Theorem 1 concludes by showing that all the latter antichains can be flattened while keeping size and volume constant. We start by showing that for every V < U_{n} there exists a flat antichain of volume V. Observation 1. For every antichain on [n], n ≤ 4, of size s and volume V, there is a flat antichain of size s and volume V. Note 2. Observation 1 is trivial for n < 4. It is easy to check that it holds for all possible antichains on [4]. Observation 2. The new-shades (starting at the end of the squashed order) of the last n − K + 2 (K − 1)-sets in squashed order have the cardinalities n − K + 1, n − K, …, 1, 0. The size of the shade of the last m (K − 1)-sets, m ≤ n − K + 2, is \frac{2n−2K+3−m}{2} × m. Lemma 7. For n ≥ 5 and for all V ≤ (K − 1)^{2} there exists a flat antichain with volume V.

Proof. Using only 1-sets and 2-sets, we can construct antichains with volumes 2x for x ≤ \binom{n}{2}, 2x + 1 for x ≤ \binom{n}{2} − (n − 1). Lemma 8. For n ≥ 5, let U_{n} = (\binom{n}{K} − \frac{2n−3K+4}{2}(K − 1) + 1) K + (K − 1)(K − 1). Then for each V < U_{n} there exists a flat antichain with volume V.

Proof. Using only K-sets and (K −1)-sets, we can construct antichains with volumes Kx for x ≤ \binom{n}{K} Kx + (K − 1), x ≤ \binom{n}{K} − (n − K + 1) Kx + 2(K − 1), x ≤ \binom{n}{K} − (n − K + 1) − (n − K) Kx + 3(K − 1), x ≤ \binom{n}{K} − (n − K + 1) − (n − K) − (n − K − 1) ⋮ Kx + (K − 1)(K − 1), x ≤ \binom{n}{K} − \frac{2n−3K+4}{2}(K − 1). This means that we can construct flat antichains with any volume V, (K−1)(K−1) < V < U_{n} using only K-sets and (K − 1)-sets. By Lemma 7, we can construct flat antichains with volume V ≤ (K − 1)(K − 1). Note that U_{n} is the first volume that we cannot obtain from only K-sets and (K −1)- sets.

Illustration. Let V_{max}(n) be the maximum possible volume of an antichain on [n]. For n even, V_{max}(n) = K\binom{n}{K} = (K − 1)\binom{n}{K−1}, and for n odd, V_{max}(n) = K\binom{n}{K}.

Let V_{max2}(n) be the second largest volume of an antichain on [n] consisting of only sets of one size. That is, for n even, V_{max2}(n) = (K + 1)\binom{n}{K+1} = (K − 2)\binom{n}{K−2}, and for n odd, V_{max2}(n) = (K + 1)\binom{n}{K+1} = (K − 1)\binom{n}{K−1}. Note that V_{max2}(n) < U_{n} for n ≥ 5.

\begin{matrix}n & 5 & 6 & 7 & 8 \\ U_{n} & 22 & 49 & 117 & 251 \\ V_{max}(n) & 30 & 60 & 140 & 280 \\ V_{max2}(n) & 20 & 30 & 105 & 168 \end{matrix}

We now describe some antichains whose volume is less than U_{n}.

The next lemma is given without a proof:

Lemma 9. For n ≥ 5,

(i) (\binom{n}{K} − \binom{K+2}{2}) K + (K + 2) (K + 1) < U_{n}, (ii) (\binom{n}{K} − \binom{n−K+2}{2}) K + (K + 1) (K − 1) < U_{n}, for n odd, (iii) (\binom{n}{K−1} − \binom{n−K+3}{2}) (K − 1) + (K + 1) (K − 2) < U_{n} for n even.

Recall that the ideal of an antichain A is IA = {B : B ⊆ A, A ∈ A}. We define the ideal at level i, denoted by I_{i}A, to be {B : B ∈ IA, |B| = i}. The filter of A is FA = {B : B ⊇ A, A ∈ A}. The filter at level i is F_{i}A = {B : B ∈ FA, |B| = i}. All antichains are assumed to be squashed. As in the previous section, “first” and “last” refer to first and last in the context of the squashed ordering of sets.

Lemma 10. For n ≥ 5 let A be an antichain with |I_{K+1}A| ≥ K + 1. Then V (A) < U_{n}.

Proof. If V (A) ≤ V_{max2}(n) then V (A) < U_{n} and we are done. If V (A) > V_{max2}(n) then A must contain sets of size less than K + 1. For, if for each A ∈ A, |A| ≥ K + 1, then V (I_{K+1}A) ≥ V (A) by Lemma 2. But V (I_{K+1}A) ≤ V_{max2}(n) < U_{n}, contradicting our assumption about V (A).

Let A′ be the antichain obtained from A by replacing the sets of size greater than K +1 by all the sets in their shadow at level K +1. Then V (A′) ≥ V (A) by Lemma 2. Note that |I_{K+1}A′| = |I_{K+1}A| ≥ K + 1.

Let A′′ be the antichain obtained from A′ by replacing the sets of size less than K by all the sets in their shade at level K. It follows that V (A′′) ≥ V (A′) by Lemma 3.

A′′ has at least (K + 1) (K + 1)-sets. The shadow of the first (K + 1) (K + 1)-sets is equal to the shadow of the first (K + 2) (K + 1)-sets, so that Lemma 4 applies to A′′ and V (A′′) ≤ (\binom{n}{K} − \binom{K+2}{2}) K + (K + 2)(K + 1). By Lemma 9(i), V (A′′) < U_{n}. We conclude that V (A) < U_{n}.

Lemma 11. For n odd and n ≥ 5, let A be an antichain with |F_{K−1}| ≥ K. Then V (A) < U_{n}.

Proof. If V (A) > V_{max2}(n), then, by Lemma 3, A must contain sets of size greater than K − 1. Let A′ be the antichain obtained from A by replacing the sets of size less than K − 1 by all the sets in their shade at level K − 1. Then V (A′) ≥ V (A) by Lemma 3. Note that |F_{K−1}A′| = |F_{K−1}A| ≥ K.

Let A′′ be the antichain obtained from A′ by replacing the sets of size greater than K by all the sets in their shadow at level K. By Lemma 2, V (A′′) ≥ V (A′). A′′ has at least K (K − 1)-sets. The shade of the last K (K − 1)-sets is equal to the shade of the last (K + 1) (K − 1)-sets, so that Lemma 5 applies to A′′ to give V (A′′) ≤ (\binom{n}{K} − \binom{n−K+2}{2}) K + (K + 1)(K − 1). It follows that V (A) < U_{n} by Lemma 9(ii).

Lemma 12. For n even and n ≥ 5 let A be an antichain with |F_{K−2}| ≥ K. Then V (A) < U_{n}.

Proof. The proof is very similar to the proof of Lemma 11. In the latter, replacing K and (K − 1)-sets by (K − 1) and (K − 2)-sets respectively, and using Lemmas 6 and 9(iii) in lieu of Lemmas 5 and 9(ii) achieves the desired result.

Observation 3. If A is an antichain such that |I_{K+1}A| < K + 1 then A contains no set of size larger than (K + 1). If n is odd and |F_{K−1}| < K then A contains no set of size smaller than K − 1. If n is even and |F_{K−2}| < K then A contains no set of size smaller than K − 2.

Lemmas 10, 11 and 12 together with Observation 3 imply that the antichains on [n], n ≥ 5, which are not flat and which have volume V ≥ U_{n} can only be one of the types listed below:

(i) for n odd, the antichains with parameters p_{i} = 0 for i > K + 1 and i < K − 1, 0 < p_{K+1} ≤ K and 0 < p_{K−1} ≤ K − 1 (antichains of type A1); (ii) for n even, the antichains with parameters p_{i} = 0 for i > K + 1 and i < K − 1, 0 < p_{K+1} ≤ K and p_{K−1} ≠ 0 (antichains of type A2); (iii) for n even, the antichains with parameters p_{i} = 0 for i > K and i < K − 2, p_{K} ≠ 0 and 0 < p_{K−2} ≤ K − 1 (antichains of type A3); (ii) for n even, the antichains with parameters p_{i} = 0 for i > K + 1 and i < K − 2, 0 < p_{K+1} ≤ K and 0 < p_{K−2} ≤ K − 1 (antichains of type A4).

In any other case, either n ≤ 4, or, if n ≥ 5, the volume V of the antichain is less than U_{n}, or the given antichain is already flat. Observation 1 together with Lemma 8 show that if A is not an antichain of any of the types described above, then there exists a flat antichain with volume V (A).

We show that antichains of type A1, A2, A3 or A4 can be flattened by keeping the size, as well as the volume, constant.

In all of the following, A is a squashed antichain on [n] with parameters p_{i}, 0 ≤ i ≤ n. As before, we assume that the sets of the smallest size, say l, form a terminal segment of l-sets in squashed order.

Notation. F_{k}(p) denotes the first p k-sets in squashed order and L_{k}(p) denotes the last p k-sets in squashed order.

Observation 4. Let k ∈ Z^{+} be such that 0 < k < n.

(i) For 0 ≤ p < k and 0 ≤ m ≤ p, the size of the new-shadow of the last m k-sets of F_{k}(p) is greater than or equal to 2m. (ii) For 0 ≤ p < n − k and 0 ≤ m ≤ p, the size of the new-shade of the first m k-sets of L_{k}(p) is greater than or equal to 2m.

The next three lemmas conclude the proof of Theorem 1.

Lemma 13. If A is an antichain of type A1 or A2, then there exists a flat antichain of size |A| and volume V (A).

Proof. Let p = min{p_{K+1}, p_{K−1}}. Then p ≤ K. By Observation 4(i), there exists an antichain of size |A| and volume V (A) having parameters q_{i} = 0 for i > K + 1 and i < K − 1, q_{K+1} = p_{K+1} − p, q_{K} = 2p + p_{K}, q_{K−1} = p_{K−1} − p.

Lemma 14. If A is an antichain of type A3, then there exists a flat antichain of size |A| and volume V (A).

Proof. Note that n = 2K − 2 and let p = min{p_{K}, p_{K−2}}. Then p ≤ K − 1 and by Observation 4(ii) there exists an antichain of size |A| and volume V (A) having parameters q_{i} = 0 for i > K and i < K − 2, q_{K} = p_{K} − p, q_{K−1} = 2p + p_{K−1}, q_{K−2} = p_{K−2} − p.

Lemma 15. If A is an antichain of type A4, then there exists a flat antichain of size |A| and volume V (A).

Proof. Note that n = 2K − 2. Three cases are considered. In each case, by Observations 4(i) and (ii), there exists an antichain of size |A| and volume V (A) and having parameters q_{i} as given below:

(i) p_{K+1} = p_{K−2}: q_{i} = 0 for i > K and i < K−1, q_{K} = p_{K+1}+p_{K}, q_{K−1} = p_{K−1}+p_{K−2}.

(ii) p_{K+1} > p_{K−2}: q_{i} = 0 for i > K + 1 and i < K − 1, q_{K+1} = p_{K+1} − p_{K−2}, q_{K} = p_{K} + p_{K−2}, q_{K−1} = p_{K−1} + p_{K−2}. This is an antichain of type A2.

(iii) p_{K+1} < p_{K−2}: q_{i} = 0 for i > K and i < K − 2, q_{K} = p_{K+1} + p_{K}, q_{K−1} = p_{K−1} + p_{K+1}, q_{K−2} = p_{K−2} − p_{K+1}. This is an antichain of type A3.

By Lemmas 13 and 14 the antichains obtained in cases (ii) and (iii) have a flat counterpart with same size |A| and volume V (A).

References

[1] G.F. Clements. More on the Generalised Macauley Theorem - II. Discrete Mathematics, 18:253–264, 1977.

[2] G.F. Clements. The Minimal Number of Basic Elements in a Multiset Antichain. Journal of Combinatorial Theory, Series A, 25:153–162, 1978.

[3] D.E. Daykin, J. Godfrey, and A.J.W. Hilton. Existence Theorems for Sperner Families. Journal of Combinatorial Theory, Series A, 17:245–251, 1974.

[4] G. Katona. A Theorem on Finite Sets. In Theory of Graphs, Proc. Colloq. Tihany, pages 187–207, Ne w York, 1966. Akademiai Kiado, Academic Press.

[5] D.J. Kleitman and E.C. Milner. On the Average Size of the Sets in Sperner Family. Discrete Mathematics, 6:141–147, 1973.

[6] J.B. Kruskal. The Number of Simplices in a Complex. In R. Bellman, editor, Mathematical Optimization Techniques, pages 251–78. University of California Press, Berkeley, 1963.

[7] P. Lieby. The Separation Problem. Honours thesis, Northern Territory University, 1994.

[8] F. Maire. On the Flat Antichain Conjecture. Australasian Journal of Combinatorics, 15:241–245, 1997.

[9] E. Sperner. Ein Satz über Untermengen einer endligen Menge. Math. Z., 27:544– 8, 1928.