\begin{document}

\title{Exact forbidden subposet results using chain decompositions of the cycle}

\begin{abstract}
We introduce a method of decomposing the family of intervals along a cyclic permutation into chains to determine the size of the largest family of subsets of $[n]$ not containing one or more given posets as a subposet.   De Bonis, Katona and Swanepoel determined the size of the largest butterfly-free family. We strengthen this result by showing that, for certain posets containing the butterfly poset as a subposet, the same bound holds. We also obtain the corresponding LYM-type inequalities.

\end{abstract}

\mathcal{S}ection{Introduction}
Let $[n] = \{1,2,\dots,n\}$ and $2^{[n]}$ be the power set of $[n]$.  Let $\binom{[n]}{r}$ denote the collection of all $r$-element subsets of $[n]$.    The sum of the $k$ largest binomial coefficients of the form $\binom{n}{i}$ is denoted by $\Sigma(n,k)$. A collection of sets, $\mathcal{A} \mathcal{S}ubset 2^{[n]}$, may be viewed as a partially ordered set (poset) with respect to inclusion.

Given two posets, $P$ and $Q$, we say that $P$ is a (weak) subposet of $Q$ if there is an injection, $\mathcal{P}hi$, from $P$ to $Q$ such that $x \le y$ in $P$ implies $\mathcal{P}hi(x) \le \mathcal{P}hi(y)$ in $Q$.  If we also have that $\mathcal{P}hi(x) \le \mathcal{P}hi(y)$ implies $x \le y$, then $P$ is called an induced subposet of $Q$. 

