\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}(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 \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