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

\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}




\begin{document}


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


\theoremstyle{definition}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{example}[thm]{Example}
\newtheorem{alg}[thm]{Algorithm}
\newtheorem{prob}[thm]{Problem}

\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}


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



\title{\bf A Deza-Frankl type of theorem for set partitions}
\author{
Cheng Yeaw Ku \\
\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, 2014}{Jan 2, 2015}\\
\small Mathematics Subject Classifications: 05D99}




\maketitle


\begin{abstract}\noindent
A set partition of $[n]$ is a collection of pairwise
disjoint nonempty subsets (called blocks) of $[n]$ whose
union is $[n]$. Let $\mathcal{B}(n)$ denote the family of all
set partitions of $[n]$. A family
$\mathcal{A} \subseteq \mathcal{B}(n)$ is said to be $m$-intersecting if any two of its members have at least $m$ blocks
in
common.     For any set partition $P \in \mathcal{B}(n)$,  let $\tau(P) = \{x: \{x\} \in P\}$ denote the union of its singletons. Also, let $\mu(P) = [n] -\tau(P)$ denote the set of elements that do not appear as a singleton in $P$. Let  
  \begin{align*} 
{\mathcal F}_{2t} & =\left\{P \in \mathcal{B}(n)\ : \ \vert \mu (P)\vert\leq t\right\};\\
\\
{\mathcal F}_{2t+1}(i_0) & =\left\{P \in \mathcal{B}(n)\ : \ \vert\mu (P)\cap ([n]\setminus \{i_0\})\vert\leq t\right\}.\\
\end{align*}  
 In this paper, we show that for $r\geq 3$, there exists a constant $n_0=n_0(r)$ depending on $r$ such that for all $n\geq n_0$, if $\mathcal{A} \subseteq\mathcal{B}(n)$ is $(n-r)$-intersecting, then 
\[ |\mathcal{A}| \leq \begin{cases} \vert {\mathcal F}_{2t}  \vert, & \textnormal{if $r=2t$};\\
\\
 \vert {\mathcal F}_{2t+1}(1)  \vert, & \textnormal{if $r=2t+1$}.
\end{cases}
\]
Moreover, equality holds if and only if 
\[ \mathcal{A}= \begin{cases} {\mathcal F}_{2t}, & \textnormal{if $r=2t$};\\
\\
 {\mathcal F}_{2t+1}(i_0), & \textnormal{if $r=2t+1$},
\end{cases}
\]
for some $i_0\in [n]$.
\end{abstract}

\bigskip\noindent \textbf{Keywords:} $t$-intersecting family, Erd{\H
o}s-Ko-Rado, set partitions

\section{Introduction}

Let $[n]=\{1, \ldots, n\}$, and let $\binom{[n]}{k}$ denote the
family of all $k$-subsets of $[n]$. A family $\mathcal{A}$ of subsets of $[n]$ is $t$-{\em intersecting} if $|A \cap B| \ge t$ for all $A, B \in \mathcal{A}$. One of the most beautiful results in extremal combinatorics is
the Erd{\H o}s-Ko-Rado theorem.

\begin{thm}[Erd{\H o}s, Ko, and Rado \cite{EKR}, Frankl \cite{Frankl}, Wilson \cite{Wilson}]\label{EKR} Suppose $\mathcal{A} \subseteq \binom{[n]}{k}$ is $t$-intersecting and $n>2k-t$. Then for $n\geq (k-t+1)(t+1)$, we have
\begin{equation}
\vert \mathcal{A} \vert\leq \binom{n-t}{k-t}.\notag
\end{equation}
Moreover, if $n>(k-t+1)(t+1)$ then equality holds if and only if $\mathcal{A}=\{A\in \binom{[n]}{k}\ :\ T\subseteq A\}$ for some $t$-set $T$.
\end{thm}


In the celebrated paper \cite{AK}, Ahlswede and Khachatrian extended the Erd{\H o}s-Ko-Rado theorem by determining the structure of all  $t$-intersecting set systems of maximum size for all possible $n$ (see also \cite{Bey, Frankl0, FF, FT, HM, Kee, Ku_Wong3, Ku_Wong8, MT, Pyber, Toku, WZ0} for some related results). There have been many recent results showing that a version of the Erd{\H o}s-Ko-Rado theorem holds for combinatorial objects other than set systems. For example, an analogue of the Erd{\H o}s-Ko-Rado theorem for the Hamming scheme is proved in \cite{Moon}. A complete solution for the $t$-intersection problem in the Hamming space is given in \cite{AK2}. Intersecting families of permutations were initiated by Deza and Frankl in \cite{DF}. Some recent work done on this problem and its variants can be found in \cite{B2, BH,CK, E, EFP, GM, KL, KW, LM, LW, WZ, Ku_Wong7, Ku_Wong9}. The investigation of the Erd{\H os}-Ko-Rado  property for graphs started in \cite{HT}, and gave rise to \cite{B, B3, HS, HST, HK, W}. The Erd{\H o}s-Ko-Rado type results also appear in vector spaces \cite{CP, FW},  set partitions \cite{KR, Ku_Wong, Ku_Wong2} and weak compositions \cite{Ku_Wong4, Ku_Wong5, Ku_Wong6}.





  Let $S_{n}$ denote the set of permutations of $[n]$. A family $\mathcal A\subseteq S_{n}$ is said to be $m$-intersecting if for any $\sigma,\delta\in \mathcal A$, there is an $m$-set $T\subseteq [n]$ such that $\sigma(j)=\delta(j)$ for all $j\in T$. Given any $\sigma\in S_n$, set $\overline \mu (\sigma)=\{ j\in [n]\ :\ \mu (j)\neq j\}$, i.e., $\overline \mu (\sigma)$ is the set of all elements in $[n]$ that are not fixed by $\sigma$. Let
  
  
