\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amssymb, amsmath, amsthm}
\usepackage{graphicx}
\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}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\newcommand{\A}{\mathcal{A}}
\newcommand{\F}{\mathcal{F}}


\title{An Erd{\H o}s-Ko-Rado theorem for permutations with fixed number of cycles}



\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{}{}\\
\small Mathematics Subject Classifications: 05D05}

\begin{document}

\maketitle


\begin{abstract}
 Let $S_{n}$ denote the set of permutations of $[n]=\{1,2,\dots, n\}$. For a positive integer $k$, define $S_{n,k}$ to be the set of all permutations of $[n]$ with exactly $k$ disjoint cycles, i.e.,
\[ S_{n,k} = \{\pi \in S_{n}: \pi = c_{1}c_{2} \cdots c_{k}\},\] 
where $c_1,c_2,\dots ,c_k$ are disjoint cycles. The size of $S_{n,k}$ is given by $\left [ \begin{matrix}n\\ k \end{matrix}\right]=(-1)^{n-k}s(n,k)$, where $s(n,k)$ is the  Stirling number of the first kind. A family $\mathcal{A} \subseteq S_{n,k}$ is said to be $t$-{\em cycle-intersecting} if any two elements of $\mathcal{A}$ have at least $t$ common cycles. In this paper, we show that, given any positive integers $k,t$ with $k\geq t+1$, if $\mathcal{A} \subseteq S_{n,k}$ is $t$-cycle-intersecting and $n \ge n_{0}(k,t)$ where $n_{0}(k,t) = O(k^{t+2})$, then 
\[ |\mathcal{A}| \le \left [ \begin{matrix}n-t\\ k-t \end{matrix}\right],\]
with equality if and only if $\mathcal{A}$ is the stabiliser of $t$ fixed points.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} $t$-intersecting family; Erd{\H o}s-Ko-Rado; permutations; Stirling number of the first kind
\end{abstract}




\section{Introduction}