For a collection of posets, $\mathcal{P}$, Katona and Tarjan \cite{katona1983extremal} introduced the function $\La(n,\mathcal{P})$, defined as the size of the largest collection $\mathcal{A} \mathcal{S}ubset 2^{[n]}$ not containing any poset $P \in \mathcal{P}$ as a subposet. Analogously, $\La^{\#}(n,\mathcal{P})$ denotes the size of the largest family $\mathcal{A} \mathcal{S}ubset 2^{[n]}$ not containing any poset $P \in \mathcal{P}$ as an induced subposet.  In the case that $\mathcal{P}$ contains just one poset, $P$, or two posets, $P$ and $Q$, we simply write $\La(n,P)$ or $\La(n,P,Q)$ instead of $\La(n,\mathcal{P})$.  Problems of this type are motivated by the famous theorem of Sperner \cite{sperner1928satz}:

\begin{theorem}
Let $\mathcal{A} \mathcal{S}ubset 2^{[n]}$ be an antichain, then 
\begin{displaymath}
\abs{\mathcal{A}} \le \binom{n}{\floor{n/2}}.
\end{displaymath}
Moreover, equality is attained if and only if $\mathcal{A}$ consists of a full level of size $\floor{n/2}$ or $\ceil{n/2}$.
\end{theorem}

Erd\H{o}s \cite{erdos1945lemma} extended this theorem by showing that if a family, $\mathcal{A}$, contains no chain of length $k+1$, then $\abs{\mathcal{A}} \le \Sigma(n,k)$.  If we define the $k+1$-path poset $P_{k+1}$ by $k+1$ elements $x_1,x_2,\dots,x_{k+1}$ with the relations $x_1 \le x_2 \le \dots \le x_{k+1}$,  then in our language, Erd\H{o}s's result states that $\La(n,P_{k+1}) = \Sigma(n,k)$.   For a variety of posets, $P$, the value of $\La(n,P)$ has been determined asymptotically. These include the $r$-fork $V_r$ \cite{de2007largest}, all crowns $O_{2k}$ except for $k \in \{3,5\}$ \cite{lu2014crown}, the $N$ poset \cite{griggs2008no} and many others.  An important asymptotic result is a theorem of Bukh \cite{bukh2009set} which yields the asymptotic bound for any tree, $\La(n,T)= (h(T)-1)\binom{n}{\floor{n/2}}(1+ O(1/n))$ where $h(T)$ is the height of the tree. This result was extended to induced trees by Boehnlein and Jiang \cite{boehnlein2012set}.  A central open problem is to determine the asymptotic value of the diamond poset (see, for example \cite{axenovich2012q,kramer2013diamond,manske2013three}).   

Fewer exact results are known.   Already, in their paper introducing the $\La$ function, Katona and Tarjan \cite{katona1983extremal} proved that $\La(n,V,\Lambda) = \La^{\#}(n,V,\Lambda) =  2 \binom{n-1}{\floor{\frac{n-1}{2}}}$, where $V$ and $\Lambda$ are the $2$-fork and $2$-brush, respectively.  Define the butterfly poset, $B$, by $4$ elements $a,b,c,d$ with $a,b \le c,d$. Of central importance to the present paper is a theorem of De Bonis, Katona and Swanepoel \cite{de2005largest} showing that $\La(n,B) = \Sigma(n,2)$.  More recently, several other exact results have been obtained. Burcsi and Nagy \cite{burcsi2013method} obtained the exact bound for multiple posets and introduced a method of creating further posets whose $\La$ function could be calculated exactly. Griggs, Li and Lu \cite{griggs2012diamond}  determined exact results for the $k$-diamond, $D_k$ ($w \le x_1,x_2,\dots,x_k \le z$), for an infinite set of values of $k$.  They also obtained exact results for harp posets, $H(l_1,l_2,\dots,l_k)$, defined by $k$ chains of length $l_i$ between two fixed elements, in the case when the $l_i$ are all distinct.  

Our first new result is a strengthening of the theorem of De Bonis, Katona and Swanepoel on the butterfly poset.  Namely,  we introduce a poset $S$ which contains the butterfly as a strict subposet and prove that, nonetheless, the same bound holds.  This poset, which we call the ``skew''-butterfly, is defined by $5$ elements, $a,b,c,d,e,$ with $a,b \le c,d$ and $b \le e \le d$ (see Figure \ref{skewpic}). 

\begin{figure}
\caption{The skew-butterfly poset}
\label{skewpic}
\label{figure 0}
\end{figure}

\begin{theorem}
\label{skew}
Let $n \ge 3$, then we have
\begin{displaymath}
\La(n,S) = \Sigma(n,2).
\end{displaymath}
\end{theorem}
A construction matching this bound is given by taking two consecutive middle levels of $2^{[n]}$.   With this result (and all of the others) we also get the corresponding LYM-type inequality if we assume $\varnothing$ and $[n]$ are not in the family.

\begin{theorem}
\label{skewbutterfly}
Let $n \ge 3$ and $\mathcal{A} \mathcal{S}ubset 2^{[n]}$  be a collection of sets not containing $S$ as a subposet, and assume that $\varnothing,[n] \notin \mathcal{A}$, then
\begin{displaymath}
\mathcal{S}um_{A\in \mathcal{A}} \frac{1}{\binom{n}{\abs{A}}} \le 2.
\end{displaymath}
\end{theorem}
For the proof of Theorem \ref{skewbutterfly}, we consider the set of intervals along a cyclic permutation (following Katona \cite{katona1972simple}).  We partition these intervals into chains and consider the interactions of consecutive chains in the partition.   The method and the proof of this result are given in Section $2$.

We now mention some notable properties of $S$.  It is one of the two posets whose Hasse diagram is a $5$-cycle.  The other is the harp, $H(4,3)$, and $\La(n,H(4,3))$ was determined exactly in the paper of Griggs, Li and Lu \cite{griggs2012diamond}(the $4$-cycles are $B$ and $D_2$).  The skew-butterfly is contained in the $X$ ($a,b \le c \le d,e$), a tree of height $3$, like $B$, and so its asymptotics are determined by Bukh's theorem.  The exact value of $\La(n,S)$ cannot be determined by the double chain method of Burcsi and Nagy \cite{burcsi2013method} because one can find $5$ sets on a double chain with no copy of $S$.   Finally, if we subdivide any of the edges $ac, ad$ or $bc$ in the Hasse diagram of $S$, we get a poset for which there is a construction of size larger than $\Sigma(n,2)$.

Next, we consider a generalization of De Bonis, Katona and Swanepoel's theorem in a different direction.  If instead of forbidding $B$, we forbid the pair of posets $Y$ and $Y'$ where $Y$ is the poset on $4$ elements $w,x,y,z$ with $w \le x \le y,z$ and $Y'$ is the same poset but with all relations reversed, then $\La(n,Y,Y') = \La(n,B) = \Sigma(n,2)$.  This result is already implicit in the proof of De Bonis, Katona and Swanepoel.  We extend the result by considering the posets $Y_k$ and $Y_k'$ defined by $k+2$ elements $x_1,x_2,\dots,x_{k},y,z$ with $x_1 \le x_2 \le \dots \le x_k \le y,z$ and its reverse (so $Y=Y_2$ and $V=Y_1$).  We prove

\begin{theorem}
\label{Yk}
Let $k \ge 2$ and $n \ge k+1$, then
\begin{displaymath}
\La(n,Y_k,Y_k') = \Sigma(n,k).
\end{displaymath}
\end{theorem}
A construction matching this bound is given by taking $k$ consecutive middle levels of $2^{[n]}$. We also have the LYM-type inequality:

\begin{theorem}
\label{YkLYM}
Let $k \ge 2$ and $n \ge k+1$.  Assume that $\mathcal{A} \mathcal{S}ubset 2^{[n]}$ contains neither $Y_k$ nor $Y_k'$ as a subposet, and $\varnothing,[n] \notin \mathcal{A}$, then
\begin{displaymath}
\mathcal{S}um_{A\in \mathcal{A}} \frac{1}{\binom{n}{\abs{A}}} \le k.
\end{displaymath}
\end{theorem}

We note that, again, the double chain method does not work for these pairs because one can have $2k+1$ sets on a double chain with no $Y_k$ and no $Y_k'$ by taking them consecutively on the secondary chain.  We also note that, for this particular result, we can find another proof using the chain partitioning method of Griggs, Li and Lu \cite{griggs2012diamond} in addition to the approach described in this paper.  

Finally, we consider the more difficult induced case.  We prove

\begin{theorem}
\label{induced}
For $n \ge 3$, we have
\begin{displaymath}
\La^{\#}(n,Y,Y') = \Sigma(2,n). 
\end{displaymath}
\end{theorem}

We also have the LYM-type inequality:

\begin{theorem}
\label{inducedLYM}
Assume that $\mathcal{A} \mathcal{S}ubset 2^{[n]}$ contains neither $Y$ nor $Y'$ as an induced subposet, and $\varnothing,[n] \notin \mathcal{A}$, then
\begin{displaymath}
\mathcal{S}um_{A\in \mathcal{A}} \frac{1}{\binom{n}{\abs{A}}} \le 2.
\end{displaymath}
\end{theorem}

To prove Theorem \ref{inducedLYM}, we introduce a second chain partitioning argument along the cycle.  These partitions may be thought of as the analogue of orthogonal symmetric chain partitions \cite{shearer1979probabilities} for the cycle. The method and the proof of Theorem  \ref{induced} are given in Section $3$.  Observe that because $B$ is a subposet of both $Y$ and $Y'$, and the inequality $\La(n,\mathcal{P}) \le \La^{\#}(n,\mathcal{P})$ always holds, we again have a direct generalization of the result of De Bonis, Katona and Swanepoel.  Note that the problem of determining $\La^{\#}(n,B)$ is fundamentally different.  In this case, one can construct a larger family by adjoining distance $4$ constant weight codes \cite{graham1980lower} to two consecutive full levels.  Here an exact result is difficult to determine because the corresponding coding theory question is a long standing open problem.   Some asymptotic results for this problem may be found in \cite{patkos2014induced}.

The paper is organized as follows.  In the second section we introduce the first chain decomposition and determine $\La(n,S)$.  In the third section we use the same decomposition to find $\La(n,Y_k,Y_k')$ for all $k \ge 2$.  In the last section we introduce the second decomposition and show that $\La^\#(n,Y,Y') = \Sigma(n,2)$.

\mathcal{S}ection{Forbidding $S$ and the first cycle decomposition}
\label{S}
A cyclic permutation, $\mathcal{S}igma$, is a cyclic ordering $x_1,x_2,\dots, x_n,x_1$ of the elements of $[n]$.   We refer to the sets $\{x_i,x_{i+1},\dots,x_{i+t}\}$, with addition taken modulo $n$, as intervals along the cyclic permutation.  For our purpose we will not consider $\varnothing$ or $[n]$ to be intervals.    The following lemma is the essential ingredient of the proof of Theorem \ref{skewbutterfly}:

\begin{lemma}
\label{lemma:mainlemma}
If $\mathcal{A}$ is  a collection of intervals along a cyclic permutation $\mathcal{S}igma$ of $[n]$ which does not contain $S$ as a subposet, then 
\begin{displaymath}
\abs{\mathcal{A}} \le 2n.
\end{displaymath} 
\end{lemma}

To prove Lemma \ref{lemma:mainlemma} we will work with a decomposition of the intervals along $\mathcal{S}igma$ into maximal chains.   Set $\mathcal{C}_i = \{ \{x_i\}, \{x_i,x_{i-1}\}, \{x_i,x_{i-1},x_{i+1}\},\dots, \{x_i,x_{i-1},\dots,x_{i+n/2-1}\} \}$ when $n$ is even, and set $\mathcal{C}_i = \{\{x_i\}, \{x_i,x_{i-1}\}, \{x_i,x_{i-1},x_{i+1}\},\dots, \{x_i,x_{i-1},\dots,x_{i-(n-1)/2}\}\}$ when $n$ is odd, where $1 \le i \le n$ (See Figure \ref{figure 1}).  Observe that the set of chains $\{\mathcal{C}_i\}_{i=1}^n$ forms a partition of the intervals along $\mathcal{S}igma$.  We will refer to this partition as the \emph {chain decomposition} of $\mathcal{S}igma$. Additionally, chains corresponding to consecutive elements of $\mathcal{S}igma$ are called consecutive chains.  

\begin{figure}
\caption{The chain decomposition is marked with bold lines on the poset of intervals along $\mathcal{S}
\label{figure 1}
\end{figure}

If $\mathcal{A}$ does not contain $S$ as a subposet, and $\mathcal{C}$ is a chain from the chain decomposition of $\mathcal{S}igma$, then it is easy to see that $\abs{\mathcal{A}\cap \mathcal{C}} \le 4$.   We will classify the chains in the chain decomposition by their intersection pattern with $\mathcal{A}$.   If $\abs{\mathcal{A} \cap \mathcal{C}}=k$, then we say $\mathcal{C}$ is of type $k$.    When $k=3$ we distinguish $3$ cases (See Figure \ref{figure 2} for an example of each case). If $\mathcal{C}$ contains exactly $3$ elements of $\mathcal{A}$, not all occurring consecutively on $\mathcal{C}$, then we say $\mathcal{C}$ is type $3^S$ ($S$ for separated).  If $\mathcal{C}$ has exactly 3 elements of $\mathcal{A}$ occurring consecutively with two sets of odd size, then $\mathcal{C}$ is type $3^R$ (facing right).  If $\mathcal{C}$ has exactly 3 elements of $\mathcal{A}$ occurring consecutively with two sets of even size, then $\mathcal{C}$ is type $3^L$ (facing left). 

\begin{figure}
\caption{An example of chains of types $3^R$, $3^L$ and $3^S$ are drawn. The elements of $\mathcal{A}
\label{figure 2}
\end{figure}

We will now prove a sequence of lemmas showing which types of chains can occur consecutively in the chain decomposition of $\mathcal{S}igma$.  These lemmas will let us disregard the exact intersection pattern of $\mathcal{A}$ with the chains and allow us to work instead with the sequence of chain types.

\begin{lemma}
\label{lemma:technical1}
Let $\mathcal{C}_i$ and $\mathcal{C}_{i+1}$ be two consecutive chains in the chain decomposition of a cyclic permutation.  If $\mathcal{C}_i$ is of type $4, 3^R$ or $3^S$, then $\abs{\mathcal{A} \cap \mathcal{C}_{i+1}} \le 1$.
\end{lemma}
\begin{proof}
First, note that if $\mathcal{C}_i$ is of type 4, then we can remove a set from $\mathcal{A} \cap \mathcal{C}_i$ to make it type $3^S$.  Hence, we may assume that $\mathcal{C}_i$ is of type $3^S$ or $3^R$. 

In order to reduce case analysis, we will now argue that we only need to consider certain configurations of sets from $\mathcal{A}$ in $\mathcal{C}_i \cup \mathcal{C}_{i+1}$.  Consider the Hasse diagram  of $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ as a graph (See Figure \ref{figure 3}). Call the vertices corresponding to sets in $\mathcal{A}$ occupied and the rest unoccupied.  If either the top or bottom vertex in the chain is occupied, then we extend $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ in both directions maintaining the same relations between adjacent levels. Then, every occupied vertex either has degree $2$ or degree $4$.  We will see that it is sufficient to consider the case when only degree $2$ vertices are occupied.   Indeed, if instead of taking a degree $4$ vertex, we take an adjacent unoccupied degree $2$ vertex, then no additional containments are introduced.   If $\mathcal{C}_i$ is of type $3^R$ or $3^S$, then every occupied vertex of degree $4$ can be replaced by a distinct adjacent unoccupied vertex of degree 2 (This cannot be done if $\mathcal{C}_i$ is type $3^L$).  Thus, we may assume that all of the occupied vertices in $\mathcal{C}_i$ from the the Hasse diagram of $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ have degree $2$. 

\begin{comment}
In the case when we have an occupied vertex at the top or bottom of $\mathcal{C}_i$ or $\mathcal{C}_{i+1}$ it may be impossible to replace that vertex with an adjacent one of degree $2$.   For example,  consider the case when $\mathcal{C}_i \cap \mathcal{A}$ consists of the bottom $3$ sets from $\mathcal{C}_i$.  In this case, we may view $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ as embedded (in an induced sense) in a larger poset.   Indeed, construct a new poset $\mathcal{C'}_i \cup \mathcal{C'}_{i+1}$ by adding 4 new elements (2 levels) at the top, and 4 more new elements (2 more levels) at the bottom of the Hasse diagram of $\mathcal{C}_i \cup \mathcal{C}_{i+1}$, extending $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ to a larger poset which is again isomorphic to the union of chains (as in the Figure \ref{figure 3}).  Clearly, the relations induced by the vertices from $\mathcal{A}$ induce the same relations in both $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ and $\mathcal{C'}_i \cup \mathcal{C'}_{i+1}$.  Thus, we will show $\mathcal{A}$ contains a skew-butterfly by reasoning on the poset $\mathcal{C'}_i \cup \mathcal{C'}_{i+1}$.  We may use the same replacement argument we used above,  and it again follows that each occupied vertex has degree $2$.  Since the arguments we would give on $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ or $\mathcal{C'}_i \cup \mathcal{C'}_{i+1}$ are identical, from now on, we will consider the poset $\mathcal{C}_i \cup \mathcal{C}_{i+1}$ and assume that each occupied vertex on it has degree $2$.
\end{comment}
 

\begin{figure}
\caption{Hasse diagrams of $\mathcal{C}
\label{figure 3}
\end{figure}

Let the sets in $\mathcal{A} \cap \mathcal{C}_i$ be $L,M$ and $N$ with $L \mathcal{S}ubset M \mathcal{S}ubset N$.  Assume, by contradiction, that there are two sets $A,B \in \mathcal{A} \cap \mathcal{C}_{i+1}$ with $A \mathcal{S}ubset B$.  We may assume that $A$ and $B$ correspond to degree $2$ vertices in $\mathcal{C}_i \cap \mathcal{C}_{i+1}$.   We will distinguish three cases by comparing the sizes of $A$ and $B$ with the size of $M$.   If $\abs{A}< \abs{M}<\abs{B}$, then  $L,M,N,A,B$ forms a skew-butterfly with $L,A \mathcal{S}ubset N,B$ and $L \mathcal{S}ubset M \mathcal{S}ubset N$. If $\abs{M}<\abs{A}<\abs{B}$, then $L,M,N,A,B$ forms a skew-butterfly with $L,M \mathcal{S}ubset N,B$ and $L \mathcal{S}ubset A \mathcal{S}ubset B$.  The case $\abs{A}<\abs{B}<\abs{M}$ is symmetric. It follows that there can be at most one set in $\mathcal{A} \cap \mathcal{C}_{i+1}$.

\end{proof}
\begin{lemma}
\label{lemma:technical2}
Let $\mathcal{C}_i,\mathcal{C}_{i+1}$ and $\mathcal{C}_{i+2}$ be three consecutive chains in the chain decomposition of a cyclic permutation.  If $\mathcal{C}_i$ is of type $4,3^R$ or $3^S$ and $\abs{\mathcal{A} \cap \mathcal{C}_{i+1}}=1$, then $\mathcal{C}_{i+2}$ is of type $0,1,2$ or $3^R$.
\end{lemma}

\begin{proof}
By contradiction, suppose $\mathcal{C}_i$ is type $4, 3^R$ or $3^S$, $\abs{\mathcal{A} \cap \mathcal{C}_{i+1}}=1$ and $\mathcal{C}_{i+2}$ is type $3^L, 3^S$ or 4. If $\mathcal{C}_i$ or $\mathcal{C}_{i+2}$ is of type 4, then we may disregard one set to make it type $3^S$.   By similar reasoning as used in Lemma \ref{lemma:technical1}, we may assume all occupied vertices on the Hasse diagram of $\mathcal{C}_i \cup \mathcal{C}_{i+1} \cup \mathcal{C}_{i+2}$ from $\mathcal{C}_i$ and $\mathcal{C}_{i+2}$ have degree 2.  Let $L,M,N$ be the three sets in $\mathcal{A} \cap \mathcal{C}_i$ in increasing order, and let $A,B,C$ be the three sets in $\mathcal{A} \cap \mathcal{C}_{i+2}$ in increasing order.  Without loss of generality, we may assume $\abs{M}>\abs{B}$. This, in turn, implies that $\abs{M}=\abs{B}+1$ for otherwise $L,M,N,A,B$ would be a skew-butterfly with $L,A \mathcal{S}ubset M,N$ and $A \mathcal{S}ubset B \mathcal{S}ubset N$.  We will consider the possible locations of the set $S \in \mathcal{A}\cap \mathcal{C}_{i+1}$ on $\mathcal{C}_{i+1}$.  If $\abs{S} \le \abs{B}$, then $N,S,A,B,C$ is a skew-butterfly with $A,S \mathcal{S}ubset N,C$ and $A \mathcal{S}ubset B \mathcal{S}ubset C$.  If $\abs{S}>\abs{B}$, then $L,M,N,S,A$ is a skew-butterfly with $L,A \mathcal{S}ubset N,S$ and $L \mathcal{S}ubset M \mathcal{S}ubset N$. Thus, in either case we have a contradiction.
\end{proof}

By symmetry, we also have the following corollaries of Lemmas \ref{lemma:technical1} and \ref{lemma:technical2}:

\begin{corollary}
\label{cor:technical1}
Let $\mathcal{C}_i$ and $\mathcal{C}_{i+1}$ be two consecutive chains in the chain decomposition of a cyclic permutation.  If $\mathcal{C}_{i+1}$ is of type $4, 3^L$ or $3^S$, then $\abs{\mathcal{A} \cap \mathcal{C}_i} \le 1$.
\end{corollary}

\begin{corollary}
\label{cor:technical2}
Let $\mathcal{C}_i,\mathcal{C}_{i+1}$ and $\mathcal{C}_{i+2}$ be three consecutive chains in the chain decomposition of a cyclic permutation.  If $\mathcal{C}_{i+2}$ is of type $4, 3^L$ or $3^S$ and $\abs{\mathcal{A} \cap \mathcal{C}_{i+1}}=1$, then $\mathcal{C}_i$ is of type $0,1,2$ or $3^L$.
\end{corollary}

We now have sufficient information about which consecutive chain types are allowed to  prove Lemma \ref{lemma:mainlemma}:

\begin{proof}[Proof of Lemma \ref{lemma:mainlemma}]
We must show that the average intersection of $\mathcal{A}$ with chains from the decomposition is at most $2$.  To this end, we will form groups of chains such that the number of sets from $\mathcal{A}$ in each group is at most twice the size of that group.  

First, consider chains of type 4.  If there is a sequence of chains alternating between type 4 and type 0 spanning every chain in the chain decomposition, then it is easy to see that the average is at most 2.  Otherwise, take each maximal group of consecutive chains alternating between type $0$ and type $4$, beginning and ending with a type $4$ chain. Call such a group a 4-0-4 pattern (it may just consist of a single chain of type $4$).  If the group has length $\ell$, then there are $2\ell+2$ sets contributed from $\mathcal{A}$.  We will add additional chains to this group to decrease the average to 2.  By Lemma \ref{lemma:technical1}, if the chain following the type 4 chain on either side is not type 0, then it must be type 1.  In this case, we add the type 1 chain to the group.  Otherwise, we have a type 0 chain followed by a chain of type 0,1,2 or 3.  If it is type 3, we add both the type 0 and type 3 chain to our group.  Otherwise, we just add the type 0 chain.  In any case, if we have added $k$ more chains to our group (on both sides of the 4-0-4 pattern), then we have added a total of at most $2k-2$ more sets from $\mathcal{A}$.  Thus, in total, the group now consists of $k+\ell$ chains having at most $2k + 2\ell$ sets from $\mathcal{A}$, as desired.

Now, consider any remaining type 3 chain.  Lemma \ref{lemma:technical1} and Corollary \ref{cor:technical1} ensure that it has a type 1 or type 0 chain on at least one side (right or left).  By Lemma \ref{lemma:technical2} and Corollary \ref{cor:technical2} and by the previous grouping of the chains of type $4$, we know that this chain was not used by any group consisting of chains of type $4$.  Thus, every type $3$ chain may be grouped with its adjacent type $1$ or $0$ chain.  All remaining chains in the decomposition have at most 2 sets from $\mathcal{A}$ and so we may group them all together.   

\begin{comment}
First, we consider the chains of type $4$.  Take a maximal group of consecutive chains which alternate between types $0$ and $4$.  Call such a group a 0-4 pattern.    If every chain in the decomposition is contained in this group, then we are done since the average intersection of $\mathcal{A}$ with a chain is exactly $2$.  If the 0-4 pattern ends with a $4$ on either side, then the following chain must be of type 1 (e.g., $(\dots,0,4,0,4,1)$).  In this case, we add the type $1$ chain to our group and stop adding more chains from that side.   If the 0-4 pattern ends with a 0 on either side, then the following chain may be of type 0,1,2 or 3 (e.g., $(\dots,4,0,4,0,3)$). In the case when the following chain is type $0,1$ or $2$, we do not include it in the group.  In the case the following chain is type 3, we do include it, and we stop adding chains from that side. In any case we have that the intersection of any such group with $\mathcal{A}$ is at most twice the size of the group.  To prove this, take the largest set of consecutive chains in the 0-4 pattern which starts and ends with 4, and say that this set has size $\ell$.   The number of sets from $\mathcal{A}$ in these $\ell$ chains is exactly $2\ell+2$. On either side of these $\ell$ chains we add either $1$ set from $1$ chain or $3$ sets from 2 chains.  Thus, if there are $k$ such chains on the sides, then the number of sets contributed by these chains is at most $2k-2$ and so in total we have at most $2\ell + 2k$ sets from $\mathcal{A}$ across $\ell + k$ chains.

Now consider any remaining chain of type $3$.  
  To this end, we will group each chain of type $3^R,3^L$ or $4$ with chains of type $0$ or $1$ so that the groups are disjoint and the chains in each group have an average of at most $2$ sets from $\mathcal{A}$.   By Lemma \ref{lemma:technical1}, every chain of type $3^R$ is followed by one of $0$ or $1$.  Group these two chains together.  Similarly, by Corollary \ref{cor:technical1} we may group each chain of type $3^L$ with one of type $0$ or $1$ preceding it.   Finally, group each chain of type $4$ with both the chain following it and the one preceding it (both are of type $0$ or $1$). Call these groups $\mathcal{G}_i$.  

Lemma \ref{lemma:technical2} and Corollary \ref{cor:technical2} ensure that if two of these groups are overlapping, then they must share a chain of type $0$.  Let us call each collection of overlapping groups as a \textit{block} and we write a block $\mathcal{B}_j = (\mathcal{G}_{j_1},\mathcal{G}_{j_2}, \cdots,\mathcal{G}_{j_k})$ if the group $\mathcal{G}_{j_r}$ overlaps with $\mathcal{G}_{j_{r+1}}$ for each $1 \le r \le k-1$ and if $\mathcal{G}_{j_1}$ does not overlap with any other group to its left and if $\mathcal{G}_{j_k}$ does not overlap with any other group to its right. Now, it is easy to see that all the blocks are disjoint. Moreover, a block can only be of the form $(X, 0, Y)$ or $(X, 0, 4, 0 \ldots, 4, 0, Y)$ or $(1, 4, 0, \ldots, 4, 0, Y)$ or $(X, 0, 4, 0 \ldots, 4, 1)$ or $(1, 4, 0 \ldots, 4, 1)$ where $X = 3^R \text{ or } 3^S \text{ or } \emptyset$ and $Y = 3^L \text{ or } \emptyset$. In each case, it is easy to see that the average number of sets from $\mathcal{A}$ in a chain, over all chains of a block is at most $2$. All chains which are not grouped contain at most $2$ sets from $\mathcal{A}$, and so it follows that the average number of sets from $\mathcal{A}$ in a chain is also at most $2$, as desired. 
\end{comment}

\end{proof}

We now derive the LYM-type inequality, Theorem \ref{skewbutterfly}, from Lemma \ref{lemma:mainlemma}.  

\begin{proof}
We will double count pairs $(A,\mathcal{S}igma)$ where $A \in \mathcal{A}$ and $\mathcal{S}igma$ is a cyclic permutation of $[n]$.  Let $f(A,\mathcal{S}igma)$ be the indicator function for $A\in \mathcal{A}$ and $A$ being an interval along $\mathcal{S}igma$.  For each $A \in \mathcal{A}$, there are $\abs{A}!(n-\abs{A})!$ cyclic permutations containing $A$ as an interval.  It follows that
\begin{displaymath}
\mathcal{S}um_{A \in \mathcal{A}} \mathcal{S}um_\mathcal{S}igma f(A,\mathcal{S}igma) = \mathcal{S}um_{A \in \mathcal{A}} \abs{A}!(n-\abs{A})!.
\end{displaymath}
On the other hand, Lemma \ref{lemma:mainlemma} implies
\begin{displaymath}
\mathcal{S}um_\mathcal{S}igma \mathcal{S}um_{A \in \mathcal{A}} f(A,\mathcal{S}igma) \le \mathcal{S}um_\mathcal{S}igma 2n = 2n!. 
\end{displaymath}
Dividing through by $n!$ gives
\begin{displaymath}
\mathcal{S}um_{A \in \mathcal{A}} \frac{1}{\binom{n}{\abs{A}}} \le 2,
\end{displaymath}
as desired.
\end{proof}

Finally, we deduce Theorem \ref{skew} from Theorem \ref{skewbutterfly}.

\begin{proof}
If $\mathcal{A}$ contains neither $[n]$ nor $\varnothing$, then the result follows easily from Theorem \ref{skew}. If $\mathcal{A}$ contains $[n]$, but there is an $n-1$ element set $A$ not contained in $\mathcal{A}$, then replacing $[n]$ with $A$ in $\mathcal{A}$ introduces no new relations and so yields another family of the same size without a skew-butterfly. Thus, in this case, Theorem \ref{skew} again yields the result.  If $\mathcal{A}$ contains $[n]$ and the entire $n-1^{st}$ level, let $\mathcal{A}' = \{A \in \mathcal{A}: \abs{A} \le n-2\}$.  Then, $\mathcal{A}'$ is an antichain, for otherwise we would have a skew-butterfly. Thus, $\abs{\mathcal{A}'} \le \binom{n}{\floor{n/2}}$ by Sperner's Theorem and so $\abs{\mathcal{A}} \le \binom{n}{\floor{n/2}} + n + 1$.  For $n \ge 5$ this implies $\abs{\mathcal{A}} \le  \binom{n}{\floor{n/2}} +  \binom{n}{\floor{n/2}+1}$.  An analogous argument works for the case when $\varnothing \in \mathcal{A}$.   If $n=4$ we give another argument (We are still assuming $\mathcal{A}$ contains all $n-1$ element sets).   If $\mathcal{A}'$ is a full level, then $\mathcal{A}$ contains  a skew-butterfly.  If $\mathcal{A}'$ is not a full level, then the equality case of Sperner's theorem implies $\abs{\mathcal{A}'} \le \binom{n}{\floor{n/2}}-1$, and so $\abs{\mathcal{A}} \le n + \binom{n}{\floor{n/2}}$ which yields the required bound when $n=4$.   The case $n=3$ is easily checked by hand.  
\end{proof}

We end this section by mentioning the relation between this approach and the double chain method.  It is not hard to see that a double chain has the exact same poset structure as two consecutive chains in the chain decomposition described above.  Namely, the degree 2 vertices from the Hasse diagram of consecutive chains correspond to the sets from the secondary chain of a double chain.  It follows that any forbidden subposet result that can be determined exactly with the double chain method can also be determined exactly using a decomposition of a cyclic permutation, and, thus, chain decompositions of the cycle may be viewed as a generalization of the double chain method.   

\mathcal{S}ection{Forbidding $Y_k$ and $Y_k'$}
\label{YkYk'}
We will use the same decomposition of the cycle as in Section \ref{S}.  The new bound we must prove is 

\begin{lemma}
\label{lemma:mainlemma2}
If $\mathcal{A}$ is a collection of intervals along a cyclic permutation $\mathcal{S}igma$ of $[n]$ which does not contain $Y_k$ or $Y_k'$ as a subposet, then 
\begin{displaymath}
\abs{\mathcal{A}} \le kn.
\end{displaymath} 
\end{lemma}

As before, we will consider groups of consecutive chains.    Each chain, $\mathcal{C}$, with $k+1$ sets in $\mathcal{C} \cap \mathcal{A}$ is characterized by whether the second largest element in $\mathcal{A} \cap \mathcal{C}$ faces left or faces right (has even or odd cardinality, respectively).  We say that a chain with $k+1$ elements of $\mathcal{A}$ is of type $k+1^R$ if the second largest element faces right and $k+1^L$ if it faces left.  

\begin{lemma}
\label{lemmaX}
Let $\mathcal{C}_i$ and $\mathcal{C}_{i+1}$ be consecutive chains in the decomposition.  If $\mathcal{C}_i$ is of type $k+1^R$, then $\abs{\mathcal{A} \cap \mathcal{C}_{i+1}} \le k-1$, and  $\abs{\mathcal{A} \cap \mathcal{C}_{i+1}} = k-1$ implies that the largest element of $\mathcal{A} \cap \mathcal{C}_{i+1}$ is the same size as the second largest element of $\mathcal{A} \cap \mathcal{C}_{i}$.
\end{lemma}

\begin{proof}
Let $A$ be the second smallest set in $\mathcal{A} \cap \mathcal{C}_i$ and $B$ be the second largest. Let $Y$ be the set of size $\abs{B}$ in $\mathcal{C}_{i+1}$, and if $A$ is degree $2$ (left), then let $X$ be the set of size $\abs{A}-1$ in $\mathcal{C}_{i+1}$. If $A$ is degree $4$, then let $X$ be the set of size $\abs{A}$ in $\mathcal{C}_{i+1}$. In either case, let $\mathcal{R}$ be the collection of those sets in $\mathcal{C}_{i+1}$ (not necessarily in $\mathcal{A}$) having sizes strictly between $\abs{X}$ and $\abs{Y}$ (See Figure \ref{figure 5}).  Every set in $\mathcal{C}_{i+1} \cap \mathcal{A}$  must lie in $\mathcal{R} \cup \{X\}\cup\{Y\}$ for otherwise we would have a $Y_k$ or $Y_k'$.    Now, $\abs{\mathcal{A} \cap \mathcal{R}} \le k-2$ for otherwise we would have a $k+2$ chain (actually, $\abs{\mathcal{A} \cap \mathcal{R}} \le k-3$ in the case $A$ is degree $4$).  If we take $k-1$ sets from $\mathcal{R} \cup \{X\}$, then we have a $Y_k'$ and so  we can take at most $k-2$ sets total from $\mathcal{R} \cup \{X\}$.  It follows that $\abs{\mathcal{A} \cap \mathcal{C}_{i+1}} \le k-1$ with equality only if $Y \in \mathcal{A}$. 

\end{proof}

\begin{figure}
\caption{The sets $A$, $B$, $X$ and $Y$ are shown, and the collection $\mathcal{R}
\label{figure 5}
\end{figure}

By a symmetric argument we have
\begin{corollary}
\label{corY}
Let $\mathcal{C}_i$ and $\mathcal{C}_{i+1}$ be consecutive chains in the decomposition.  If $\mathcal{C}_{i+1}$ is of type $k+1^L$, then $\abs{\mathcal{A} \cap \mathcal{C}_{i}} \le k-1$, and  $\abs{\mathcal{A} \cap \mathcal{C}_{i}} = k-1$ implies that the largest element of $\mathcal{A} \cap \mathcal{C}_{i}$ is the same size as the second largest element of $\mathcal{A} \cap \mathcal{C}_{i+1}$.
\end{corollary}

\begin{lemma}
There are no $3$ consecutive chains $\mathcal{C}_i, \mathcal{C}_{i+1},\mathcal{C}_{i+2}$ such that $\mathcal{C}_i$ is type $k+1^R$, $\mathcal{C}_{i+1}$ is type $k-1$ and $\mathcal{C}_{i+1}$ is type $k+1^L$.
\end{lemma}

\begin{proof}
Since $\mathcal{C}_{i}$ is type $k+1^R$ and $\mathcal{C}_{i+2}$ is type $k+1^L$, the respective second largest elements of $\mathcal{A} \cap \mathcal{C}_i$ and $\mathcal{A} \cap \mathcal{C}_{i+2}$ must be of different sizes.  It follows from Lemma \ref{lemmaX} and Corollary \ref{corY} that we can have at most $k-2$ sets in $\mathcal{A} \cap \mathcal{C}_{i+1}$.
\end{proof}

We now have what we need to prove Lemma \ref{lemma:mainlemma2}.

\begin{proof}[Proof of Lemma \ref{lemma:mainlemma2}]
Every group of $3$ consecutive chains of type $k+1^R$, $\le k-2$ and $k+1^L$, respectively,  may be grouped together yielding a total of at most $3k$ sets on $3$ chains.  All remaining chains of type $k+1^R$ may be paired with a chain of at most $k-1$ sets from $\mathcal{A}$ following it, and all remaining chains of type $k+1^L$ may be paired with a chain of at most $k-1$ sets preceding it.  It follows that $\mathcal{A}$ consists of at most $kn$ intervals along the cyclic permutation $\mathcal{S}igma$.
\end{proof}

Theorem \ref{YkLYM} follows directly from Lemma \ref{lemma:mainlemma2} as before.  It remains to use Theorem \ref{YkLYM} to deduce Theorem \ref{Yk}.

\begin{proof}[Proof of Theorem \ref{Yk}]
Let $\mathcal{A} \mathcal{S}ubset 2^{[n]}$ be a $Y_k$ and $Y_k'$-free family.  If neither of $\varnothing$ and $[n]$ are in $\mathcal{A}$, then the result is immediate from Theorem \ref{YkLYM}.  If $\varnothing$ and $[n]$ are in $\mathcal{A}$, then $\mathcal{A} \mathcal{S}etminus \{\varnothing,[n]\}$ is $k$-chain free and so has size at most $\Sigma(n,k-1)$ by Erd\H{o}s's theorem. Since $2 + \Sigma(n,k-1) \le \Sigma(n,k)$ for $n \ge k+1$ and $k\ge 2$, we are done.  Finally, suppose that $\varnothing \in \mathcal{A}$ and $[n] \not\in \mathcal{A}$.  If there is a singleton set $\{x\} \not\in \mathcal{A}$, then we may replace $\varnothing$ with $\{x\}$ and we are back in the first case.  Hence, we may assume that $\mathcal{A}$ contains every singleton set ($\binom{[n]}{1}\mathcal{S}ubset \mathcal{A}$).  Let $\mathcal{A}' = \mathcal{A} \mathcal{S}etminus \{\{\varnothing\} \cup \binom{[n]}{1}\}$.  Now, $\mathcal{A}'$ is $k$-chain free, so again by Erd\H{o}s's theorem, $\abs{\mathcal{A}'} \le \Sigma(n,k-1)$.  It follows that $\abs{\mathcal{A}} \le 1 + n + \Sigma(n,k-1)$. If $\mathcal{A}'$ contains $k-1$ full levels, then we have a copy of $Y_k'$, so we may assume we do not.  However, then we may apply the equality case of Erd\H{o}s's theorem to obtain that $\abs{\mathcal{A}} \le n + \Sigma(n,k-1)$.  Finally, since $n \ge k+1$ implies that the $k^{th}$ largest level has size at least $n$, we have $\abs{\mathcal{A}} \le \Sigma(n,k)$, as desired.
\end{proof}

\mathcal{S}ection{Forbidding induced $Y$ and $Y'$ and second cycle decomposition}
As in the proof of Theorem \ref{skew}, we will need to prove a lemma which bounds the largest intersection of an induced $Y$,$Y'$-free family with the set of intervals along a cyclic permutation.

\begin{lemma}
\label{ortho}
If $\mathcal{A}$ is a collection of intervals along a cyclic permutation $\mathcal{S}igma$ of $[n]$ which does not contain $Y$ or $Y'$ as an induced subposet, then 
\begin{displaymath}
\abs{\mathcal{A}} \le 2n.
\end{displaymath} 
\end{lemma}

\begin{proof}
We will consider a different way of partitioning the chains along $\mathcal{S}igma$  from the one in the proofs of the previous theorems.  Let $\mathcal{S}igma$ be the ordering $x_1,x_2,\dots,x_n,x_1$.  Group the intervals along $\mathcal{S}igma$ into chains $\mathcal{C}_i = \{\{x_i\},\{x_i,x_{i+1}\}, \{x_i,x_{i+1},x_{i+2}\},\dots,\{x_i,x_{i+1},\dots,x_{i+n-1}\}\}$ where $1 \le i \le n$.  Observe that $\{\mathcal{C}_i\}_{i=1}^n$ is a partition of the intervals along $\mathcal{S}igma$.  

We now consider a second way of partitioning the intervals by setting \\  $\mathcal{C}_i' = \{\{x_i\},\{x_i,x_{i-1}\}, \{x_i,x_{i-1},x_{i-2}\},\dots, \{x_i,x_{i-1},\dots, x_{i-n+1}\}\}$ for $1 \le i \le n$.  Observe that $\{\mathcal{C}_i'\}_{i=1}^n$ is again a partition (See Figure \ref{Ortho_decomp}). 

\begin{figure}
\caption{Orthogonal chain decompositions $\{\mathcal{C}
\label{Ortho_decomp}
\end{figure}

Now, the two partitions we have defined have the property that if $A$ and $B$ are in $\mathcal{C}_i$ for some $i$, then at most one of $A$ and $B$ are in any $\mathcal{C}_j'$.   Moreover, since each $A$ is contained in exactly one chain in each partition, it follows that each $A$ is contained in exactly $2$ chains in the union of the two partitions.  Thus,  we have 
\begin{displaymath}
\mathcal{S}um_{\mathcal{C} \in \{\mathcal{C}_i\}_{i=1}^n \cup \{C_i'\}_{i=1}^n} \abs{\mathcal{A} \cap \mathcal{C}} = 2 \abs{\mathcal{A}}.
\end{displaymath}
On the other hand, if a chain $\mathcal{C} \in \{\mathcal{C}_i\}_{i=1}^n$ intersects $\mathcal{A}$ in $k> 2$ sets $A_1,A_2,\dots,A_k$ with $A_1\mathcal{S}ubset A_2 \mathcal{S}ubset \dots \mathcal{S}ubset A_k$, then there are $k-2$ chains in $\mathcal{C}' \in \{\mathcal{C}_i'\}_{i=1}^n$ such that $\abs{\mathcal{A} \cap \mathcal{C}'} =1$, namely those chains in $\{\mathcal{C}_i'\}_{i=1}^n$ containing $A_2,A_3,\dots, A_{k-2}$ or $A_{k-1}$,  as an intersection of greater than one would yield an induced $Y$ or $Y'$.   Similarly, if a chain $\mathcal{C}' \in \{\mathcal{C}_i'\}_{i=1}^n$ intersects $\mathcal{A}$ in $k > 2$ sets, then there are $k-2$ chains from $\{\mathcal{C}_i\}_{i=1}^n$ which intersect $\mathcal{A}$ in exactly one set.   
Here, we are using an additional property of the decomposition that if $A \in \mathcal{C} \cap \mathcal{C}'$, then no set larger than $A$ in $\mathcal{C}$ is comparable to a set larger than $A$ in $\mathcal{C}'$, and, similarly, no set smaller than $A$ in $\mathcal{C}$ is comparable to a set smaller than $A$ in $\mathcal{C}'$. 
We have shown that there is a total of $2k-2$ incidences of $\mathcal{A}$ with these $k-1$ chains. It follows that the number of pairs $(A,\mathcal{C})$ where $A \in \mathcal{A},  \mathcal{C} \in \{\mathcal{C}_i\}_{i=1}^n \cup \{\mathcal{C}_i'\}_{i=1}^n$ and $A \in \mathcal{C}$ is at most twice the number of chains. Thus,
\begin{displaymath}
\mathcal{S}um_{\mathcal{C} \in \{\mathcal{C}_i\}_{i=1}^n \cup \{C_i'\}_{i=1}^n} \abs{\mathcal{A} \cap \mathcal{C}} \le 2 \abs{ \{\mathcal{C}_i\}_{i=1}^n \cup \{C_i'\}_{i=1}^n} = 4n.
\end{displaymath}
Dividing through by $2$ yields the desired inequality.  
\end{proof}

Lemma \ref{ortho} implies the LYM-type inequality, Theorem \ref{inducedLYM}, exactly as in the previous proofs.  It remains to derive the bound on $\La^\#(n,Y,Y')$ using Theorem \ref{inducedLYM}.

\begin{proof}[Proof of Theorem \ref{induced}]
 If $\mathcal{A}$ contains neither $\varnothing$ nor $[n]$, then we are done by Theorem \ref{inducedLYM}.  If $\varnothing$ and $[n]$ are in $\mathcal{A}$, then $\mathcal{A} \mathcal{S}etminus \{\varnothing,[n]\}$ is induced $V$ and $\Lambda$ free.  It follows from  Katona and Tarjan \cite{katona1983extremal} that
 \begin{displaymath}
  \La^\#(n,Y,Y') \le 2 + \La^\#(n,V,\Lambda) = 2 + 2\binom{n-1}{\floor{\frac{n-1}{2}}} \le \Sigma(n,2).
  \end{displaymath}
  Now, assume without loss of generality that $\varnothing \not\in \mathcal{A}$ but $[n] \in \mathcal{A}$, and let $\mathcal{A}' = \mathcal{A} \mathcal{S}etminus \{[n]\}$.  Since $\mathcal{A}'$ is induced $Y$ and $Y'$-free,  it satisfies the hypothesis of Theorem \ref{inducedLYM}. Assume, by contradiction, that $\abs{\mathcal{A}'} = \Sigma(n,2)$. It follows that equality holds in Theorem \ref{inducedLYM}. If $n$ is odd, then we have that $\mathcal{A}'  = \binom{[n]}{\floor{n/2}} \cup \binom{[n]}{\ceil{n/2}}$ which implies $\mathcal{A}$ induces a $Y'$, contradiction.  If $n$ is even, then $\binom{[n]}{n/2} \mathcal{S}ubset \mathcal{A}'$ and $\binom{n}{n/2+1}$ sets from $\binom{[n]}{n/2-1} \cup \binom{[n]}{n/2+1}$  are in $\mathcal{A}$.  Since $\mathcal{A}$ contains no $Y'$, it follows that $\mathcal{A}' \cap \binom{[n]}{n/2+1} = \varnothing$.  Thus, we must have $\mathcal{A}' = \binom{[n]}{n/2 -1} \cup \binom{[n]}{n/2}$, but then $\mathcal{A}$ still contains an induced $Y'$, contradiction.
  
  
\end{proof}

\mathcal{S}ubsection*{Acknowledgements}
We thank D\"{o}m\"{o}t\"{o}r P\'{a}lv\"{o}lgyi for many helpful discussions which were especially useful to the proof of Lemma \ref{ortho}. We also thank D\'{a}niel Gerbner, Guillaume Lagarde, Gyula O.H.Katona, D\'aniel Nagy and Bal\'azs Patk\'os for many useful discussions and Anna Jablonkai for helping with the illustrations.

\end{document}