\begin{align*}
\overline{\mathcal F}_r=\begin{cases} \left\{\sigma\in S_n\ : \ \vert\overline \mu (\sigma)\vert\leq t\right\},   & \textnormal{if $r=2t$};\\
\\
 \left\{\sigma\in S_n\ : \ \vert\overline \mu (\sigma)\cap ([n]\setminus \{1\})\vert\leq t\right\},   & \textnormal{if $r=2t+1$}.
\end{cases}
\end{align*}  
It can be verified easily that $\overline{\mathcal F}_r$ is $(n-r)$-intersecting. Furthermore, Deza and Frankl \cite{DF} proved the following theorem.
  
  \begin{thm}[Deza-Frankl]\label{thm_Deza_Frankl} For $r\geq 3$, there exists an $n_0=n_0(r)$ such that for all $n\geq n_0$, if $\mathcal{A} \subseteq S_{n}$ is $(n-r)$-intersecting, then 
\[ |\mathcal{A}| \leq \vert \overline{\mathcal F}_r  \vert.\]
\end{thm}
  
  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 $m$-{\em
intersecting} if $\vert P\cap Q\vert\geq m$ for all $P,Q\in\A$, i.e., any two of its members have at least $m$ blocks
in
common. Let $I(n,m)$ denote the set of all $m$-intersecting families of set partitions of $[n]$.
  
  For any set partition $P \in \mathcal{B}(n)$,  let $\tau(P) = \{x: \{x\} \in P\}$ denote the union of its singletons. Also, let $\mu(P) = [n] -\tau(P)$ denote the set of elements that do not appear as a singleton in $P$. For any two partitions $P$, $Q$, we make the following simple observations:

\begin{itemize}
\item $P$ and $Q$ cannot intersect in any singleton $\{x\}$ where $x \in \mu(P) \triangle \mu(Q)$ (here the operation $\triangle$ denotes the symmetric difference of two sets).

\item $P$ and $Q$ must intersect in every singleton $\{x\}$ where $x \in [n] - (\mu(P) \cup \mu(Q))$.
\end{itemize}

Let  
  \begin{align*} 
{\mathcal F}_{2t} & =\left\{P \in \mathcal{B}(n)\ : \ \vert\mu (P)\vert\leq t\right\};\\
\\
{\mathcal F}_{2t+1}(i_0) & =\left\{P \in \mathcal{B}(n)\ : \ \vert \mu (P)\cap ([n]\setminus \{i_0\})\vert\leq t\right\}.\\
\end{align*}  
  It can be readily verified that $\mathcal{F}_{2t}\in I(n,n-2t)$ and $\mathcal{F}_{2t+1}(i_0)\in I(n,n-2t-1)$. Moreover, 
\begin{eqnarray}
|\mathcal{F}_{2t}| & = & \sum_{i=0}^{t} \tilde B_{i} { n \choose i},  \label{eq_s1} \\
|\mathcal{F}_{2t+1}(i_0)| & = & \sum_{i=0}^{t} \tilde B_{i} {n \choose i} + \tilde B_{t+1}{n-1 \choose t}. \label{eq_s2}
\end{eqnarray}


In this paper, we will prove the following theorem.


\begin{thm}\label{thm_main}  For $r\geq 3$, there exists an $n_0=n_0(r)$ such that for all $n\geq n_0$, if $\mathcal{A} \subseteq\mathcal{B}(n)$ is $(n-r)$-intersecting, then 
\[ |\mathcal{A}| \leq \begin{cases} \vert {\mathcal F}_{2t}  \vert, & \textnormal{if $r=2t$};\\
\\
 \vert {\mathcal F}_{2t+1}(1)  \vert, & \textnormal{if $r=2t+1$}.
\end{cases}
\]
Moreover, equality holds if and only if 
\[ \mathcal{A}= \begin{cases} {\mathcal F}_{2t}, & \textnormal{if $r=2t$};\\
\\
 {\mathcal F}_{2t+1}(i_0), & \textnormal{if $r=2t+1$},
\end{cases}
\]
for some $i_0\in [n]$.
\end{thm}

Note that Theorem \ref{thm_main} can be considered  as an analogue of Theorem \ref{thm_Deza_Frankl} for set partitions. Let $A_0=\{ \{x\}\ :\ x\in [n]\}$ and $A_1=\{ \{x\}\ :\ x\in [n]\setminus \{1,2\}\} \cup \{\{1,2\}\}$. Then ${\mathcal F}_{2}=\{A_0\}$ and $\{A_0,A_1\}\in I(n,n-2)$. So, $\vert \{A_0,A_1\}\vert=2>\vert {\mathcal F}_{2}  \vert=1$. This explains why $r\geq 3$ is required in Theorem \ref{thm_main}.

