\documentclass[12pt]{article}
\usepackage{e-jc}


\usepackage{amsfonts, amssymb, amsmath, amsthm, xcolor, graphicx, pstricks, pstricks-add}



\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{cla}[thm]{Claim}
\newtheorem{lm}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{example}[thm]{Example}

\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{alg}[thm]{Algorithm}
\newtheorem{prob}[thm]{Problem}
\newtheorem{rem}[thm]{Remark}

\newcommand{\m}{\textnormal{mult}}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}

\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\F}{\mathcal{F}}

\renewcommand{\baselinestretch}{1.1}


\title{\bf On cross-intersecting families of set partitions}
\author{Cheng Yeaw Ku \thanks{corresponding author}\\
\small Department of Mathematics\\[-0.8ex]
\small National University of
Singapore\\[-0.8ex]
\small Singapore 117543.\\
\small\tt matkcy@nus.edu.sg\\
\and
Kok Bin Wong\\
\small Institute of Mathematical Sciences\\[-0.8ex]
\small University of Malaya\\[-0.8ex]
\small 50603 Kuala Lumpur, Malaysia. \\
\small\tt kbwong@um.edu.my
}

\date{\dateline{Jan 1, 2012}{Jan 2, 2012}\\
\small Mathematics Subject Classifications: 05D05}




\begin{document}

 \maketitle


\begin{abstract}\noindent
Let $\mathcal{B}(n)$ denote the collection of all set partitions
of $[n]$. Suppose $\mathcal A_1,\mathcal A_2\subseteq \mathcal{B}(n)$ are cross-intersecting i.e. for all $A_1\in \mathcal A_1$ and $A_2\in \mathcal A_2$, we have $A_1\cap A_2\neq\varnothing$. It is proved that for sufficiently large $n$,
\[ \vert \mathcal A_1\vert\vert \mathcal A_2\vert\leq B_{n-1}^2
\]
where $B_{n}$ is the $n$-th Bell number. Moreover, equality holds if and only if $\mathcal{A}_1=\mathcal A_2$ and $\mathcal A_1$ consists of all set partitions with a fixed singleton.

% keywords are optional
  \bigskip\noindent \textbf{Keywords:} 
  cross-intersecting family, Erd{\H
o}s-Ko-Rado, set partitions 
\end{abstract}


\section{Introduction}

\subsection{Finite sets}

Let $[n]=\{1, \ldots, n\}$ and ${[n] \choose k}$ denote the
family of all $k$-subsets of $[n]$. A fundamental result in extremal combinatorial set theory is the Erd{\H o}s-Ko-Rado theorem (\cite{EKR}, \cite{Frankl}, \cite{Wilson}) which asserts that if a
family $\mathcal{A} \subseteq {[n] \choose k}$ is $t$-{\em
intersecting} (i.e. $\vert A\cap  B\vert\geq t$ for any $A,B\in \A$), then $|\mathcal{A}|
\le {n-t \choose k-t}$ for $n\geq (k-t+1)(t+1)$. Recently, there are several Erd{\H o}s-Ko-Rado type  results  
(see \cite{CK, E, EFP, GM, HK, KL, KW, LM, Toku, WZ}), most notably is the result of Ellis, Friedgut and Pilpel \cite{EFP}, which states that for sufficiently large $n$ depending on $t$, a $t$-intersecting family $\A$ of permutations has size at most $(n-t)!$, with equality if and only if $\A$ is a coset of the stabilizer of $t$ points, thus settling an old conjecture of Deza and Frankl \cite{DF}. 

Let $\mathcal{A}_i\subseteq {[n] \choose k_i}$ for $i=1,2,\dots, r$. We say that the families $\mathcal{A}_1,\mathcal A_2,\dots, \mathcal A_r$ are $r$-\emph{cross} $t$-\emph{intersecting} if $\vert A_1\cap A_2\cap \cdots\cap A_r\vert\geq t$ holds for all $A_i\in\mathcal A_i$. When $t=1$, we will just say $r$-\emph{cross intersecting} instead of $r$-cross $1$-intersecting. Furthermore when $r=2$ and $t=1$, we will just say \emph{cross-intersecting} instead of $2$-cross intersecting. It has been shown by Frankl and Tokushige \cite{FT} that if $\mathcal{A}_1,\mathcal A_2,\dots, \mathcal A_r\subseteq {[n] \choose k}$ are $r$-cross intersecting, then for $n\geq rk/(r-1)$,
\begin{equation}
\prod_{i=1}^r \vert \mathcal A_i\vert\leq \binom{n-1}{k-1}^r.\notag
\end{equation}