Let $[n]=\{1, \ldots, n\}$, and let ${[n] \choose 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{theorem}[Erd{\H o}s, Ko, and Rado \cite{EKR}, Frankl \cite{Frankl}, Wilson \cite{Wilson}]\label{EKR} Suppose $\mathcal{A} \subseteq {[n] \choose 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 {n-t \choose k-t}.\notag
\end{equation}
Moreover, if $n>(k-t+1)(t+1)$ then equality holds if and only if $\mathcal{A}=\{A\in {[n] \choose k}\ :\ T\subseteq A\}$ for some $t$-set $T$.
\end{theorem}

Later, Ahlswede and Khachatrian \cite{AK} 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$. 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 (see \cite{B, B2,B3, BH, CK, CP, DF, E, EFP, GM, HS, HST, HT, HK, Kee, KL, KR, KW, Ku_Wong, Ku_Wong2, Ku_Wong3, Ku_Wong3, Ku_Wong4, LM, LW, ML, MP, Moon, WZ, W}). 

Let $S_{n}$ denote the set of permutations of $[n]$. A family of $S_{n}$ is said to be $t$-{\em intersecting} if  any two permutations in the family agree in at least $t$ points. In 1977, Deza and Frankl \cite{DF} proved that a $1$-intersecting family has size at most $(n-1)!$. Much later, it was proved by several authors via different approaches that the only families achieving the maximum size are the cosets of stabilisers of a point (see \cite{CK,GM,LM,WZ}). More recently, Ellis, Friedgut and Pilpel \cite{EFP} have settled an old conjecture of Deza and Frankl regarding an analogue of the Erd{\H o}s-Ko-Rado theorem for permutations. In particular, they showed that for sufficiently large $n$ depending on $t$, a $t$-intersecting family $\A$ of $S_{n}$ has size at most $(n-t)!$, with equality if and only if $\A$ is a coset of the stabilizer of $t$ points. Their proof uses spectral methods and representations of the symmetric group. 

The concept of $t$-cycle intersection for permutations was introduced by Ku and Renshaw \cite{KR}. A family $\mathcal{A}$ of permutations is $t$-{\em cycle-intersecting} if any two permutations in $\mathcal{A}$, when written in their cycle decomposition form, have at least $t$ cycles in common. Obviously, if $\mathcal{A}$ is $t$-cycle-intersecting, it is $t$-intersecting but the converse is not true. 



In this paper, we are interested in the $t$-cycle-intersection problem for permutations that have a prescribed number of cycles. For a positive integer $k$, define $S_{n,k}$ to be the set of all permutations of $[n]$ with exactly $k$ disjoint cycles, i.e.,
\[ S_{n,k} = \{\pi \in S_{n}: \pi = c_{1}c_{2} \cdots c_{k}\},\] 
where $c_1,c_2,\dots ,c_k$ are disjoint cycles. It is well known that the size of $S_{n,k}$ is given by $\left [ \begin{matrix}n\\ k \end{matrix}\right]=(-1)^{n-k}s(n,k)$, where $s(n,k)$ is the {\em Stirling number of the first kind}.

We shall use the following notations:
\begin{itemize}
\item[\textnormal{(a)}] Let $N(c)=\{a_1,a_2,\dots, a_l\}$ denote the set of points occurring in the cycle $c=(a_1,a_2,\dots, a_l)$;
\item[\textnormal{(b)}] Let $M(\pi)=\{c_1,c_2,\dots, c_k\}$ denote the set of cycles in the cycle decomposition of the permutation $\pi=c_1c_2\dots c_k\in S_{n,k}$.
\end{itemize}


Thus, a family $\mathcal{A} \subseteq S_{n,k}$ is $t$-cycle-intersecting if $\vert M(\pi_1)\cap M(\pi_2)\vert\geq t$ for any $\pi_1,\pi_2\in \A$.


\begin{theorem}\label{thm_main} Suppose $k,t$ are positive integers with $k\geq t+1$. There exists a function $n_0(k,t)=O(k^{t+2})$ such that  if $\mathcal{A} \subseteq S_{n,k}$ is $t$-cycle-intersecting and $n \ge n_{0}(k, t)$, then 
\[ |\mathcal{A}| \le \left [ \begin{matrix}n-t\\ k-t \end{matrix}\right],\]
with equality if and only if $\mathcal{A}$ is the stabiliser of $t$ fixed points, i.e. $\A$ consists of all permutations in $S_{n,k}$ with some $t$ fixed cycles of length one.
\end{theorem}




\section{Stirling number revisited}

The unsigned Stirling number $\left [ \begin{matrix}n\\ k \end{matrix}\right]$ satisfies the recurrence relation
\begin{equation}\label{eq_recurrence}
\left [ \begin{matrix}n\\ k \end{matrix}\right]=\left [ \begin{matrix}n-1\\ k-1 \end{matrix}\right]+(n-1)\left [ \begin{matrix}n-1\\ k \end{matrix}\right],
\end{equation}
with initial conditions $\left [ \begin{matrix}0\\ 0 \end{matrix}\right] = 1$ and $\left [ \begin{matrix}n\\ 0 \end{matrix}\right] = \left [ \begin{matrix} 0\\ k \end{matrix}\right] = 0$,  $n > 0$. Note that $\left [ \begin{matrix}n\\ n\end{matrix}\right]=1$, and $\left [ \begin{matrix}n\\ 1\end{matrix}\right]=(n-1)!$.

It is well-known that the sequence $\left[\begin{matrix} n \\ k \end{matrix} \right]$, $1 \le k \le n$, is {\em strongly log-concave} (SLC):
\begin{eqnarray}
\left[\begin{matrix} n \\ k \end{matrix} \right]^{2} & > & \left[ \begin{matrix}
n \\
k+1\\
\end{matrix} \right] \left[ \begin{matrix}
n \\
k-1
\end{matrix} \right],~~\textnormal{for}~~2 \le k \le n-1.
\end{eqnarray}

Using Newton's inequality for symmetric functions, Lieb \cite{Lieb} obtained the following inequality which implies the SLC property.


\begin{theorem}[Lieb \cite{Lieb}]
The following sequences are strictly decreasing for any $n=3,4, \ldots$:
\begin{eqnarray}
\frac{k-1}{n-k+1}\left[\begin{matrix}
n \\
k
\end{matrix} \right] \Big/ \left[\begin{matrix}
n \\
k-1
\end{matrix} \right], ~~\textnormal{for}~2 \le k \le n.\label{A}
\end{eqnarray}
\end{theorem}

\begin{corollary}\label{C1}
The following inequalities are obtained by considering the ends of the sequence in (\ref{A}):
\begin{eqnarray}
\frac{n-k+1}{(k-1)(n-1)} H_{n-1}& \ge & \left[\begin{matrix}
n \\
k
\end{matrix} \right] \Big/ \left[\begin{matrix}
n \\
k-1
\end{matrix} \right] \ge \frac{2(n-k+1)}{(k-1)n}, ~~\textnormal{for}~2 \le k \le n,\label{B}
\end{eqnarray}
where $H_{m} = \sum_{i=1}^{m} \frac{1}{i}$ is the $m$-th Harmonic number.
\end{corollary}

\section{Proof of Theorem \ref{thm_main}}

We may assume that $\A$ is maximally $t$-intersecting  (with respect to inclusion) .


Suppose $k=t+1$. Since $\A$ is $t$-intersecting, there are $\pi_1,\pi_2\in\A$ such that
\begin{align}
\pi_1&=c_1c_2\dots c_td_1\notag\\
\pi_2&=c_1c_2\dots c_td_2\notag
\end{align}
where $c_1,\dots,c_t,d_1$ are disjoint cycles, $d_2\neq d_1$ and $N(d_2)=N(d_1)$. Suppose there is a $\pi\in\A$ with $c_{i_0}\notin\ M(\pi)$ for some $i_0$. Then $d_1,d_2\in M(\pi)$. But this is impossible as $N(d_1)=N(d_2)$. Hence,
\begin{equation}
\A= \{ \pi\in S_{n,k}\ :\ c_i\in M(\pi)\ \ \textnormal{for}\ \ i=1,2,\dots, t\},\notag
\end{equation}
since $\A$ is maximally $t$-intersecting. Let  $P=\bigcup_{i=1}^t N(c_i)$. Then
\begin{equation}
\vert\A\vert=\left [ \begin{matrix}n-\vert P\vert\\ 1 \end{matrix}\right]\leq \left [ \begin{matrix}n-t\\ 1 \end{matrix}\right],\notag
\end{equation}
with equality if and only if $\vert N(c_i)\vert=1$ for $i=1,2\dots,t$, i.e., $\A$ is the stabilizer of at least $t$ fixed points. Now, if $n\geq t+2$, then  $\A$ is the stabilizer of $t$ fixed points.







From now on, we may suppose that $k \ge t+2$ and that $\mathcal{A} \subseteq S_{n,k}$ is a $t$-intersecting family of maximum size. Assuming that $\mathcal{A}$ is not the stabilizer of $t$ points, we shall prove that $|\mathcal{A}| < \left[ \begin{matrix}
n-t \\
k-t
\end{matrix} \right]$.

Pick any $\pi \in \mathcal{A}$ and assume that $\pi=c_{1}c_{2} \cdots c_{k}$, where $k \ge t+1$. Let $T=\{c_1,\dots, c_t\}$. We set
\begin{equation}
\A(T)=\{\pi\in\A\ :\ T\subseteq M(\pi)\}.\notag
\end{equation} 

If  $\mathcal{A} \subseteq \A(T)$, then at least one of the $c_{i}$, $1 \le i \le t$,  must be of size greater than $1$ (otherwise $\A$ will be the stabilizer of $t$ points). Thus, in this case,  $|\A| \le |\A(T)| \le \left[ \begin{matrix}
n-\sum_{i=1}^{t} |N(c_{i})| \\
k- t \end{matrix}\right] <  \left[ \begin{matrix}
n-t  \\
k- t \end{matrix}\right]$, where the last inequality follows from (\ref{eq_recurrence}).

Therefore, there must be a permutation $\sigma \in \mathcal{A}$ that does not contain all the $t$-cycles in $T$. Every permutation in the subfamily $\mathcal{A}(T)$ must $t$-intersect $\sigma$, and so it must contain an additional cycle from $\sigma$ that is different from those in $T$. There are at most $k-1$ ways to pick such a cycle from $\sigma$ since at least one cycle from $\sigma$ would contain elements from the cycles in $T$. Consequently, the maximum size of the subfamily $\A(T)$ is at most
\[  (k-1) \left[\begin{matrix}
n-t-1 \\
k-t-1
\end{matrix} \right].\]
Since every permutation in $\A$ must $t$-intersect $\pi$, we deduce that
\[ |\A|   = \left\vert \bigcup_{T \subseteq M(\pi)} A(T)  \right\vert \le {k \choose t} (k-1) \left[\begin{matrix}
n-t-1 \\
k-t-1
\end{matrix} \right].\]
Since we can write 
\[ \left [ \begin{matrix}n-t\\ k-t \end{matrix}\right]=\left [ \begin{matrix}n-t-1\\ k-t-1 \end{matrix}\right]+(n-t-1)\left [ \begin{matrix}n-t-1\\ k-t \end{matrix}\right] \]
it remains to show that
\begin{eqnarray}
 {k \choose t} (k-1) & < & 1 + (n-t-1)  \left [ \begin{matrix}n-t-1\\ k-t \end{matrix}\right]  \Big/  \left[\begin{matrix}
n-t-1 \\
k-t-1
\end{matrix} \right].
\end{eqnarray}
By Corollary \ref{C1}, it is enough to show that
\begin{eqnarray}
 {k \choose t} (k-1) & < & 1 + (n-t-1) \frac{2(n-k)}{(k-t-1)(n-t-1)}\end{eqnarray}
which implies that
\[ n > k + \frac{(k-t-1)}{2} \left( (k-1){k \choose t}-1\right). \]

This concludes the proof of Theorem \ref{thm_main}.





\section{Dependence of $n$ on $k$ and $t$}


For $0 \le i \le  \lfloor (k-t)/2 \rfloor$, define the family
\[ \mathcal{F}_{i} = \{ \pi \in S_{n,k}: \left\vert M(\pi) \cap \{(1), (2), \ldots, (t+2i)\}\right\vert \ge t+i \}. \]
These families are analogous to those first defined by Frankl for set systems:
\[ \left\{ F \in {[n] \choose k}: |F \cap [t+2i]| \ge t+i\right\}. \]
Clearly, $\mathcal{F}_{i}$ is $t$-cycle-intersecting for $0 \le i \le \lfloor (k-t)/2 \rfloor$. Note that $\mathcal{F}_{0}$ is the stabiliser of $t$ fixed points. Therefore, Theorem \ref{thm_main} says that if $n \ge n_{0}(k,t)$, then the only largest $t$-cycle-intersecting families of $S_{n,k}$ are those isomorphic to $\mathcal{F}_{0}$. The following proposition shows that the condition $n \ge n_{0}(k,t)$  cannot be replaced by $n \ge n_{0}(t)$ or $k \ge k_{0}(t)$.


\begin{proposition}
Let $r$ be a fixed positive integer. If $k=n-r$ then $|\mathcal{F}_{1}| > |\mathcal{F}_{0}|$ for all sufficiently large $n$ in terms of $r$, regardless of the value of $t$.
\end{proposition}



\begin{proof}
Note that
\[ |\mathcal{F}_{1}| = {t+2 \choose t+1} \left[ \begin{matrix}
n-t-1 \\
k-t-1 \\
\end{matrix} \right] - (t+1) \left[ \begin{matrix}
n-t-2 \\
k-t-2 
\end{matrix} \right], ~~|\mathcal{F}_{0}| = \left[ \begin{matrix}
n-t \\
k-t \\
\end{matrix} \right]. \]
It follows that
\begin{eqnarray}
|\mathcal{F}_{1}|-|\mathcal{F}_{0}| & = & { t+2 \choose t+1}\left[ \begin{matrix}
n-t-1 \\
k-t-1 \\
\end{matrix} \right] - (t+1) \left[ \begin{matrix}
n-t-2 \\
k-t-2 
\end{matrix} \right] \notag \\
& & - \left(\left[ \begin{matrix}
n-t-1 \\
k-t-1 \\
\end{matrix} \right] + (n-t-1) \left[ \begin{matrix}
n-t-1 \\
k-t \\
\end{matrix} \right] \right) \notag \\
& = & (t+1) \left[ \begin{matrix}
n-t-1 \\
k-t-1 \\
\end{matrix} \right] - (t+1) \left[ \begin{matrix}
n-t-2 \\
k-t-2 
\end{matrix} \right] - (n-t-1) \left[ \begin{matrix}
n-t-1 \\
k-t \\
\end{matrix} \right] \notag \\
& = & (t+1)(n-t-2) \left[ \begin{matrix} n-t-2 \\k-t-1\end{matrix} \right] - (n-t-1) \left[\begin{matrix}n-t-2 \\k-t-1 \end{matrix} \right] \notag \\
& & -(n-t-1)(n-t-2)\left[\begin{matrix}n-t-2 \\k-t\end{matrix} \right] \notag \\
& = & \left(t(n-t-1)-(t+1)\right) \left[ \begin{matrix} n-t-2 \\k-t-1\end{matrix} \right]  -(n-t-1)(n-t-2)\left[\begin{matrix}n-t-2 \\k-t\end{matrix} \right]. \label{F1}
\end{eqnarray}
To show that the right-hand side of (\ref{F1}) is greater than $0$, we shall prove the inequality
\begin{eqnarray}
\left[\begin{matrix}n-t-2 \\k-t\end{matrix} \right] \Big/ \left[ \begin{matrix} n-t-2 \\k-t-1\end{matrix} \right] & < & \frac{ \left(t(n-t-1)-(t+1)\right) }{(n-t-1)(n-t-2)}.
\end{eqnarray}
By Corollary \ref{C1},
\begin{eqnarray}
\left[\begin{matrix}n-t-2 \\k-t\end{matrix} \right] \Big/ \left[ \begin{matrix} n-t-2 \\k-t-1\end{matrix} \right] & \le & \frac{n-k-1}{(k-t-1)(n-t-3)}H_{n-t-3} \notag \\
& < & \frac{n-k-1}{(k-t-1)(n-t-3)}(1 + \ln (n-t-3)) \notag \\
& = & \frac{r-1}{(n-r-t-1)(n-t-3)}(1 + \ln (n-t-3)). \label{F2}
\end{eqnarray}
Clearly, the right-hand side of (\ref{F2}) is now less than $\frac{ \left(t(n-t-1)-(t+1)\right) }{(n-t-1)(n-t-2)}$ for sufficiently large $n$ in terms of $r$, regardless of the value of $t$.
\end{proof}







\section{Concluding remarks}

The technique used in the proof of the main theorem of this paper is the {\em kernel method} introduced by Hajnal and Rothschild \cite{HR}. The limitation of this method is that it only works from some threshold. This method usually yields short and easy proofs but rarely gives the exact range of results. We were rather cavalier in our estimates of the function $n_{0}(k,t)$. A better bound is perhaps possible by using a more delicate approximation of the unsigned Stirling number of the first kind. We believe that the bound $n_{0}(k,t)=O(k^{t+2})$ is not optimal, and that a different technique similar to the shifting operation and compression for set systems may be needed to derive the exact optimal bound for $n$. 


In the original EKR theorem (Theorem \ref{EKR}), the condition $n \ge 2k$ is optimal for $t=1$ since taking all $k$-subsets of $[n]$ with $n=2k-1$ yields a $1$-intersecting family of $k$-subsets which has size greater than ${n-1 \choose k-1} = { 2k-2 \choose k-1}$. A similar construction for permutations can be given as follows. Suppose $n=2k-3$, where $k \ge 4$. Consider the family $\A \subseteq S_{2k-3,k}$ which consists of permutations with exactly $k-1$ fixed points and one cycle of length $n-(k-1) = k-2$. Since $k-1> n/2$, any two permutations of $\A$ must intersect in at least one fixed point, so $\A$ is $1$-cycle-intersecting.  The size of $\A$ is given by
\[ \vert \A \vert  = {2k-3 \choose k-1} (k-3)!, \]
which is greater than $|\F_{0}|$ when $k=4$. Unfortunately, our numerical computation suggests that this size is smaller than $|\F_{0}| = \left[\begin{matrix} n-1 \\ k-1 \end{matrix} \right] = \left[\begin{matrix} 2k-4 \\ k-1 \end{matrix} \right]$ all $k \ge 5$.


It is worth noting that the idea in the above construction is that if $n$ and $k$ are close and $t$ is small, then all permutations in $S_{n,k}$ will be $t$-cycle-intersecting. In general, take $k=n-r$ for some $r$. By the pigeonhole principle, every permutation in $S_{n,k}$ has at least $n-2r$ fixed points. If $n-4r \ge t$, then every two permutations in $S_{n,k}$ must intersect in at least $t$ fixed points. By substituting $r=n-k$ and $t=1$, the condition $n-4r \ge t$ becomes $n \le \frac{4k-1}{3}$. We conjecture that the optimal lower bound for $n$ in Theorem \ref{thm_main} for $t=1$ is $O(4k/3)$.

\section*{Acknowledgments}	
We would like to thank the anonymous referee for the comments that had helped
us make several improvements to this paper, particularly for pointing out the kernel method which has simplified our original proof. This project was supported by the Advanced Fundamental Research Cluster, University of Malaya (UMRG RG238/12AFR). 




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

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

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

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

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

\bibitem{BH} F.~Brunk and S.~Huczynska, Some Erd{\H o}s-Ko-Rado theorems for injections, {\em Eur. J. Comb.} {\bf 31} (2010), 839--860.

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

\bibitem{CP} A.~Chowdhury and B.~Patk\'os, Shadows and intersections in vector spaces, {\em J. Comb. 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. Comb. Theory, Ser. A}  {\bf 22} (1977), 352--360.

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

\bibitem{EFP} D.~Ellis, E.~Friedgut and H.~Pilpel, Intersecting families of permutations, {\em J. Am. 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 Q. J. Math., Oxf. II. Ser.} {\bf 12} (1961), 313--320.

\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{FW} P.~Frankl and R.~M. Wilson, The Erd{\H o}s-Ko-Rado theorem for vector spaces, {\em J. Comb. 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 Eur. J. Comb.} {\bf 30} (2009), 404--414.

\bibitem{HR} A.~Hajnal and B.~Rothschild, A generalisation of the Erd{\H o}s-Ko-Rado theorem on finite set systems, {\em J. Comb. Theory, Ser. A} {\bf 15}  (1973), 359--362.

\bibitem{HS} A.~J.~W. Hilton and C.~L. Spencer, A graph-theoretical generalisation of Berge's analogue of the Erd{\H o}s-Ko-Rado theorem, {\em Trends in Graph Theory, Birkhauser Verlag, Basel, Switzerland} (2006), 225--242.

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

\bibitem{HT} F.~C. Holroyd and J.~Talbot, Graphs with the Erd{\H o}s-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. Comb. Theory, Ser. A} {\bf 118}
(2011), 829--841.

\bibitem {Kee}  P.~Keevash, Shadows and intersections: Stability and new proofs, {\em 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. Comb. 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. Comb.} {\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. Comb. 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. Comb.} {\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{LM} B.~Larose and C.~Malvenuto, Stable sets of maximal size in Kneser-type graphs, {\em Eur. J. Comb.} {\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. Comb.} {\bf 14} (2007) \#R1.

\bibitem{Lieb} E.~H. Lieb, Concavity properties and a generating functions of Stirling numbers, {\em J.
Comb. Theory} {\bf 5} (1968), 203--206.

\bibitem{ML} K.~Meagher and L.~Moura, Erd{\H o}s-Ko-Rado theorems for uniform set-partition systems, {\em Electron. J. Comb.} {\bf 12} (2005), \#R40.

\bibitem{MP} K.~Meagher and A.~Purdy, An Erd{\H o}s-Ko-Rado theorem for multisets, {\em Electron. J. Comb.} {\bf  18}  (2011),  \#P220.

\bibitem{Moon} A.~Moon, An analogue of the Erd{\H o}s-Ko-Rado theorem for the Hamming schemes $H(n,q)$, {\em J. Comb. Theory, Ser. A} {\bf 32}(3) (1982), 386--390.


\bibitem{WZ} J. Wang and S. J. Zhang, An Erd{\H o}s-Ko-Rado-type theorem in Coxeter groups, {\em Eur. J. Comb.} {\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.

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


\end{thebibliography}

\end{document}