\section{Splitting operation}

In this section, we summarize some important results regarding
the splitting operation for intersecting family of set
partitions. We refer the reader to \cite{KR} for proofs which
are omitted here.

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}). \]


Surprisingly, it turns out that for any
$\A \in I(n,m)$, splitting operations preserve the size and the
intersecting property.


\begin{lm}[\cite{KR}, Proposition 3.2] \label{lm_P1}
 Let $\A \in I(n,m)$. Then
$S_{ij}(\A) \in I(n,m)$ and $|S_{ij}(\A)|=|\A|$.
\end{lm}



A family $\A$ of set partitions is {\it compressed} if for any
$i,j
\in [n]$, $i \not = j$, we have $S_{ij}(\A)=\A$.


\begin{lm}[\cite{KR}, Proposition 3.3] \label{lm_P2}
Given a family $\A \in I(n,t)$, by repeatedly applying the splitting
operations, we eventually obtain a compressed family $\A^{*} \in I(n,t)$ with $|\A^{*}|=|\A|$.
\end{lm}

\begin{lm}\label{lm_pre_size} Let $a,b$ be positive integers with $a+b\leq n$. Let $P,Q\in\mathcal B(n)$ be such that $\vert P\cap Q\vert\geq n-a$. If ~$\vert \tau(P)\setminus \mu(Q)\vert \leq n-a-b$, then $P$ and $Q$ have at least $b$ blocks of size at least 2 in common and $\vert \mu(P)\cap \mu(Q)\vert\geq 2b$.
\end{lm}

\begin{proof} Since $\vert \tau(P)\setminus \mu(Q)\vert\leq n-a-b$,  $P$ and $Q$ have at most $n-a-b$ singletons in common. Now,  $\vert P\cap Q\vert\geq n-a$ means that $P$ and $Q$ have at least $n-a$ blocks in common. Therefore, 
$P$ and $Q$ must have at least $b$ blocks of size at least 2 in common. Let $W_1,\dots ,W_{b}\in P\cap Q$ with $\vert W_i\vert \geq 2$ for all $i$. Then $\bigcup_{i=1}^{b} W_i\subseteq \mu(P)\cap \mu(Q)$ and $W_i\cap W_j=\varnothing $ for $i\neq j$. This implies that $2b\leq \sum_{i=1}^{b} \vert W_i\vert\leq \vert \mu(P)\cap \mu(Q)\vert$. 
\end{proof}


\begin{lm}\label{lm_size} If $\A \in I(n,n-r)$, then $\max_{P\in\A} \vert\mu (P)\vert\leq 2r$.
\end{lm}

\begin{proof} Suppose $\max_{P\in\A} \vert\mu (P)\vert=2r+s$ where $s\geq 1$. Let $P_0\in \A$ with $\vert \mu(P_0)\vert=2r+s$. Then $\vert \tau(P_0)\vert=n-2r-s$. Note that $\vert P_0\vert\geq n-r$ for $\A \in I(n,n-r)$. By Lemma \ref{lm_pre_size} (take $Q=P=P_0$ with $a=r$, $b=r+s$), we have  $2r+s=\vert \mu(P_0)\vert\geq 2(r+s)$. Thus, we have $s\leq 0$, a contradiction. Hence, the lemma follows.
\end{proof}