For differing values of $k$'s, we have the following result. 

\begin{thm}[Bey \cite{Bey}, Matsumoto and Tokushige \cite{MT}, Pyber  \cite{Pyber}]\label{Bey} Let $\mathcal{A}_1\subseteq {[n] \choose k_1}$ and $\mathcal{A}_2\subseteq {[n] \choose k_2}$ be cross-intersecting. If $k_1,k_2\leq n/2$, then
\begin{equation}
\vert \mathcal A_1\vert \vert \mathcal A_2\vert\leq \binom{n-1}{k_1-1} \binom{n-1}{k_2-1}.\notag
\end{equation}
Equality holds for $k_1+k_2<n$ if and only if $\mathcal A_1$ and $\mathcal A_2$ consist of all $k_1$-element resp.
$k_2$-element sets containing a fixed element.
\end{thm}





\subsection{Set partitions}
A set partition of $[n]$ is a collection of pairwise
disjoint nonempty subsets (called {\em blocks}) of $[n]$ whose
union is $[n]$. Let $\mathcal{B}(n)$ denote the family of all
set partitions of $[n]$. It is well-known that the size of
$\mathcal{B}(n)$ is the $n$-th Bell number, denoted by $B_{n}$.
A block of size one is also known as a {\em singleton}. We
denote the number of all set partitions of $[n]$ which are
singleton-free (i.e. without any singleton) by $\tilde{B}_{n}$.

A family
$\mathcal{A} \subseteq \mathcal{B}(n)$ is said to be $t$-{\em
intersecting} if any two of its members have at least $t$ blocks
in
common. Ku and Renshaw
\cite[Theorem 1.7 and Theorem 1.8]{KR} proved the following analogue of the Erd{\H o}s-Ko-Rado
theorem for set partitions.

\begin{thm}[Ku-Renshaw]\label{Ku-Renshaw}
Suppose $\mathcal{A} \subseteq \mathcal{B}(n)$ is
a $t$-intersecting family. Then, for  $n\geq n_0(t)$, 
\[ |\mathcal{A}| \le B_{n-t}, \]
with equality if and only if $\mathcal{A}$ consists of all set partitions with $t$ fixed singletons.
\end{thm}

 Recently, Ku and Wong \cite[Theorem 1.4]{Ku_Wong} proved a generalization of Theorem \ref{Ku-Renshaw}, which is an analogue of the Hilton-Milner Theorem \cite{HM} for set partitions.


In this paper,  we will prove the following analogue of Theorem \ref{Bey} for set partitions.

\begin{thm}\label{thm_main} Let $\mathcal A_1,\mathcal A_2\subseteq \mathcal{B}(n)$ be cross-intersecting. Then, for $n\geq n_0$, 
\[ \vert \mathcal A_1\vert\vert \mathcal A_2\vert\leq B_{n-1}^2.
\]
 Moreover, equality holds if and only if $\mathcal{A}_1=\mathcal A_2$ and $\mathcal A_1$ consists of all set partitions with a fixed singleton. 
\end{thm} 



\section{Splitting operation}

