%% %% this is a 12 page AMS-LaTeX document %% %% \documentclass[oneside,fleqn,12pt]{article} \usepackage[fleqn]{amsmath} \usepackage{amstext,amsthm} %%%% SETTINGS \setlength{\parindent}{0mm} \setlength{\parskip}{8pt} \setlength{\topmargin}{0mm} \setlength{\baselineskip}{24pt} \setlength{\headheight}{0mm} \setlength{\headsep}{10mm} \setlength{\textheight}{229mm} \setlength{\marginparwidth}{1in} \setlength{\oddsidemargin}{8mm} \setlength{\evensidemargin}{0mm} \setlength{\textwidth}{152mm} %%%%%% HANDY THINGS \newcommand{\room}{\hspace*{\fill}\newline} \newcommand{\reminder}[1]{\footnote{{#1}}} \newcommand{\comment}[1]{} %%%%%% ENVIRONMENTS \theoremstyle{plain} \newtheorem{theorem}{Theorem}%[section] \newtheorem{lemma}{Lemma}%[section] \newtheorem{proposition}{Proposition}%[section] \newtheorem{corollary}{Corollary}%[section] \newtheorem{claim}{Claim}%[section] \newtheorem*{conjecture}{Conjecture} \theoremstyle{definition} \newtheorem{definition}{Definition}%[section] \newtheorem{example}{Example}%[section] \newtheorem*{notation}{Notation} \newtheorem{problem}{Problem}%[section] \newtheorem{observation}{Observation}%[section] \theoremstyle{remark} \newtheorem{remark}{Remark}%[section] \newtheorem{note}{Note}%[section] \newtheorem*{case}{Case} %\numberwithin{equation}{section} %%%%%% SYMBOLS \def\shadow{\triangle} \def\shade{\protect{\raisebox{.5ex}{$\bigtriangledown$}}} \def\biga{{\cal A}} \def\bigb{{\cal B}} \def\bigc{{\cal C}} \def\bigd{{\cal D}} \def\bige{{\cal E}} \def\bigf{{\cal F}} \def\bigg{{\cal G}} \def\bigi{{\cal I}} \def\bigll{{\cal L}} \def\bigm{{\cal M}} \def\bign{{\cal N}} \def\bigo{{\cal O}} \def\bigp{{\cal P}} \def\bigq{{\cal Q}} \def\bigrr{{\cal R}} \def\bigs{{\cal S}} \def\bigt{{\cal T}} \def\bigu{{\cal U}} \def\bigx{{\cal X}} \def\bigy{{\cal Y}} \def\bigz{{\cal Z}} \def\astar{{\cal A}^{\ast}} \def\bstar{{\cal B}^{\ast}} \def\cstar{{\cal C}^{\ast}} \def\gstar{{\cal G}^{\ast}} \def\acirc{{\cal A}^\circ} %% BEGIN DOCUMENT %% \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 6 (1999), \#R1\hfill} \thispagestyle{empty} \begin{center} \LARGE{\bf Flattening Antichains with Respect to the Volume} \normalsize \vspace{1cm} {\large Ljiljana Brankovic}\\ %\scriptsize \vspace{0mm} Department of Computer Science and Software Engineering\\ %\scriptsize \vspace{0mm} The University of Newcastle NSW 2308 Australia\\ %\scriptsize \vspace{0mm} {\bf e-mail}: {\tt lbrankov@cs.newcastle.edu.au} \normalsize \vspace{.5cm} {\large Paulette Lieby}\\ %\scriptsize \vspace{0mm} School of Mathematical and Physical Sciences\\ %\scriptsize \vspace{0mm} Northern Territory University, Darwin, NT Australia\\ %\scriptsize \vspace{0mm} {\bf e-mail}: {\tt paule@it.ntu.edu.au} \normalsize \vspace{.5cm} {\large Mirka Miller}\\ %\scriptsize \vspace{0mm} Department of Computer Science and Software Engineering\\ %\scriptsize \vspace{0mm} The University of Newcastle NSW 2308 Australia\\ %\scriptsize \vspace{0mm} {\bf e-mail}: {\tt mirka@cs.newcastle.edu.au} \vspace{.5cm} Submitted: September 10, 1998; Accepted: November 9, 1998. AMS Subject Classification: 05D99. \end{center} \vspace{1cm} \begin{abstract} We say that an antichain $\biga$ in the boolean lattice $B_n$ is flat if there exists an integer $k\geq 0$ such that every set in $\biga$ has cardinality either $k$ or $k+1$. Define the volume of $\biga$ to be $\sum_{A\in\biga}|A|$. We prove that for every antichain $\biga$ in $B_n$ there exist an antichain which is flat and has the same volume as $\biga$. \end{abstract} \newpage \section{Introduction} Throughout the paper the universal set is $[n]=\{1,2,\ldots\,n\}$. A collection $\biga$ of subsets of $[n]$ is an {\bf antichain} if for any distinct $A$, $B\in\biga$, $A\not\subseteq B$. The {\bf parameters} of an antichain $\biga$ are the non-negative integers $p_i$, $0 \leq i \leq n$, such that $p_i = |\biga_i|$ where $\biga_i = \{A:|A|=i, A\in\biga\}$. Let $\biga$ be an antichain. We say that $\biga$ is {\bf flat} if, for any $A\in\biga$, $|A|=k$ or $|A|=k+1$, for some non-negative integer $k$. Thus the parameters of $\biga$ are such that %$\exists k$ with $p_k$, $p_{k+1}\neq 0$ % and $p_i=0$ for $i\neq k$, $k+1$. The {\bf size} of $\biga$ is $|\biga|$ and its {\bf volume} is $V(\biga)=\sum_{A\in\biga}|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 $\biga$ is an antichain of size $s$, then there exists an antichain consisting of $s$ $\left\lfloor\frac{n}{2}\right\rfloor$-sets. A result by Kleitman and Milner\cite{kleitman1}, Clements\cite{clements8}, and more recently by Maire\cite{maire}, shows that, if $\biga$ is an antichain whose average set size is an integer, then there exists a flat antichain having the same size and volume as $\biga$. The {\bf ideal} of a collection of sets $\bigb$ is $\bigi \bigb= \{C: C \subseteq B, B\in\bigb\}$. Clements\cite{clements8} proved that, given $s$, an antichain $\biga$ of size $s$ which achieves minimum (or maximum) volume and minimum (or maximum) ideal is flat. Lieby\cite{liebya} conjectured that, if $\biga$ 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\cite{kleitman1} 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 $\biga$ there exists a flat antichain with same volume as $\biga$. Our main result is: \begin{theorem} \label{th:flatvol} If $\biga$ is an antichain then there exists a flat antichain with volume $V(\biga)$. \end{theorem} The next section, Section~\ref{sec:back}, provides the necessary background material; Section~\ref{sec:prelim} establishes preliminary results needed in the proof of Theorem~\ref{th:flatvol} which is presented in Section~\ref{sec:theproof}. \section{Background} \label{sec:back} If $\bigb$ is a collection of $k$-sets, $0 < k \leq n$, the {\bfseries shadow} of $\bigb$ is $ \shadow \bigb = \{C: |C| = k-1, C \subset B, B \in \bigb\}. $ Similarly, the {\bfseries shade} of $\bigb$ is $ \shade \bigb = \{C: |C| = k+1, B \subset C, B \in \bigb\}. $ Sperner's lemma gives a relationship between the size of a collection of sets and the sizes of its shadow and shade: \begin{lemma}[Sperner\cite{sperner}] \label{lem:Sperner} Let $\bigb$ be a collection of $k$-subsets of $[n]$. Then \[ |\shadow \bigb| \geq \frac{k}{n-k+1} |\bigb| \quad\quad \text{ if } k > 0 \] and \[ |\shade \bigb| \geq \frac{n-k}{k+1} |\bigb| \quad\quad\quad\quad \text{ if } k < n. \] \end{lemma} An order relation on sets, the {\bfseries squashed order}, denoted by { $\leq_S$}, is defined: If $A$ and $B$ are any sets, then $A \leq_S B$ if the largest element of $A+B$ is in $B$, where $A + B$ denotes the symmetric difference of $A$ and $B$. A {\bfseries squashed antichain} $\biga$ is an antichain such that for each $i$, the sets in $\biga$ of size $i$, together with the sets of size $i$ contained in all the larger members of $\biga$, constitute an initial segment of the sets of size $i$ in squashed order. Kruskal\cite{kruskal} and Katona\cite{katona} showed that the shadow of a collection of $k$-sets $\bigb$ is minimised when $\bigb$ is an initial segment of the $k$-sets in squashed order. One important consequence of this result is \begin{theorem}[Clements\cite{clements5}, Daykin\cite{daykin1}] \label{th:nec&suf} There exists an antichain with $p_i$ $i$-sets if and only if there exists a squashed antichain with $p_i$ $i$-sets, $0\leq i \leq n$. \end{theorem} If $\bigb$ is any collection of consecutive $k$-sets in squashed order, then the {\bf new-shadow} of $\bigb$, denoted by $\shadow_N\bigb$, is the collection of the $(k-1)$-sets that belong to the shadow of $\bigb$ but {\em not} to the shadow of any $k$-set that comes before any set of $\bigb$ in the squashed ordering of sets. That is, the new-shadow of $\bigb$ is the contribution of the sets in $\bigb$ to the shadow of the first $p$ $k$-sets in squashed order, where $p$ is such that the $p$th set in squashed order is the last set in $\bigb$. The {\bf new-shade} of $\bigb$, denoted by $\shade_N\bigb$, is defined in a similar way. It consists of the $(k+1)$-sets that are in the shade of $\bigb$ but not in the shade of any $k$-set that comes after any set of $\bigb$ in the squashed ordering of sets. Formally, if $\bigb$ is a collection of consecutive $k$-sets in squashed order, then the {new-shadow} of $\bigb$ is $ \shadow_N \bigb = \{ D: D \in\shadow \bigb \text{ and } D \not\in \shadow C \text{ for all } C \leq_S B, C \not\in \bigb, B\in\bigb \}. $ The {new-shade} of $\bigb$ is $ \shade_N \bigb = \{ D: D \in\shade \bigb \text{ and } D \not\in \shade C \text{ for all } C, B \leq_S C, C \not\in \bigb, B \in \bigb\}. $ \begin{note} By Theorem~\ref{th:nec&suf} we only need to consider squashed antichains, so that throughout the rest of this paper only squashed antichains will be considered. \end{note} \begin{notation} We set $K=\frac{n}{2} + 1$ for $n$ even and $K=\frac{n+1}{2}$ for $n$ odd. \end{notation} \section{Preliminary Results} \label{sec:prelim} This section presents the technical results needed in the proof of Theorem~\ref{th:flatvol}. Lemma~\ref{lem:volsdo} 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~\ref{lem:volsde} establishes a similar relationship with the volume of its shade. \begin{lemma} \label{lem:volsdo} Let $\bigb$ be a collection of $l$-sets. If $l>K$ for $n$ odd or $l \geq K$ for $n$ even then $V(\shadow\bigb)\geq V(\bigb)$. \end{lemma} \begin{proof} By Sperner's lemma $|\shadow\bigb| \geq \frac{l}{n-l+1}|\bigb|$ so that \[ V(\shadow\bigb) \geq (l-1)\frac{l}{n-l+1}|\bigb| \geq l |\bigb| = V(\bigb) \] for $\frac{l-1}{n-l+1} \geq 1$, that is for $l\geq \frac{n+2}{2}$. \end{proof} \begin{lemma} \label{lem:volsde} Let $\bigb$ be a collection of $l$-sets. If $l < K$ then $V(\shade\bigb)\geq V(\bigb)$. \end{lemma} \begin{proof} By Sperner's lemma $|\shade\bigb| \geq \frac{n-l}{l+1}|\bigb|$ so that \[ V(\shade\bigb) \geq (l+1)\frac{n-l}{l+1}|\bigb| \geq l |\bigb| = V(\bigb) \] for $n-l \geq l$, that is for $l \leq \frac{n}{2}$. \end{proof} The next three lemmas give an upper bound for $V(\biga)$ where $\biga$ is an antichain satisfying certain conditions. In particular, Lemma~\ref{lem:maxvol(K+1)&(K)} says that if $\biga$ is an antichain whose largest set has size $K+1$ and having parameter $p_{K+1} > K+2$, then $V(\biga)$ is bounded above by the volume of the antichain $\astar$ obtained from $\biga$ by replacing $(K+1)$-sets by $K$-sets so that $\astar$ has exactly $(K+2)$ $(K+1)$-sets. Lemma~\ref{lem:odd,maxvol(K-1)&(K)} says that, for $n$ odd, if $\biga$ is an antichain whose smallest set has size $K-1$ and having parameter $p_{K-1} > K+1$, then $V(\biga)$ is bounded above by the volume of the antichain $\astar$ obtained from $\biga$ by replacing $(K-1)$-sets by $K$-sets so that $\astar$ has exactly $(K+1)$ $(K-1)$-sets. Lemma~\ref{lem:even,maxvol(K-2)&(K-1)} says that, for $n$ even, if $\biga$ is an antichain whose smallest set has size $K-2$ and having parameter $p_{K-2} > K+1$, then $V(\biga)$ is bounded above by the volume of the antichain $\astar$ obtained from $\biga$ by replacing $(K-2)$-sets by $(K-1)$-sets so that $\astar$ 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. \begin{lemma} \label{lem:maxvol(K+1)&(K)} For $n\geq 5$ let $\biga$ be an antichain with parameters $p_i$ such that $p_i=0$ for $i> K+1$, and $p_{K+1} > K+2$. Let $\astar$ be the antichain obtained from $\biga$ by replacing all the $(K+1)$-sets of $\biga$ but the first $(K+2)$ $(K+1)$-sets by all the $K$-sets in their new-shadow. Then $V(\astar) \geq V(\biga)$. \end{lemma} \begin{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,\ldots,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 \leq i \leq 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 $\biga$ be as defined in the statement of the lemma and consider $\biga_{K+1}$, the subcollection of $\biga$ consisting of its $(K+1)$-sets. By the introductory remark, $\biga_{K+1}$ is the union of consecutive collections $\biga^i$ of consecutive $(K+1)$-sets in squashed order where for some $I$, $K \leq I \leq n-1$, $|\biga^i| = \binom{i}{K}$ for $K \leq i < I$, $|\biga^i| \leq \binom{i}{K}$ for $i=I$, and $|\biga^i| = 0$ for $i>I$. Let $i$ be given, $K \leq i \leq I$. We have seen that any $(K+1)$-set of $\biga^i$ is the union of one of the $\binom{i}{K}$ $K$-subsets of $[i]$ sets and $\{i+1\}$. Therefore the sets in $\shadow_N \biga^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$, {\em must} be in the shadow of some set which precedes the sets in $\biga^i$ in squashed order. Let $\bigb^i = \{B:|B|=K, B\subset A, A\in\biga^i, i+1\notin B\}$. Note that \\ (i) $|\bigb^i| = |\biga^i| \leq \binom{i}{K}$. \\ (ii) The sets in $\bigb^i$ constitute an initial segment of $K$-subsets of $[i]$ in squashed order, so that $|\shadow_N\biga^i|=|\shadow\bigb^i|$ for $K < i \leq I$. By Sperner's lemma we have \[ \left|\shadow\bigb^i\right|\geq \frac{K}{i-K+1}\left|\bigb^i\right|. \] From (i) and (ii) it follows that \[ V\left(\shadow_N\biga^i\right) = K|\shadow_N\biga^i| \geq K \frac{K}{i-K+1}\left|\biga^i\right| \geq \left(K+1\right)\left|\biga^i\right| = V\left(\biga^i\right) \] for $K < i \leq I \leq n-1$. Also, \[ \left|\shadow_N\left( \biga_{K+1}\setminus\left( \biga^K\cup\biga^{K+1}\right)\right)\right| = \sum_{i=K+2}^{I}\left|\shadow_N \biga^i\right| \] so that \begin{align*} V\left( \shadow_N\left(\biga_{K+1}\setminus\left( \biga^K\cup\biga^{K+1}\right)\right) \right) & = \sum_{i=K+2}^{I}V\left(\shadow_N \biga^i\right) \\ & \geq \sum_{i=K+2}^{I} V\left(\biga^i\right) \\ & = V\left(\biga_{K+1}\setminus\left( \biga^K\cup\biga^{K+1}\right)\right). \end{align*} $\astar$ is the antichain obtained from $\biga$ by replacing all the $(K+1)$-sets in $\biga^i$, $K+2 \leq i \leq I$, by all the $K$-sets in $\shadow_N\biga^i$. Note that $|\biga^K\cup\biga^{K+1}| = K+2$. This implies \begin{align*} V\left(\astar\right) & = V\left(\biga\right) - V\left(\biga_{K+1}\setminus\left( \biga^K\cup\biga^{K+1}\right)\right) \\ & \mspace{50mu} + V\left( \shadow_N\left(\biga_{K+1}\setminus\left( \biga^K\cup\biga^{K+1}\right)\right) \right) \\ & \geq V\left(\biga\right). \end{align*} This proves the lemma. \end{proof} We now need to establish a similar result to the one stated in the previous lemma in the case where $\astar$ is obtained from $\biga$ by replacing sets of $\biga$ by sets in their new-shade. The proofs of the following lemmas are similar to the proof of Lemma~\ref{lem:maxvol(K+1)&(K)} 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. \begin{lemma} \label{lem:odd,maxvol(K-1)&(K)} For $n$ odd and $n\geq 5$ let $\biga$ be an antichain with parameters $p_i$ such that $p_i=0$ for $i< K-1$ and $p_{K-1} > K+1$. Let $\astar$ be the antichain obtained from $\biga$ 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(\astar) \geq V(\biga)$. \end{lemma} \begin{proof} Let $\biga$ be as defined in the statement of the lemma and consider $\biga_{K-1}$, the subcollection of $\biga$ consisting of its $(K-1)$-sets. Then $\biga_{K-1}$ is the union of consecutive collections $\biga^i$ of consecutive $(K-1)$-sets in reverse squashed order where for some $I$, $K-1 \leq I \leq n-1$, $|\biga^i| = \binom{i}{i-K+1}$ for $K-1 \leq i < I$, $|\biga^i| \leq \binom{i}{i-K+1}$ for $i=I$, and $|\biga^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,\ldots,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,\ldots,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,\ldots,n\}$. In general, for $K-1 \leq i \leq I$, any $(K-1)$-set of $\biga^i$ is the union of one of the $\binom{i}{i-K+1}$ $(i-K+1)$-subsets of $[i]$ and $\{i+2,\ldots,n\}$, so that the sets in $\shade_N \biga^i$ are the union of one of the $\binom{i}{i-K+2}$ $(i-K+2)$-subsets of $[i]$ and $\{i+2,\ldots,n\}$. Let $\bigb^i = \{B:|B|=i-K+1, B\subset A, A\in\biga^i, B\cap\{i+2,\ldots,n\}=\emptyset\}$. Note that \\ (i) $|\bigb^i| = |\biga^i| \leq \binom{i}{i-K+1}$. \\ (ii) The sets in $\bigb^i$ constitute a terminal segment of $(i-K+1)$-subsets of $[i]$ in squashed order, so that $|\shade_N\biga^i|=|\shade\bigb^i|$. By Sperner's lemma we have \[ \left|\shade\bigb^i\right|\geq \frac{K-1}{i-K+2}\left|\bigb^i\right|. \] From (i) and (ii) it follows that \[ V\left(\shade_N\biga^i\right) = K|\shade_N\biga^i| \geq K \frac{K-1}{i-K+2}\left|\biga^i\right| \geq \left(K-1\right)\left|\biga^i\right| = V\left(\biga^i\right) \] for $K-1 \leq i \leq I \leq n-1$. Also, \[ \left|\shade_N\left( \biga_{K-1}\setminus\left( \biga^{K-1}\cup\biga^K\right)\right)\right| = \sum_{i=K+1}^{I}\left|\shade_N \biga^i\right| \] so that \begin{align*} V\left( \shade_N\left(\biga_{K-1}\setminus\left( \biga^{K-1}\cup\biga^K\right)\right) \right) & = \sum_{i=K+1}^{I}V\left(\shade_N \biga^i\right) \\ & \geq \sum_{i=K+1}^{I} V\left(\biga^i\right) \\ & = V\left(\biga_{K-1}\setminus\left( \biga^{K-1}\cup\biga^K\right)\right). \end{align*} \end{proof} \begin{lemma} \label{lem:even,maxvol(K-2)&(K-1)} For $n$ even and $n\geq 5$ let $\biga$ be an antichain with parameters $p_i$ such that $p_i=0$ for $i< K-2$ and $p_{K-2} > K+1$. Let $\astar$ be the antichain obtained from $\biga$ 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(\astar) \geq V(\biga)$. \end{lemma} \begin{proof} Let $\biga$ be as defined in the statement of the lemma and consider $\biga_{K-2}$, the subcollection of $\biga$ consisting of its $(K-2)$-sets. Then $\biga_{K-2}$ is the union of consecutive collections $\biga^i$ of consecutive $(K-2)$-sets in reverse squashed order where for some $I$, $K-1 \leq I \leq n-1$, $|\biga^i| = \binom{i}{i-K+1}$ for $K-1 \leq i < I$, $|\biga^i| \leq \binom{i}{i-K+1}$ for $i=I$, and $|\biga^i| = 0$ for $i>I$. The same argument as the one used in the proof of Lemma~\ref{lem:odd,maxvol(K-1)&(K)} shows that \[ V\left( \shade_N\left(\biga_{K-2}\setminus\left( \biga^{K-1}\cup\biga^K\right)\right) \right) \geq V\left(\biga_{K-2}\setminus\left( \biga^{K-1}\cup\biga^K\right)\right). \] \end{proof} \section{Proof of Theorem~\ref{th:flatvol}} \label{sec:theproof} To prove Theorem~\ref{th:flatvol} 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~\ref{sec:prelim}, 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 of Theorem~\ref{th:flatvol} 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 V_{max2}(n)$ then $\biga$ must contain sets of size less than $K+1$. For, if for each $A\in\biga$, $|A| \geq K+1$, then $V(\bigi_{K+1}\biga) \geq V(\biga)$ by Lemma~\ref{lem:volsdo}. But $V(\bigi_{K+1}\biga) \leq V_{max2}(n) < U_n$, contradicting our assumption about $V(\biga)$. Let $\biga^\prime$ be the antichain obtained from $\biga$ by replacing the sets of size greater than $K+1$ by all the sets in their shadow at level $K+1$. Then $V(\biga^\prime) \geq V(\biga)$ by Lemma~\ref{lem:volsdo}. Note that $|\bigi_{K+1}\biga^\prime| = |\bigi_{K+1}\biga| \geq K+1$. Let $\biga^{\prime\prime}$ be the antichain obtained from $\biga^\prime$ by replacing the sets of size less than $K$ by all the sets in their shade at level $K$. It follows that $V(\biga^{\prime\prime})\geq V(\biga^\prime)$ by Lemma~\ref{lem:volsde}. $\biga^{\prime\prime}$ 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~\ref{lem:maxvol(K+1)&(K)} applies to $\biga^{\prime\prime}$ and $V(\biga^{\prime\prime}) \leq \left(\binom{n}{K} - \binom{K+2}{2}\right)K + (K+2)(K+1)$. By Lemma~\ref{lem:ineq}(i), $V(\biga^{\prime\prime}) < U_n$. We conclude that $V(\biga) < U_n$. \end{proof} \begin{lemma} \label{lem:odd,(K-1)} For $n$ odd and $n\geq 5$, let $\biga$ be an antichain with $|\bigf_{K-1}| \geq K$. Then $V(\biga) < U_n$. \end{lemma} \begin{proof} If $V(\biga) > V_{max2}(n)$, then, by Lemma~\ref{lem:volsde}, $\biga$ must contain sets of size greater than $K-1$. Let $\biga^\prime$ be the antichain obtained from $\biga$ by replacing the sets of size less than $K-1$ by all the sets in their shade at level $K-1$. Then $V(\biga^\prime) \geq V(\biga)$ by Lemma~\ref{lem:volsde}. Note that $|\bigf_{K-1}\biga^\prime| = |\bigf_{K-1}\biga| \geq K$. Let $\biga^{\prime\prime}$ be the antichain obtained from $\biga^\prime$ by replacing the sets of size greater than $K$ by all the sets in their shadow at level $K$. By Lemma~\ref{lem:volsdo}, $V(\biga^{\prime\prime})\geq V(\biga^\prime )$. $\biga^{\prime\prime}$ 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~\ref{lem:odd,maxvol(K-1)&(K)} applies to $\biga^{\prime\prime}$ to give $V(\biga^{\prime\prime}) \leq \left(\binom{n}{K} - \binom{n-K+2}{2}\right)K + (K+1)(K-1)$. It follows that $V(\biga) < U_n$ by Lemma~\ref{lem:ineq}(ii). \end{proof} \begin{lemma} \label{lem:even,(K-2)} For $n$ even and $n\geq 5$ let $\biga$ be an antichain with $|\bigf_{K-2}| \geq K$. Then $V(\biga) < U_n$. \end{lemma} \begin{proof} The proof is very similar to the proof of Lemma~\ref{lem:odd,(K-1)}. In the latter, replacing $K$ and $(K-1)$-sets by $(K-1)$ and $(K-2)$-sets respectively, and using Lemmas~\ref{lem:even,maxvol(K-2)&(K-1)} and \ref{lem:ineq}(iii) in lieu of Lemmas~\ref{lem:odd,maxvol(K-1)&(K)} and \ref{lem:ineq}(ii) achieves the desired result. \end{proof} \begin{observation} \label{obs:charac} If $\biga$ is an antichain such that $|\bigi_{K+1}\biga| < K+1$ then $\biga$ contains no set of size larger than $(K+1)$. If $n$ is odd and $|\bigf_{K-1}| < K$ then $\biga$ contains no set of size smaller than $K-1$. If $n$ is even and $|\bigf_{K-2}| < K$ then $\biga$ contains no set of size smaller than $K-2$. \end{observation} Lemmas~\ref{lem:(K+1)}, \ref{lem:odd,(K-1)} and \ref{lem:even,(K-2)} together with Observation~\ref{obs:charac} imply that the antichains on $[n]$, $n\geq 5$, which are not flat and which have volume $V \geq 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} \leq K$ and $0 < p_{K-1} \leq 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} \leq K$ and $p_{K-1} \neq 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} \neq 0$ and $0< p_{K-2} \leq 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} \leq K$ and $0< p_{K-2} \leq K-1$ (antichains of type A4). \\ In any other case, either $n\leq 4$, or, if $n\geq 5$, the volume $V$ of the antichain is less than $U_n$, or the given antichain is already flat. Observation~\ref{obs:flatvol01} together with Lemma~\ref{lem:Un} show that if $\biga$ is not an antichain of any of the types described above, then there exists a flat antichain with volume $V(\biga)$. 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, $\biga$ is a squashed antichain on $[n]$ with parameters $p_i$, $0 \leq i \leq n$. As before, we assume that the sets of the smallest size, say $l$, form a terminal segment of $l$-sets in squashed order. \begin{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. \end{notation} \begin{observation} \ \\ \label{obs:sizes} Let $k\in\boldsymbol{Z^+}$ be such that $0 < k < n$.\\ (i) For $0 \leq p < k$ and $0\leq m \leq 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 \leq p < n-k$ and $0\leq m \leq p$, the size of the new-shade of the first $m$ $k$-sets of $L_k(p)$ is greater than or equal to $2m$. \\ \end{observation} The next three lemmas conclude the proof of Theorem~\ref{th:flatvol}. \begin{lemma} \label{lem:typeA1&A2} If $\biga$ is an antichain of type A1 or A2, then there exists a flat antichain of size $|\biga|$ and volume $V(\biga)$. \end{lemma} \begin{proof} Let $p = \text{min}\{p_{K+1},p_{K-1}\}$. Then $p \leq K$. By Observation~\ref{obs:sizes}(i), there exists an antichain of size $|\biga|$ and volume $V(\biga)$ having parameters $q_i=0$ for $i>K+1$ and $iK$ and $iK$ and $i p_{K-2}$: $q_i=0$ for $i>K+1$ and $iK$ and $i