The following theorem says that the family $\mathcal{F}_{2t+1}(i_0)$
is preserved when `undoing' the splitting operations.

\begin{thm} \label{thm_undo} If $t\geq 1$, $n\geq 5t+3$, $\A \in I(n,n-2t-1)$ and $S_{ij}(\mathcal{A}) =\mathcal{F}_{2t+1}(i_0)$, then $\A=\mathcal{F}_{2t+1}(i_0)$.
 \end{thm}

\begin{proof}  Suppose $\A\not\subseteq  \mathcal{F}_{2t+1}(i_0)$. Then $\max_{P\in\A} \vert\mu (P)\cap ([n]\setminus \{i_0\})\vert=t+s$  with $s\geq 1$. Let $P_0\in \A$ with $ \vert\mu (P_0)\cap ([n]\setminus \{i_0\})\vert=t+s$. Then $\vert \mu(P_0)\vert=t+1+s$ or $t+s$, depending on whether $i_0\in \mu(P_0)$ or not. By Lemma \ref{lm_size}, $\vert \mu(P_0)\vert\leq 4t+2$. Since $n\geq 5t+3$, there is a $t$-set $T\subseteq [n]\setminus (\mu(P_0)\cup \{i_0\})$. Let $A_1=\{\{x\}\ :\ x\in [n]\setminus (T\cup \{i_0\})\}\cup \{T\cup \{i_0\}\}$. Then $A_1\in \mathcal{F}_{2t+1}(i_0)=S_{ij}(\mathcal{A})$. 

Now, $\vert \tau(P_0)\setminus (T\cup \{i_0\})\vert=n-2t-1-s$, $\vert T\cup \{i_0\}\vert=t+1\geq 2$ and $(T\cup \{i_0\})\not\subseteq \mu(P_0)$. The only block in $A_1$ that has size greater than one is $T\cup \{i_0\}$. Since $(T\cup \{i_0\})\not\subseteq \mu(P_0)$, $T\cup \{i_0\}\notin P_0$. So, $P_0$ and $A_1$ have singletons in common only. Note that the number of singletons that  $P_0$ and $A_1$ have in common is exactly $\vert \tau(P_0)\setminus (T\cup \{i_0\})\vert=n-2t-1-s$. Thus,  $\vert P_0\cap A_1\vert\leq n-2t-1-s\leq  n-2t-2$. This means that $A_1\notin \A$ and $A_1=s_{ij}(C_1)$ for some $C_1\in \A$.

Now, there are two possibilities for $C_1$ depending on whether $j$ is in $T\cup \{i_0\}$ or not:
\begin{itemize}
\item[(i)] $C_1=\{\{x\}\ :\ x\in [n]\setminus (T\cup \{i,i_0\})\}\cup \{T\cup \{i,i_0\}\}$ and $j\in T\cup \{i_0\}$.
\item[(ii)] $C_1=\{\{x\}\ :\ x\in [n]\setminus (T\cup \{i,i_0,j\})\}\cup \{(T\cup \{i_0\}),\{i,j\}\}$.
\end{itemize}

If (i) holds, then $(T\cup \{i,i_0\})\notin P_0$ since $(T\cup \{i_0\})\not\subseteq \mu(P_0)$, and $\vert \tau(P_0)\setminus (T\cup \{i,i_0\})\vert\leq \vert \tau(P_0)\setminus (T\cup \{i_0\})\vert= n-2t-1-s$. Thus, 
$\vert P_0\cap C_1\vert\leq n-2t-1-s\leq  n-2t-2$, a contradiction.

Suppose (ii) holds. The number of singletons that $P_0$ and $C_1$ have in common is at most $\vert \tau(P_0)\setminus (T\cup \{i,i_0,j\})\vert\leq \vert \tau(P_0)\setminus (T\cup \{i_0\})\vert\leq n-2t-1-s$.
Recall that $T\cup \{i_0\}\notin P_0$. If $\{i,j\}\notin P_0$, then $\vert P_0\cap C_1\vert\leq n-2t-1-s\leq n-2t-2$, a contradiction. If $\{i,j\}\in P_0$, then $\vert P_0\cap C_1\vert\leq n-2t-s$. Since $\vert P_0\cap C_1\vert\geq n-2t-1$, we must have $s=1$, $\vert P_0\cap C_1\vert= n-2t-1$, and $C_1=\{\{x\}\ :\ x\in [n]\setminus (T\cup \{i,i_0,j\})\}\cup \{(T\cup \{i_0\}),\{i,j\}\}$. But then $\vert\mu(C_1)\cap ([n]\setminus \{i_0\}) \vert=\vert T\cup\{i,j\}\vert=t+2>t+1=\vert \mu(P_0)\cap ([n]\setminus \{i_0\})\vert$, contradicting the choice of $P_{0}$. Thus, $\A\subseteq \mathcal{F}_{2t+1}(i_0)$. By Lemma \ref{lm_P1}, $\vert \A\vert=\vert S_{ij}(\A)\vert=\vert \mathcal{F}_{2t+1}(i_0)\vert$. Hence, $\A=\mathcal{F}_{2t+1}(i_0)$.
\end{proof}

\section{Main result}

\begin{lm}\label{lm_technical_1} Let $t\geq 1$, $\A\subseteq \mathcal B(n)$ and  $W\subseteq [n]$. Suppose that $\vert W\vert\leq q$ and
$\vert \mu(P)\setminus W\vert\leq t-1$
for all $P\in \A$. Then there exists an $n_0=n_0(q,t)$ such that for all $n\geq n_0$,
\begin{align*}
\vert \A\vert< n^{t-0.5}.
\end{align*}
\end{lm}

\begin{proof} Note that for each  $P\in\A$, 
\begin{equation}
\mu(P)=C_1\cup C_2,\notag
\end{equation}
where $C_1\subseteq [n]\setminus W$, $\vert C_1\vert\leq t-1$ and $C_2\subseteq W$. The number of such $C_1$ is at most
\begin{align*}
\sum_{i=0}^{t-1} \binom{n-\vert W\vert}{i}\leq \sum_{i=0}^{t-1} \binom{n}{i},
\end{align*}
and the number of such $C_2$ is at most $2^{\vert W\vert}\leq 2^{q}$. Furthermore, $\vert \mu(P)\vert=\vert \mu(P)\setminus W\vert+\vert \mu(P)\cap W\vert\leq t-1+q$. Therefore the number of $Q\in\A$ with $\mu(Q)=\mu(P)$ is at most $\tilde B_{\vert \mu(P)\vert}\leq \tilde B_{t-1+q}$, where $B_{m}$ is the number of singleton-free set partitions of $[m]$. Thus
\begin{align*}
\vert \A\vert &\leq \tilde B_{t-1+q}2^{q}\sum_{i=0}^{t-1} \binom{n}{i}.
\end{align*}
If $t=1$, then $\vert \A\vert \leq \tilde B_{q}2^{q}<n^{0.5}$ provided that $n>(B_{q}2^{q})^2$. Suppose $t\geq 2$. Then
\begin{align*}
\vert \A\vert &\leq \tilde B_{t-1+q}2^{q}\left(1+\sum_{i=1}^{t-1} \frac{n^i}{i!}\prod_{j=1}^{i-1}\left(1-\frac{j}{n}\right)\right)\\
&< \tilde B_{t-1+q}2^{q}\left(1+\sum_{i=1}^{t-1} n^{t-1}\right)\\
&= \tilde B_{t-1+q}2^{q}tn^{t-1}<n^{t-0.5},
\end{align*}
provided that $n\geq (\tilde B_{t-1+q}2^{q}t)^2$. This completes the proof of the lemma.
\end{proof}

\begin{lm}\label{lm_compressed_1} For $t\geq 2$, there exists an $n_0=n_0(t)$ such that for all $n\geq n_0$, if $\A\in I(n,n-2t)$, then
\[ |\mathcal{A}| \leq  \vert {\mathcal F}_{2t}\vert.\]
Moreover, equality holds if and only if $\mathcal{A}={\mathcal F}_{2t}$.
\end{lm}

\begin{proof}  Suppose $\A\not\subseteq \mathcal{F}_{2t}$. Then $\max_{P\in\A} \vert\mu (P)\vert=t+s$  with $s\geq 1$. Let $P_0\in \A$ with $\vert \mu(P_0)\vert=t+s$.
By Lemma \ref{lm_size}, $\max_{P\in\A} \vert\mu (P)\vert\leq 4t$. 

\vskip 0.5cm
\noindent
{\bf Claim$^*$}. $\vert \mu(P)\setminus \mu(P_0)\vert\leq t-1$ for all $P\in\A$. 

Suppose there is a $Q\in\A$ with $\vert \mu(Q)\setminus \mu(P_0)\vert\geq t$. Then $\vert \tau(P_0)\setminus \mu(Q)\vert \leq n-2t-s$. Since $\vert P_0\cap Q\vert\geq n-2t$, by Lemma \ref{lm_pre_size}, $\vert \mu(P_0)\cap \mu(Q)\vert\geq 2s$. Therefore $\vert \mu(Q)\vert=\vert \mu(Q)\setminus \mu(P_0)\vert+\vert \mu(P_0)\cap \mu(Q)\vert\geq t+2s$.
On the other hand, $\vert \mu(Q)\vert\leq \vert \mu(P_0)\vert=t+s$ by the choice of $P_{0}$. This implies that $s\leq 0$, a contradiction. Hence, the claim follows.

By Claim$^*$ and Lemma \ref{lm_technical_1}  (take $W=\mu(P_0)$ and $q=4t$), $\vert \A\vert< n^{t-0.5}$. Note that $\tilde B_{t}\geq \tilde B_{2}=1$ for $t\geq 2$. So, by equation (\ref{eq_s1}),
\begin{align*}
\vert\mathcal F_{2t}\vert &=\sum_{i=0}^{t} \tilde B_{i} { n \choose i}\\
&\geq \tilde B_{t} { n \choose t}\\
&\geq \frac{1 }{t!}\prod_{j=0}^{t-1} \left( n-j\right)\\
&\geq \frac{n^t}{t!2^{t-1}}>n^{t-0.5},
\end{align*}
provided that $n\geq \max\left(\left(t!2^{t-1} \right)^2, 2t-2\right)$. Thus, $|\mathcal{A}| < \vert {\mathcal F}_{2t}\vert$.

Suppose  $\A\subseteq \mathcal{F}_{2t}$. Then $\vert\A\vert\leq \vert \mathcal{F}_{2t}\vert$ and equality holds if and only if $\mathcal{A}={\mathcal F}_{2t}$.
\end{proof}





\begin{lm}\label{lm_compressed_2} For $t\geq 1$, there exists an $n_0=n_0(t)$ such that for all $n\geq n_0$, if $\A\in I(n,n-2t-1)$ and $\A$ is compressed, then
\[ |\mathcal{A}| \leq  \vert {\mathcal F}_{2t+1}(1)\vert.\]
 Moreover, equality holds if and only if $\mathcal{A}={\mathcal F}_{2t+1}(i_0)$ for some $i_0\in [n]$.
\end{lm}

\begin{proof}  Since $t\geq 1$, $\tilde B_{t+1}\geq \tilde B_{2}=1$. Therefore, by equation (\ref{eq_s2}), for all $a\in [n]$,
\begin{align}
|\mathcal{F}_{2t+1}(a)| & = \sum_{i=0}^{t} \tilde B_{i} {n \choose i} + \tilde B_{t+1}{n-1 \choose t}\notag\\
& \geq \tilde B_{t} {n \choose t} + {n-1 \choose t}\notag\\
& = \tilde B_{t} {n \choose t} + \frac{1}{t!}\prod_{j=0}^{t-1} \left (n-1-j \right)\notag\\
& \geq \tilde B_{t} {n \choose t} + \frac{n^t}{t!2^t},\label{eq_s3}
\end{align}
provided that  $n\geq 2t$. 


Suppose $\max_{P\in\A} \vert\mu (P)\vert\leq t$. Then $\vert\mu (P)\cap ([n]\setminus \{1\})\vert\leq t$ for all $P\in\A$. Hence, $\A\subseteq {\mathcal F}_{2t+1}(1)$ and the lemma follows.


Suppose $\max_{P\in\A} \vert\mu (P)\vert=t+s$  with $s\geq 1$. Let $P_0\in \A$ with $\vert \mu(P_0)\vert=t+s$.
By Lemma \ref{lm_size}, $\max_{P\in\A} \vert\mu (P)\vert\leq 4t+2$. 



\vskip 0.5cm
\noindent
{\bf Claim$^{**}$}. If $s\geq 2$, then $\vert \mu(P)\setminus \mu(P_0)\vert\leq t-1$ for all $P\in\A$. 

Suppose there is a $Q\in\A$ with $\vert \mu(Q)\setminus \mu(P_0)\vert\geq t$. Then $\vert \tau(P_0)\setminus \mu(Q)\vert \leq n-2t-s=n-2t-1-(s-1)$. Since $\vert P_0\cap Q\vert\geq n-2t-1$, by Lemma \ref{lm_pre_size}, $P_0$ and $Q$ have at least $(s-1)$ blocks of size at least 2 in common and $\vert \mu(P_0)\cap \mu(Q)\vert\geq 2(s-1)$. Therefore $\vert \mu(Q)\vert=\vert \mu(Q)\setminus \mu(P_0)\vert+\vert \mu(P_0)\cap \mu(Q)\vert\geq t+2(s-1)$.
On the other hand, $\vert \mu(Q)\vert\leq \vert \mu(P_0)\vert=t+s$ by the choice of $P_{0}$. This implies that $s\leq 2$. Since $s\geq 2$, we must have $s=2$, $\vert \mu(Q)\vert=\vert \mu(P_0)\vert=t+2$ and $P_0$ and $Q$ have exactly one block of size 2 in common, say $\{i,j\}$. Since $\A$ is compressed, $s_{ij}(Q)\in\A$. Note that $\mu(s_{ij}(Q))=\mu(Q)\setminus \mu(P_0)$. So, $\vert \mu(s_{ij}(Q))\setminus \mu(P_0)\vert=t$ and $\vert \tau(P_0)\setminus \mu(s_{ij}(Q))\vert = n-2t-2=n-2t-1-1$. Since $\vert P_0\cap s_{ij}(Q)\vert\geq n-2t-1$, by Lemma \ref{lm_pre_size}, $\vert \mu(P_0)\cap \mu(s_{ij}(Q))\vert\geq 2$. This contradicts that $\mu(s_{ij}(Q))=\mu(Q)\setminus \mu(P_0)$.
Hence, the claim follows.

Suppose $s\geq 2$. By Claim$^{**}$ and Lemma \ref{lm_technical_1} (take $W=\mu(P_0)$ and $q=4t+2$), $\vert \A\vert<n^{t-0.5}$ for sufficiently large $n$.
It then follows from equation (\ref{eq_s3}) that 
\begin{align}
\vert \A\vert<n^{t-0.5}<\frac{n^t}{t!2^t}\leq |\mathcal{F}_{2t+1}(1)|, \notag
\end{align}
if $n\geq \left( t!2^t\right)^2$.


Suppose $s=1$. Then $\mu(P)\leq t+1$ for all $P\in\A$. 
Let $P_0,P_1,\dots, P_m\in \A$ be such that for all $ 1 \le i \le m$, we have 
\begin{itemize}
\item[(i)] $\vert \mu(P_i)\vert=t+1$, and 
\item[(ii)] $\vert \mu(P_i)\setminus (\bigcup_{j=0}^{i-1} \mu(P_j))\vert=t$.
\end{itemize}
We may assume that $m$ is the largest integer in the sense that there is no $R\in\A$ with $\vert \mu(R)\vert=t+1$ and $\vert \mu(R)\setminus (\bigcup_{j=0}^{m} \mu(P_j))\vert=t$.

If there is a $Q\in\A$ with $\vert \mu(Q)\setminus (\bigcup_{j=0}^{m} \mu(P_j))\vert\geq t+1$, then $\vert\mu(Q)\vert=t+1$ and $\mu(Q)\cap \mu(P_0)=\varnothing$. 
So, $\vert P_0\cap Q\vert=\vert \tau (P_0)\setminus \mu(Q)\vert=n-2t-2<n-2t-1$, a contradiction. Thus,  $\vert \mu(P)\setminus (\bigcup_{j=0}^{m} \mu(P_j))\vert\leq t$ for all $P\in\A$, and $\A=\A_1\cup \A_2$ where
\begin{align*}
\A_1 &= \left\{ P\in\A\ :\  \left\vert \mu(P)\setminus \left(\bigcup_{j=0}^{m} \mu(P_j)\right)\right\vert\leq t-1 \right\},\\
\\
\A_2 &= \left\{ P\in\A\ :\  \left\vert \mu(P)\setminus \left(\bigcup_{j=0}^{m} \mu(P_j)\right)\right\vert=t\ \textnormal{and}\ \vert\mu(P)\vert=t \right\}.
\end{align*}

Suppose $m\leq t$. Then $\left\vert \bigcup_{j=0}^{m} \mu(P_j)\right\vert\leq \sum_{j=0}^m \vert \mu(P_j)\vert\leq (t+1)^2$.
By Lemma \ref{lm_technical_1} (take $W=\bigcup_{j=0}^{m} \mu(P_j)$ and $q=(t+1)^2$), $\vert \A_1\vert<n^{t-0.5}$ for sufficiently large $n$.
Note that the number of $\mu(R)$ with $R\in \A$ and $\vert \mu(R)\vert=t$ is at most 
$\binom{n}{t}$ and the number of $Q\in\A$ with $\mu(Q)=\mu(R)$ is at most $\tilde B_{t}$. Thus, 
\begin{align*}
\vert \A_2\vert\leq \tilde B_{t}\binom{n}{t}.
\end{align*}
It then follows from equation (\ref{eq_s3}) that
\begin{align}
\vert \A\vert\leq \vert\A_1\vert+\vert\A_2\vert<n^{t-0.5}+\tilde B_{t}\binom{n}{t}<\frac{n^t}{t!2^t}+\tilde B_{t}\binom{n}{t}\leq |\mathcal{F}_{2t+1}(1)|, \notag
\end{align}
if $n\geq \left( t!2^t\right)^2$. 

Suppose $m\geq t+1$. 
\vskip 0.5cm
\noindent
{\bf Claim$^{***}$}. There is a $i_0\in [n]$ with $i_0\in P_i$ for $i=0,1,2,\dots, t+1$. 

Note that if $\mu(P_i)\cap \mu(P_j)=\varnothing$ for $i\neq j$, then $\vert P_{i} \cap P_{j} \vert = \vert \tau(P_i)\setminus \mu(P_j)\vert=n-2t-2<n-2t-1$, a contradiction. 
So, $\mu(P_i)\cap \mu(P_j)\neq \varnothing$ for $i\neq j$. By properties (i) and (ii), we may conclude that $\vert \mu(P_i)\cap \mu(P_j)\vert=1$ for all $i,j$ with $i\neq j$.

Let $\mu(P_1)\cap \mu(P_0)=\{i_0\}$, $\mu(P_i)\cap \mu(P_0)=\{j_1\}$ and $\mu(P_i)\cap \mu(P_1)=\{j_2\}$ where $2\leq i\leq t+1$.
Since $\vert \mu(P_i)\vert=t+1$ and $\vert \mu(P_i)\setminus (\bigcup_{j=0}^{i-1} \mu(P_j))\vert=t$, $j_1=j_2\in\mu(P_1)\cap \mu(P_0)=\{i_0\} $. 
Thus, $i_0\in P_i$ for $i=0,1,2,\dots, t+1$. This completes the proof of the claim.

By Claim$^{***}$, 
\begin{align*}
\mu(P_i)=W_i\cup \{i_0\},
\end{align*}
for $i=0,1,\dots, t+1$ and $W_i\cap W_j=\varnothing$ for $i\neq j$. Suppose $\A\not\subseteq \mathcal{F}_{2t+1} (i_0)$. Then there is a $Q\in\A$ with 
$\vert \mu (Q)\cap ([n]\setminus \{i_0\})\vert=t+1$, i.e., $\vert \mu (Q)\vert=t+1$ and $i_0\notin \mu(Q)$. Note that $\mu(Q)\cap \mu(P_i)\neq \varnothing$ for all $i$, for otherwise, $\vert Q\cap P_i\vert= \vert \tau (Q)\setminus \mu(P_i)\vert= n-2t-2<n-2t-1$. Therefore $\mu(Q)\cap W_i\neq\varnothing$. Since $W_i\cap W_j=\varnothing$ for $i\neq j$, $\mu(Q)$ will have at least $t+2$ elements, a contradiction. Hence, $\A\subseteq \mathcal{F}_{2t+1}(i_0)$, $\vert\A\vert\leq \vert \mathcal{F}_{2t+1}(i_0)\vert$ and  equality holds if and only if $\mathcal{A}={\mathcal F}_{2t+1}(i_0)$.

This completes the proof of the lemma.
\end{proof}

\begin{proof}[Proof of Theorem \ref{thm_main}] If $r=2t$, then the theorem follows from Lemma \ref{lm_compressed_1}. Suppose $r=2t+1$. By repeatedly applying the splitting operations, we eventually obtain a compressed family $\A^{*} \in I(n,n-2t-1)$ with $|\A^{*}|=|\A|$ (Lemma \ref{lm_P2}). It then follows from Lemma \ref{lm_compressed_2} that 
$|\A|=|\A^{*}|\leq \vert {\mathcal F}_{2t+1}(1)\vert$ and equality holds if and only if $\A^{*}={\mathcal F}_{2t+1}(i_0)$ for some $i_0\in [n]$. By Theorem \ref{thm_undo}, we may conclude that $\A^{*}={\mathcal F}_{2t+1}(i_0)$ implies that $\A={\mathcal F}_{2t+1}(i_0)$. This completes the proof of Theorem \ref{thm_main}.
\end{proof}

\section*{Acknowledgments}	
We would like to thank Peter Frankl for suggesting us to look at Theorem \ref{thm_Deza_Frankl}, and the anonymous referee for reading our paper. This project was supported by the Frontier Science Research Cluster, University of Malaya (RG367-15AFR).


\begin{thebibliography}{99}

\bibitem{AK} R. Ahlswede and L. H. Khachatrian,  The complete intersection theorem for systems of finite sets, {\em European J. Combin.} {\bf 18}  (1997), 125--136.

\bibitem{AK2} R. Ahlswede and L.H. Khachatrian, The diametric theorem in Hamming spaces -- Optimal anticodes, {\em Adv. in Appl. Math.} {\bf 20} (1998), 429--449.

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

\bibitem{B} P. Borg, Extremal t-intersecting sub-families of hereditary families, {\em J. London Math. Soc.} {\bf 79} (2009), 167--185.

\bibitem{B2} P. Borg, On t-intersecting families of signed sets and permutations, Discrete
Math. {\bf 309} (2009), 3310--3317.

\bibitem{B3} P. Borg and F.C. Holroyd, The Erdos-Ko-Rado property of various graphs containing singletons, {\em Discrete Math.} {\bf 309} (2009), 2877--2885.

\bibitem{BH} F. Brunk and S. Huczynska, Some Erdos-Ko-Rado theorems for injections, {\em European J. Combin.} {\bf 31} (2010), 839--860.

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


\bibitem{CP} A. Chowdhury and B. Patk\'os, Shadows and intersections in vector spaces, {\em J. Combin. Theory Ser. A} {\bf 117} (2010), 1095--1106.

\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 Journal of the American Society} {\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{Frankl0} P. Frankl, On intersecting families of finite sets, {\em J. Combin. Theory Ser. A} {\bf 24} (1978), 146--161.

\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{FF} P. Frankl and Z. F{\" u}redi, Nontrivial
intersecting families, {\em J. Combin. Theory Ser. A} {\bf 41}
(1986), 150--153.

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

\bibitem{FW} P. Frankl and R.M. Wilson, The Erd{\H o}s-Ko-Rado theorem for vector spaces, {\em J. Combin. Theory Ser. A} {\bf 43} (1986) 228--236.

\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{HS} A.J.W. Hilton and C.L. Spencer, A graph-theoretical generalisation of Berge’s analogue of the Erdos-Ko-Rado theorem, Trends in Graph Theory, Birkhauser Verlag,
Basel, Switzerland (2006), 225--242.

\bibitem{HST} F.C. Holroyd, C. Spencer and J. Talbot, Compression and Erdos-Ko-Rado graphs, {\em Discrete Math.} {\bf 293} (2005), 155--164.

\bibitem{HT} F.C. Holroyd and J. Talbot, Graphs with the Erdos-Ko-Rado property, {\em Discrete Math.} {\bf 293} (2005), 165--176.


\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 {Kee}  P. Keevash, Shadows and intersections: Stability and new proofs, Adv. Math. {\bf 218} (2008) 1685--1703.

\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, {\em J. Combin. Theory Ser. A} {\bf 120} (2013), 1508--1520.

\bibitem{Ku_Wong2} C. Y. Ku and K. B. Wong, On cross-intersecting families of set partitions, {\em Electron. J. Combin.} {\bf 19}(4) (2012), \#49.

\bibitem{Ku_Wong3} C. Y. Ku and K. B. Wong, On $r$-cross intersecting families of sets, {\em Far East J. Math. Sci.} {\bf 75} (2013), 295--300.

\bibitem{Ku_Wong4} C. Y. Ku and K. B. Wong, An analogue of the Erd{\H o}s-Ko-Rado theorem for weak compositions, {\em Discrete Math.} {\bf 313} (2013) 2463--2468.

\bibitem{Ku_Wong5} C. Y. Ku and K. B. Wong, On $r$-cross $t$-intersecting families for weak compositions, to appear in {\em Discrete Math.}.

\bibitem{Ku_Wong6} C. Y. Ku and K. B. Wong, An Analogue of the Hilton-Milner Theorem  for weak compositions, to appear in {\em B. Korean Math. Soc.}

\bibitem{Ku_Wong7} C. Y. Ku and K. B. Wong, An Erd{\H o}s-Ko-Rado theorem for permutations with fixed number of cycles, {\em Electron. J. Combin.} {\bf 21}(3) (2014), \#P3.16. 

\bibitem{Ku_Wong8} C. Y. Ku and K. B. Wong, An intersecting theorem for integer sequence, preprint.

\bibitem{Ku_Wong9} C. Y. Ku and K. B. Wong, A Frankl-Hilton-Milner type of theorem for permutations with fixed number of cycles, preprint.

\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{LW} Y.-S. Li and Jun Wang, Erd{\H o}s-Ko-Rado-type theorems for colored sets, {\em Electron. J. Combin.} {\bf 14} (2007) \#R1.

\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{Moon} A. Moon, An analogue of the Erd{\H o}s-Ko-Rado theorem for the Hamming schemes $H(n,q)$, {\em J. Combin. Theory Ser. A} {\bf 32}(3) (1982), 386--390.

\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{WZ0} J. Wang and H. Zhang, Cross-intersecting families and primitivity of symmetric systems, {\em J. Combin. Theory Ser. A} {\bf 118} (2011), 455--462.


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

\bibitem{W} R. Woodroofe, Erdos-Ko-Rado theorems for simplicial complexes, {\em J. Combin. Theory Ser. A}  {\bf 118} (2011), 1218--1227.


\end{thebibliography}


\end{document}











\end{document} 