In this section, we will prove some important results regarding
the splitting operation for $r$-cross $t$-intersecting families of set
partitions. These results are the `cross' version of \cite[Proposition 3.1, 3.2, 3.3, 3.4]{KR}.

Let $i, j \in [n]$, $i \not = j$, and $P \in \mathcal{B}(n)$.
Denote by
$P_{[i]}$ the block of $P$ which contains $i$. We define the
$(i,j)$-{\it
split} of $P$ to be the following set partition:
\[ s_{ij}(P) = \left\{\begin{array}{ll}
P \setminus \{P_{[i]}\} \cup \{\{i\}, P_{[i]}\setminus\{i\}\} &
\textrm{if } j \in P_{[i]}, \\
P      &   \textrm{otherwise. }
\end{array} \right.   \]
For a family $\mathcal{A} \subseteq \B(n)$, let
$s_{ij}(\mathcal{A}) = \{ s_{ij}(P):
P \in \mathcal{A}\}$. Any family $\mathcal{A}$ of set partitions
can be decomposed
with respect to given $i$, $j \in [n]$ as follows:
\begin{eqnarray}
\A & = & (\A \setminus \A_{ij}) \cup \A_{ij}, \nonumber
\end{eqnarray}
where $\A_{ij} = \{ P \in \A: s_{ij}(P) \not \in \A\}$. Define
the
$(i,j)$-{\em splitting} of $\A$ to be the family
\[ S_{ij}(\A) = (\A \setminus \A_{ij}) \cup s_{ij}(\A_{ij}). \]
It is not hard to see that $\vert S_{ij}(\A)\vert=\vert \A\vert$. 

Let $I(n,r,t)$ denote the set of all $r$-cross $t$-intersecting families of
set partitions of $[n]$. Let $\mathbf A=\{\A_1,\A_2,\dots, \A_r\}\in I(n,r,t)$. We set 
\begin{equation}
S_{ij}(\mathbf A)=\{S_{ij}(\A_1),S_{ij}(\A_2),\dots, S_{ij}(\A_r)\},\notag
\end{equation}
and write $S_{ij}(\mathbf A)=\mathbf A$ if $S_{ij}(\A_l)=\A_l$ for $l=1,2,\dots, r$.

We define $\vert \mathbf A\vert=\prod_{l=1}^r \vert \A_l\vert$. It is not hard to see that
\begin{equation}
\vert \mathbf A\vert=\prod_{i=1}^r \vert S_{ij}(\A_l)\vert.\notag
\end{equation}

An element  $\mathbf A=\{\A_1,\A_2,\dots, \A_r\}\in I(n,r,t)$ is said to be \emph{trivial}, if $\A_1=\A_2=\cdots=\A_r$ and $\A_1$ consists of all set partitions containing $t$ fixed singletons.

\begin{prop}\label{prop_inherit} Let $i,j\in [n]$, $i\neq j$. If $\mathbf A \in I(n,r,t)$, then
$S_{ij}(\mathbf A) \in I(n,r,t)$.
\end{prop}

\begin{proof} Let $\mathbf A=\{\A_1,\A_2,\dots, \A_r\}$. For each $l=1,2,\dots, r$, choose an  $A_l\in S_{ij}(\A_l)$. If $A_l\in\A_l$ for all $l$, then $\vert A_1\cap A_2\cap\cdots\cap A_r\vert\geq t$. Without loss of generality, suppose $A_l\in s_{ij}((\A_l)_{ij})$ for $l=1,\dots, q$, and $A_l\in\A_l\setminus (\A_l)_{ij}$ for $l=q+1,\dots,r$. Then 
$A_l=s_{ij}(P_l)$ for $l=1,\dots, q$, where $P_l\in (\A_l)_{ij}\subseteq A_l$. 

Now there are at least $t$ blocks, say $M_1,M_2,\dots, M_t$, that are all contained in $P_1\cap \cdots\cap P_q\cap A_{q+1}\cap\cdots\cap A_r$.
If $\{i,j\}\nsubseteq M_y$ for $y=1,\dots,t$, then $M_1,M_2,\dots, M_t\in A_l$ for $l=1,\dots, q$. This implies that  $M_1,M_2,\dots, M_t$ are contained in $A_1\cap \cdots\cap A_q\cap A_{q+1}\cap\cdots\cap A_r$, and thus $\vert A_1\cap\cdots\cap A_r\vert\geq t$. 

Suppose one of the $M_y$ contains $\{i,j\}$. We may assume that $\{i,j\}\subseteq M_1$. If $q=r$, then $\{i\}$, $M_2,\dots, M_t$ are contained in  $A_1\cap \cdots\cap A_r$, and thus   $\vert A_1\cap\cdots\cap A_r\vert\geq t$. 
Suppose $1\leq q<r$. Since $A_l\in\A_l\setminus (\A_l)_{ij}$ for $l\geq q+1$, we must have $s_{ij}(A_l)\in \A_l$. 
Note that $M_2,\dots, M_t$ are contained in $P_1\cap \cdots\cap P_q\cap s_{ij}(A_{q+1})\cap\cdots\cap s_{ij}(A_r)$. Since $\vert P_1\cap \cdots\cap P_q\cap s_{ij}(A_{q+1})\cap\cdots\cap s_{ij}(A_r)\vert\geq t$, there is 
a block $M_{t+1}$ disjoint from $M_1,M_2,\dots, M_t$, that is contained in $P_1\cap \cdots\cap P_q\cap s_{ij}(A_{q+1})\cap\cdots\cap s_{ij}(A_r)$. Now $M_{t+1}$ is a block in $A_1\cap \cdots\cap A_q\cap A_{q+1}\cap\cdots\cap A_r$, for $\{i,j\}\nsubseteq M_{t+1}$. Hence $\vert A_1\cap\cdots\cap A_r\vert\geq t$.
\end{proof}


\begin{prop}\label{prop_reverse} Let $n\geq t+1$. Suppose $\mathbf A\in I(n,r,t)$ and $\vert\mathbf A\vert>1$. Let $i,j\in [n]$, $i\neq j$. If $S_{ij}(\mathbf A)$ is trivial, then $\mathbf A$ is trivial.
\end{prop}

\begin{proof} Let $\mathbf A=\{\A_1,\A_2,\dots, \A_r\}$. Then $S_{ij}(\mathbf A)=\{S_{ij}(\A_1),S_{ij}(\A_2),\dots, S_{ij}(\A_r)\}$ and by Proposition \ref{prop_inherit}, $S_{ij}(\mathbf A) \in I(n,r,t)$. Since $S_{ij}(\mathbf A)$ is trivial, $S_{ij}(\A_1)=S_{ij}(\A_2)=\cdots=S_{ij}(\A_r)$ and $S_{ij}(\A_1)$ consists of all set partitions containing $t$ fixed singletons, say $\{x_1\}$, $\{x_2\}$, $\dots$, $\{x_t\}$. Note that $T=\{\{x_1\}, \{x_2\},\dots, \{x_t\}, [n]\setminus \{x_1,\dots, x_t\}\}\in S_{ij}(\A_1)$. If $T\in s_{ij}((\A_1)_{ij})$, then $T=s_{ij}(P)$ for a $P\in (\A_1)_{ij}\subseteq \A_1$. Note that $P$ will have exactly $t$ blocks. Now, if $Q_l\in \A_l$ for $l=2,\dots, r$, then  $P=Q_2=\cdots =Q_r$, for $\vert P\cap Q_2\cap\cdots\cap Q_r\vert\geq t$. Therefore $\A_2=\A_3=\cdots=\A_r=\{P\}$, and this implies that $\A_1=\{P\}$. So $\vert \mathbf A\vert=\prod_{l=1}^r \vert \A_l \vert=1$,  a contradiction.
So we may assume that $T\in \A_1\setminus (\A_1)_{ij}\subseteq \A_1$. Similarly, $T\in\A_2\cap\cdots\cap \A_r$. 


Suppose $\A_1\neq S_{ij}(\A_1)$. Then there is a $P\in \A_1$ with $s_{ij}(P)\notin \A_1$. Now
\begin{equation}
\vert P\cap \overbrace {T\cap \cdots\cap T}^{r-1}\vert \geq t,\notag
\end{equation} 
for $T\in\A_2\cap\cdots\cap \A_r$. Suppose $[n]\setminus \{x_1,\dots, x_t\}$ is a block in $P$. Since $T$ has exactly $t+1$ blocks, we deduce that $P=T$.  This means that $T\in (\A_1)_{ij}$, and $s_{ij}(T)\in S_{ij}(\A_1)$. So $T\notin S_{ij}(\A_1)$, a contradiction.

Suppose $[n]\setminus \{x_1,\dots, x_t\}$ is not a block in $P$. Then $\{x_1\}, \{x_2\},\dots, \{x_t\}$ are blocks in $P$. This implies that $P\in S_{ij}(\A_1)$, for $S_{ij}(\mathbf A)$ is trivial. Since $P\in\A_1$, we must have $s_{ij}(P)\in \A_1$, a contradiction. Hence $\A_1=S_{ij}(\A_1)$. Similarly $\A_l= S_{ij}(\A_l)$ for $l=2,\dots,r$.
\end{proof}


An element  $\mathbf A\in I(n,r,t)$ is said to be {\it compressed} if for any
$i,j\in [n]$, $i \not = j$, we have $S_{ij}(\mathbf A)=\mathbf A$. For a set
partition
$P$, let $\sigma(P)=\{ x : \{x\} \in P\}$ denote the union of
its
singletons (block of size $1$). For a family $\A$ of set
partitions,
let $\sigma(\A)=\{\sigma(P): P \in \A\}$. Note that $\sigma(\A)$
is a family of subsets of $[n]$. Now for $\mathbf A=\{\A_1,\dots, \A_r\}$, where $\A_1,\dots, \A_r\subseteq \mathcal B(n)$, set $\sigma(\mathbf A)=\{\sigma(\A_1),\dots,\sigma(\A_r)\}$. We say $\sigma(\mathbf A)$ is $r$-cross $t$-intersecting if $\sigma(\A_1),\dots,\sigma(\A_r)$ are $r$-cross $t$-intersecting.



\begin{prop}\label{prop_compressed} Given an element  $\mathbf A\in I(n,r,t)$, by repeatedly applying the splitting operations, we eventually obtain a compressed $\mathbf A^{*} \in I(n,r,t)$ with $|\mathbf A^{*}|=|\mathbf A|$.
\end{prop}

\begin{proof}
Note that if $S_{ij}({\mathbf A}) \not = {\mathbf A}$, then the $(i,j)$-splits of some partitions are finer than the originals and therefore will move down in the partition lattice. Eventually this results in a compressed family of partitions.
\end{proof}



For a compressed $\mathbf A$, its $r$-cross $t$-intersecting property can be
transferred to $\sigma(\mathbf A)$, thus allowing us to access the
structure of $\mathbf A$ via the structure of $\sigma(\mathbf A)$.

\begin{prop}\label{prop_transfer} If $\mathbf A \in I(n,r,t)$ is compressed, then $\sigma(\mathbf A)$ is $r$-cross $t$-intersecting.
\end{prop}

\begin{proof} Let $\mathbf A=\{\A_1,\A_2,\dots, \A_r\}$. Assume, for a contradiction, that there exist $P_l\in\A_l$, $l=1,\dots, r$ such that $\vert \sigma(P_1)\cap \cdots\cap \sigma(P_l)\vert<t$. Since $\vert P_1\cap \cdots\cap P_r\vert\geq t$, there are $s\geq t-\vert \sigma(P_1)\cap \cdots\cap \sigma(P_l)\vert$ common blocks of  $P_1,\dots, P_r$ (each of size at least 2), say $M_1,\dots, M_s$, which are disjoint from $\sigma(P_1)\cup\cdots\cup \sigma(P_r)$. Fix two distinct points $x_e, y_e$ from each $M_e$. Then $P_1^*=s_{x_sy_s}(\cdots(s_{x_1y_1}(P_1))\cdots)\in \A_1$, for $\mathbf A$ is compressed. Now $\vert P_1^*\cap P_2\cap\cdots\cap P_r\vert <t$,  a contradiction.
\end{proof}

\section{Proof of main result}

Recall that the size of $\mathcal{B}(n)$ is the $n$-th Bell number, denoted by $B_{n}$, and the number of all set partitions of $[n]$ which are singleton-free (i.e. without any singleton) is denoted by $\tilde{B}_{n}$.

The following identities for $B_{n}$ and $\tilde{B}_{n}$ are straightforward.

\begin{lm}\label{identity}
Let $n \ge 2$. Then
\begin{eqnarray}
B_{n} & = & \sum_{k=0}^{n} {n \choose k} \tilde{B}_{n-k},
\label{e1} \\
\tilde{B}_{n} & = & \sum_{k=1}^{n-1} {n-1 \choose k}
\tilde{B}_{n-1-k}, \label{e2}
\end{eqnarray}
with the conventions $B_{0}=\tilde{B}_{0}=1$.
\end{lm}
Note in passing that $\tilde{B}_{1}=0$. By (\ref{e1}) and (\ref{e2}),
\begin{equation}
B_n=\tilde{B}_n+\tilde{B}_{n+1}.\label{ttt}
\end{equation}

Given a real number $x$, we shall denote the greatest integer less than or equal to $x$, by $\lfloor x\rfloor$. Note that $\lfloor x\rfloor \leq  x<\lfloor x\rfloor +1$. Some useful inequalities involving  $B_n$ can be found in \cite{Klazar}. However we just need the following inequality. 
 
\begin{lm}\label{lm_less} There is a positive integer $n_0$ such that for $n\geq n_0$,
\[ \tilde{B}_{n-1}> 8^n\sum_{\lfloor \frac{n}{2}\rfloor \leq k\leq n} {n \choose k}\tilde{B}_{n-k}. \]
\end{lm}

\begin{proof} By  (\ref{e2}), 
\begin{align}
\sum_{\lfloor \frac{n}{2}\rfloor \leq k\leq n} {n \choose k}\tilde{B}_{n-k} & \leq \tilde{B}_{n-\lfloor\frac{n}{2}\rfloor +2} \sum_{\lfloor \frac{n}{2}\rfloor \leq k\leq n} {n \choose k}\notag\\
&\leq  2^n\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +2}.\notag
\end{align}
So it is sufficient to show that $\tilde{B}_{n-1}/\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +2}> (16)^n$.

Again by (\ref{e2}), for any fixed $q$, $\tilde{B}_{m}/\tilde{B}_{m-2}>q$ for sufficiently large $m$. Therefore
\begin{align}
\frac{\tilde{B}_{n-1}}{\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +2}}&\geq \left( \frac{\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +2u}}{\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +2u-2}}\right)\cdots \left( \frac{\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +6}}{\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +4}}\right)\left( \frac{\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +4}}{\tilde{B}_{n-\lfloor \frac{n}{2}\rfloor +2}}\right)\notag\\
& > q^{u-1},\notag
\end{align}
where $u=\lfloor \frac{1}{2}(\lfloor \frac{n}{2}\rfloor-3)\rfloor$. Clearly $u-1\geq \frac{n}{8}$. So if we choose $q=(16)^{8}$, then for sufficiently large $n$, the lemma follows.
\end{proof}

Let $\mathbf A=\{\A_1,\dots, \A_r\} \in I(n,r,t)$ be compressed. We say $\sigma(\mathbf A)$ is \emph{trivial} if there is a fixed $t$-set, say  $T$, such that $T\subseteq \sigma(P_l)$ for all $P_l\in\A_l$, $l=1,\dots, r$.

\begin{thm}\label{thm_pre_main} Let $\mathbf A\in I(n,2,1)$ be compressed. If  $\sigma(\mathbf A)$ is non-trivial, then 
\begin{equation}
\vert \mathbf A\vert < B_{n-1}^2.\notag
\end{equation}
\end{thm}


\begin{proof}  Let $\mathbf A=\{\A_1, \A_2\}$. For $k \ge 1$, let $\F_{lk} = \sigma(\A_l) \cap {[n] \choose k}$.
If $\F_{l1}\neq \varnothing$ for $l=1,2$, then  $\sigma(\mathbf A)$ is trivial. So we may assume that $\F_{21}=\varnothing$. By Proposition \ref{prop_transfer}, $\sigma(\mathbf A)$ is cross-intersecting. 
Note that  $\vert \A_1\vert\leq \sum_{1\leq k\leq n} \vert F_{1k}\vert \tilde B_{n-k}$ and  $\vert \A_2\vert\leq \sum_{2\leq k\leq n} \vert F_{2k}\vert \tilde B_{n-k}$. 
Then
\begin{align}
\vert \A_1\vert &\leq \sum_{1\leq k < \lfloor \frac{n}{2}\rfloor} \vert F_{1k}\vert \tilde B_{n-k}+\sum_{\lfloor \frac{n}{2}\rfloor\leq k\leq n} \vert F_{1k}\vert \tilde B_{n-k}\notag\\
&\leq \sum_{1\leq k < \lfloor \frac{n}{2}\rfloor} \vert F_{1k}\vert \tilde B_{n-k}+\sum_{\lfloor \frac{n}{2}\rfloor\leq k\leq n}  \binom{n}{k}\tilde B_{n-k},\notag
\end{align}
and
\begin{equation}
\vert \A_2\vert \leq \sum_{2\leq k < \lfloor \frac{n}{2}\rfloor} \vert F_{2k}\vert \tilde B_{n-k}+\sum_{\lfloor \frac{n}{2}\rfloor\leq k\leq n}  \binom{n}{k}\tilde B_{n-k}.\notag
\end{equation}
Let
\begin{align}
Q &= \sum_{\lfloor \frac{n}{2}\rfloor\leq k\leq n}  \binom{n}{k}\tilde B_{n-k}\notag\\
M_1 & = \sum_{1\leq k <\lfloor \frac{n}{2}\rfloor} \vert F_{1k}\vert \tilde B_{n-k}\notag\\
M_2 & = \sum_{2\leq k <\lfloor \frac{n}{2}\rfloor} \vert F_{2k}\vert \tilde B_{n-k}.\notag
\end{align}
Then
\begin{align}
\vert\mathbf A\vert & \leq (M_1+Q)(M_2+Q)\notag\\
& =M_1M_2+M_1Q+M_2Q+Q^2.\notag
\end{align}
Note that by (\ref{e2}) and (\ref{ttt}),
\begin{align}
 M_{l} &\leq \tilde B_{n} \sum_{1\leq k < \lfloor \frac{n}{2}\rfloor} \vert F_{lk}\vert \notag\\
& \leq \tilde B_{n} \sum_{1\leq k < \lfloor \frac{n}{2}\rfloor} \binom{n}{k}\notag\\
& \leq 2^n\tilde B_{n}\notag\\
&\leq 2^nB_{n-1}.\notag
\end{align}
By Lemma \ref{lm_less} and (\ref{ttt}), $Q\leq \frac{1}{8^{n}}\tilde B_{n-1}< \frac{1}{8^{n}}B_{n-1}< B_{n-1}$. Therefore
\begin{align}
M_1Q+M_2Q+Q^2 &< (2^n+2^n+1)B_{n-1}\left(\frac{\tilde{B}_{n-1}}{8^n}\right)\notag\\
&<\frac{1}{2}B_{n-1}\tilde{B}_{n-1}.\notag
\end{align}


By Theorem \ref{Bey}, 
\begin{align}
M_1M_2 &\leq \sum_{\substack {1\leq k_1< \lfloor\frac{n}{2}\rfloor,\\ 2\leq k_2< \lfloor\frac{n}{2}\rfloor}}   \binom{n-1}{k_1-1} \binom{n-1}{k_2-1} \tilde B_{n-k_1} \tilde B_{n-k_2}\notag\\
&=\left( \sum_{1\leq k<  \lfloor \frac{n}{2}\rfloor}\binom{n-1}{k-1} \tilde B_{n-k}   \right)\left( \sum_{2\leq k<  \lfloor \frac{n}{2}\rfloor}\binom{n-1}{k-1} \tilde B_{n-k}   \right).\notag
\end{align}


By (\ref{e1}), 
\begin{align}
\sum_{1\leq k<  \lfloor \frac{n}{2}\rfloor}\binom{n-1}{k-1} \tilde B_{n-k} & < B_{n-1}\notag\\
\sum_{2\leq k<  \lfloor \frac{n}{2}\rfloor}\binom{n-1}{k-1} \tilde B_{n-k}  & < B_{n-1}-\tilde B_{n-1}.\notag
\end{align}


 So $M_1M_2 \leq (B_{n-1}-\tilde B_{n-1})B_{n-1}$, and
\begin{align}
\vert \mathbf A\vert &< B_{n-1}^2-\tilde B_{n-1}B_{n-1} +\frac{1}{2}(B_{n-1})\tilde{B}_{n-1}\notag\\
&< B_{n-1}^2.\notag
\end{align}
\end{proof}

\noindent {\bf Proof of Theorem \ref{thm_main}}.

Let $\mathbf A\in I(n,2,1)$ be of maximum size. We may assume that ${\mathbf A}$ has size at least $B^{2}_{n-1}$. Repeatedly apply the splitting operations until we obtain an $\mathbf A^{*}\in I(n,2,1)$ such that $\mathbf A^{*}$ is compressed (Proposition \ref{prop_compressed}). By Proposition \ref{prop_transfer}, $\sigma(\mathbf A^{*})$ is cross-intersecting. If $\sigma(\mathbf A^{*})$ non-trivial, by  Theorem \ref{thm_pre_main}, $\vert \mathbf A\vert< B_{n-1}^2$, a contradiction. So $\sigma(\mathbf A^{*})$ is trivial. This implies that $\mathbf A^*$ is trivial, for $\mathbf A$ is of maximum size. It then follows from Proposition \ref{prop_reverse} that $\mathbf A$ is trivial.

\subsection*{Acknowledgement}

We would like to thank the anonymous referee for the comments that helped us make
several improvements to this paper.

\begin{thebibliography}{99}

\bibitem{Bey} C. Bey, On cross-intersecting families of sets, {\em Graphs Combin.} {\bf 21} (2005), 161--168.

\bibitem {CK} P. J. Cameron and C. Y. Ku, Intersecting families of permutations, 
{\em European J. Combin}. {\bf 24} (2003), 881--890.

\bibitem{DF} M. Deza and P. Frankl, On the maximum number of
permutations with given maximal or minimal distance, {\em J. Combin.
Theory Ser. A} {\bf 22} (1977), 352--360.

\bibitem{E} D. Ellis, Stability for t-intersecting families of
permutations, {\em J. Combin. Theory Ser. A} {\bf 118} (2011), 208--227.

\bibitem{EFP} D. Ellis, E. Friedgut and H. Pilpel, Intersecting families of permutations, {\em J. Amer. Math. Soc.} {\bf 24} (2011), 649-682.

\bibitem{EKR} P. Erd{\H o}s, C. Ko and R. Rado, Intersection
theorems for systems of finite sets, {\em Quart. J. Math. Oxford
Ser.} 2 {\bf 12} (1961), 313--318.

\bibitem{Frankl} P. Frankl, The Erd{\H o}s-Ko-Rado theorem is true for $n=ckt$, {\em Col. Soc. Math. J. Bolyai} {\bf 18} (1978), 365--375.

\bibitem{FT} P. Frankl and N. Tokushige, On $r$-cross intersecting families of sets, {\em Combin. Probab. Comput.} {\bf 20} (2011), 749--752.


\bibitem{GM} C. Godsil and K. Meagher, A new proof of the Erd{\H
o}s-Ko-Rado theorem for intersecting families of permutations, {\em European J. Combin.} {\bf 30} (2009), 404--414. 



\bibitem{HM} A. J. W. Hilton and E. C. Milner, Some intersection
theorems for systems of finite sets, {\em Quart. J. Math.
Oxford} (2) {\bf 18} (1967), 369--384.

\bibitem {HK} G. Hurlbert and V. Kamat, Erd{\H o}s-Ko-Rado theorems for chordal graphs and trees, 
{\em J. Combin. Theory Ser. A} {\bf 118} 
(2011), 829--841. 

\bibitem {Klazar} M. Klazar, Counting set systems by weight, {\em Electron. J. Combin.} {\bf 12} (2005), \#R11.


\bibitem {KL} C. Y. Ku and I. Leader, An Erd{\H o}s-Ko-Rado theorem for partial permutations, 
{\em Discrete Math.} {\bf 306} (2006), 74--86.

\bibitem{KR} C. Y. Ku and D. Renshaw, Erd{\H o}s-Ko-Rado theorems for
permutations and set partitions, {\em J. Combin. Theory Ser. A} {\bf 115} (2008), 1008--1020.

\bibitem {KW} C. Y. Ku and T. W. H. Wong, Intersecting families in the alternating group and 
direct product of symmetric groups, {\em Electron. J. Combin.} {\bf 14} (2007), \#R25.

\bibitem{Ku_Wong} C. Y. Ku and K. B. Wong, An Analogue of Hilton-Milner Theorem for Set
Partitions, preprint available at \arxiv{1109.0417}.

\bibitem{LM} B. Larose and C. Malvenuto, Stable sets of maximal size in Kneser-type graphs, {\em European
J. Combin.} {\bf 25} (2004), 657--673.

\bibitem{MT} M. Matsumoto and N. Tokushige, The exact bound in the  Erd{\H o}s-Ko-Rado theorem for cross-intersecting families, {\em J. Combin. Theory Ser. A} {\bf 52} (1989), 90--97.

\bibitem{Pyber} L. Pyber, A new generalization of the  Erd{\H o}s-Ko-Rado theorem, {\em J. Combin. Theory Ser. A} {\bf 43} (1986), 85--90.

\bibitem {Toku} N. Tokushige, A product version of the Erd{\H o}s-Ko-Rado theorem, 
{\em J. Combin. Theory Ser. A} {\bf 118} 
(2011), 1575--1587. 

\bibitem{WZ} J. Wang and S. J. Zhang, An Erd{\H
o}s-Ko-Rado-type theorem in Coxeter groups, {\em European J. Combin.} {\bf 29} (2008), 1112--1115.


\bibitem{Wilson} R.M. Wilson, The exact bound in the Erd{\H o}s-Ko-Rado theorem, {\em Combinatorica} {\bf 4} (1984), 247--257.



\end{thebibliography}


\end{document}







\end{document}