\documentclass[letterpaper,12pt]{article}

\usepackage{enumerate}
\usepackage{e-jc}
\specs{P4.41}{22(4)}{2015}


% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\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}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins



% declare theorem-like environments
\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}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Stability for intersecting families in $PGL(2,q)$}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Rafael Plaza\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small University of Delaware\\[-0.8ex] 
\small Newark, Delaware, U.S.A.\\
\small\tt plaza@udel.edu\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{July 11, 2015}{Dec 1, 2015}{Dec 23, 2015}\\
\small Mathematics Subject Classifications: 05C88, 05C89}




\begin{document}


\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{abstract}
We consider the action of the $2$-dimensional projective general linear group $PGL(2,q)$ on the projective line $PG(1,q)$. A subset $S$ of $PGL(2,q)$ is said to be an intersecting family if for every $g_1,g_2 \in S$, there exists $\alpha \in PG(1,q)$ such that $\alpha^{g_1}= \alpha^{g_2}$. It was proved by Meagher and Spiga that the intersecting families of maximum size in $PGL(2,q)$ are precisely the cosets of point stabilizers.  We prove that if an intersecting family $S \subset PGL(2,q)$ has size close to the maximum then it must be ``close" in structure to a coset of a point stabilizer. This phenomenon is known as stability.  We  use this stability result proved here to show that if the size of $S$ is close enough to the maximum then $S$ must be contained in a coset of a point stabilizer.
\end{abstract}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}

The Erd\H{o}s-Ko-Rado (EKR) theorem is a classical result in extremal set theory. It states that if $k < n/2$, an intersecting family of $k$-subsets of $[n]=\{1,2,\ldots, n\}$ has size at most ${n-1 \choose k-1}$; equality holds if and only if the family consists of all $k$-subsets containing a fixed element from $[n]$. Intersecting families of maximum size are called {\it extremal families}. In \cite{Frankl2}, Frankl proved that these extremal families are not only unique, but also stable: Any intersecting family of size close to the maximum is ``close'' in structure to an extremal family. In this paper, we focus on an analogue of these results for permutations groups, in particular, to the natural right action of $PGL(2,q)$ on the projective points of $PG(1,q)$, where $q$ is a prime power. 

Let $\Omega$ be a finite set and $G$ a finite group acting on $\Omega$. A subset $S$ of $G$ is said to be an {\it intersecting family} if for every $g_1,g_2 \in S$ there exists an element $\alpha \in \Omega$ such that $\alpha^{g_1}= \alpha^{g_2}$. Like in the original EKR-problem, we call intersecting families of maximum size {\it extremal families}. Moreover, intersecting families whose sizes are close to the maximum are called {\it almost extremal families}.

The following problems about intersecting families in $G$ are considered to be the basic problems in EKR theory.

\begin{enumerate}[I]
\item (Upper Bound) What is the maximum size of an intersecting family?
\item (Uniqueness) What is the structure of extremal families?
\item (Stability) Are almost extremal families similar in structure to the extremal ones?
\end{enumerate}

The above three problems were solved for the symmetric group $S_n$.  Indeed, Deza and Frankl \cite{Frankl1} proved that the maximum size of an intersecting family in $S_n$ is $(n-1)!$. Moreover, they conjectured that the cosets of points stabilizers are the only extremal families. This conjecture turned out to be rather harder to prove than one might expect. It was first proved by Cameron and Ku \cite{Cameron1}, and independently by Larose and Malvenuto \cite{Larose1}. Finally, the stability of extremal families in $S_n$ was settled by Ellis \cite{Ellis5}, who  proved that for any $\epsilon >0$ and $n > N(\epsilon)$, any intersecting family of size at least $(1-1/e +\epsilon) (n-1)!$ must be strictly contained in an extremal family.
 
In \cite{Karen1}, Meagher and Spiga studied Problems I and II for the group $G_q:=PGL(2,q)$ acting on the set of points of the projective line $PG(1,q)$. These authors proved that the maximum size of an intersecting family in $G_q$ is $q(q-1)$. Furthermore, they also solved the uniqueness problem: Every extremal family in $G_q$ is a coset of a point stabilizer. In this paper, we prove that extremal families in $G_q$ are also stable, like their counterparts in the symmetric group. That is, an almost extremal family in $G_q$ must be close in structure to a coset of a point stabilizer. We make this statement explicit in the following theorem.

\begin{theorem}\label{teo1}
There exists an absolute constant $C_0$ such that the following holds. Let $S \subset G_q$ be an intersecting family with  $|S|= (1- \delta)q(q-1)$, where $0 \leq \delta \leq 1/2$. Then there exists a coset of a point stabilizer $T \subset G_q$ such that 
\[
|S \triangle T|  \leq C_0 \left(\delta^{1/2} + \frac{1}{q+1}\right) |S|,\] 
where $\triangle$ is the symmetric difference of sets.
\end{theorem} 

Using Theorem \ref{teo1} and some properties of intersecting families in $G_q$ we get the following stronger result on almost extremal families in $G_q$.

\begin{theorem}\label{teo2}
There exists an absolute constant $\delta_0>0$ such that the following holds. If $S \subset G_q$ is an intersecting family with $|S| \geq (1-\delta_0) q(q-1)$, then $S$ is contained within a coset of a point stabilizer in $G_q$.
\end{theorem}

Theorem $2$ is a direct analogue of the Cameron-Ku conjecture proved by Ellis in \cite{Ellis5}.

The main tools in this paper are the eigenvalue method and analysis of Boolean functions on $G_q$.  The eigenvalue method was introduced by L\'{o}vasz \cite{Lo1} as a new way to prove for the EKR-theorem. Since then, it has been used several times to prove analogues of the EKR theorem \cite{Filmus, Karen4, Karen1, Wilson1}.  The analysis of Boolean functions on finite groups has been an active research area especially in computer science. A lot of work has been done in recent years to characterize Boolean functions whose Fourier transforms are highly concentrated on some irreducible representations. Friedgut, Kalai and Naor \cite{Friedgut2} proved that a Boolean function on $\mathbb{Z}_2^n$ whose Fourier transform is close to being concentrated on the first two levels, must be close to a dictatorship (a function determined by just one coordinate). Furthermore, similar results have been obtained for other abelian groups \cite{Alon1,Hatami1}. Recently, Ellis, Filmus and Friedgut \cite{Ellis2} showed that similar results can be obtained for the symmetric group $S_n$. Specifically, they proved that if the Fourier transform of a Boolean function $f$ is highly concentrated on the first two irreducible representations of $S_n$ and $\frac{1}{n!} \sum_{x \in S_n} f(x) = O(\frac{1}{n})$ then $f$ must be close to a union of cosets of points stabilizers.  

The proof of Theorem \ref{teo1} is divided into two parts. First, we prove that the Fourier transform of the characteristic function of the almost extremal families are highly concentrated on two irreducible representations of $G_q$. Second, we use this Fourier characterization of almost extremal families to get structural information. In particular, we note that most of the ideas used in \cite{Ellis2},  can be used to characterize Boolean functions on $G_q$ whose Fourier transforms are highly concentrated on the trivial and standard representations of $G_q$. This partially answers a question of Ellis, Filmus and Friedgut in \cite{Ellis4}. These authors asked if there were others groups (besides $S_n$)  for which there is an elegant characterization of Boolean functions whose Fourier support is concentrated on certain irreducible representations. Actually, in Section \ref{sec3}, we explain that $3$-transitive groups satisfying certain extra conditions have a similar characterization.   

The proof of Theorem \ref{teo2} follows from Theorem \ref{teo1} and some basic properties of intersecting families in $G_q$.   

The rest of the paper is organized as follows.  In Section \ref{sec1} we provide some notation, definitions and basic results. In Section \ref{sec2} we characterize the Fourier transforms of the characteristic functions of almost extremal families. In Section \ref{sec3} we prove our main theorems. Finally, in Section \ref{sec4} we conclude with some remarks and open problems.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Background}\label{sec1}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Fourier Analysis}

Let G be a finite group. We denote by $\mathbb{C}[G]$ the vector space of all complex valued functions on $G$.  

\begin{definition}
Let $R$ be a complete set of non-isomorphic irreducible matrix representations of $G$. The Fourier transform of $f \in \mathbb{C}[G]$ is a matrix-valued function on irreducible representations. Its value at the irreducible representation $\rho \in R$ is
\[
\widehat{f}(\rho)= \frac{1}{|G|} \sum_{s \in G} f(s)\rho(s).
\]  
\end{definition} 

We apply the Fourier transform to decompose the vector space $\mathbb{C}[G]$ into a direct sum of subspaces indexed by the irreducible representations of $G$. For every $\rho \in R$, we denote by $V_{\rho}$ the subspace of  $\mathbb{C}[G]$ consisting of all functions whose Fourier transform is supported only on $\rho$, more precisely,
\[
V_{\rho}=\{ f \in \mathbb{C}[G]: \widehat{f} (\rho')=0,  \mbox{ for all }\rho' \neq \rho, \mbox{ } \rho' \in R\}.
\] 
Since the Fourier transform is an invertible linear transformation, we can write 
\[
\mathbb{C}[G] = \bigoplus_{\rho \in R} V_{\rho}. 
\]
By abuse of notation, we will sometimes use $V_{\chi_{\rho}}$ to denote $V_{\rho}$ where $\chi_{\rho}$ is the irreducible character afforded by $\rho$.

Moreover, we can make $\mathbb{C}[G]$ an inner product space. For any $f,g \in \mathbb{C}[G]$ we define
\[
 \langle f,g \rangle = \frac{1}{|G|} \sum_{x \in G} f(x) \overline{g(x)}.
\]
We denote by $\Vert f \Vert$ the euclidean norm induced by the inner product
\[
 \Vert f \Vert = \sqrt{\frac{1}{|G|} \sum_{g \in G} |f(g)|^2 }\mbox{ }.
\]

Let $U$ be any subspace of $\mathbb{C}[G]$ and $f \in \mathbb{C}[G]$. We denote by $U^{\bot}$ the orthogonal complement of $U$ and by $P_U(f)$ the projection of $f$ onto $U$. Thus, we can write
\[
f = P_U(f) + P_{U^{\bot}}(f).
\]

Let  $\Omega=\{1, \dots, n\}$ be a set and $\mathbb{C}[\Omega]$ be the vector space of all $\mathbb{C}$-valued functions defined on $\Omega$. For every $i \in \Omega$, we define $e_i$ as the function on $\Omega$ which takes the value $1$ at $i$ and $0$ elsewhere. Let $G$ be a group acting on $\Omega$ on the right. This action turns $\mathbb{C}[\Omega]$ into a representation of $G$ of degree $n$. Indeed, this representation is produced by a linear extension of the (left) action defined by  $g(e_i)= e_{ig^{-1}}$ for all $g \in G$ and $i \in \Omega$. The vector subspace $V_{std}$ spanned by the vectors $\{ \sum_{i=1}^n x_ie_i: \sum x_i=0  \}$ is a subrepresentation of $\mathbb{C}[\Omega]$ of degree $n-1$, known as the standard representation of $G$. We denote by $\chi_{std}$ the character afforded by the standard representation (we will refer to $\chi_{std}$ as the standard character of $G$). It follows by definition that for every $g \in G$, the value $\chi_{std}(g)$ corresponds to the number of elements in $\Omega$ fixed by $g$ minus one. 

Let $X$ be an inverse-closed subset of $G$. The Cayley graph on $G$ generated by $X$ is the graph with vertex set $G$ such that there is an edge between  $g_1,g_2 \in G$ if and only if  $g_1g_2^{-1} \in X$. We denote this graph by $Cay(G,X)$. The following lemma says that under certain conditions on $X$, the subspaces $V_{\rho}$ are eigenspaces of $Cay(G,X)$. 

\begin{lemma}\label{lemma22}
(Babai \cite{Babai}, Diaconis-Shahshahani \cite{Diaconis}) Let $G$ be a finite group, and let $R$ be a complete set of irreducible representations of $G$. Let $X \subset G$ be inverse-closed and conjugation invariant, and let $Cay(G,X)$ be the Cayley graph on $G$ with generating set $X$. For every $\rho \in R$, the vector subspace $V_{\rho}$ is an eigenspace of $Cay(G,X)$ with eigenvalue
\[
 \frac{1}{\chi_{\rho}(1)} \sum_{x \in X} \chi_{\rho}(x), 
\]
where $\chi_{\rho}$ is the irreducible character of $\rho$. Besides, if $\lambda$ is an eigenvalue of $Cay(G,X)$ corresponding to the irreducible representations $\{\rho_1,\dots,\rho_s\} \subset R$ then the dimension of the $\lambda$-eigenspace is $\sum_{i=1}^s\chi_{\rho_i}(1)^2$.    
\end{lemma}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{$PGL(2,q)$}

 \begin{table}[t]
 \caption{Character table of $PGL(2,q)$.}\label{table1}
 \begin{center}
  \begin{tabular}{ | l | c | c | c | c | }
    \hline
                                 &   $I$      &  $u$      &  $d_{x}$                                         & $v_{r}$                           \\ \hline
      $\lambda_1$       &     $1$    &   $1$     &  $1$                                              & $1$                                \\ \hline    
      $\psi_1$              &     $q$    &   $0$     &   $1$                                             & $-1$                               \\ \hline
      $\eta_{\beta}$     &   $q-1$   &  $-1$    &   $0$                                              & $-\beta(r)- \beta(r^q)$    \\ \hline
      $\nu_{\gamma}$  &  $q+1$  &   $1$     &   $\gamma(x) + \gamma(x^{-1})$  & $0$                                \\ \hline  
      $\lambda_{-1}$ ($q$ odd)   &     $1$    &   $1$     &   $\delta(x)$                  & $\delta(r)$                      \\ \hline
      $\psi_{-1}$  ($q$ odd)         &     $q$    &   $0$     &   $\delta(x)$                   & $-\delta(r)$                    \\ \hline
  \end{tabular}
\end{center}
 \end{table}
 
Let $\mathbb{F}_q$ be the finite field of size $q$ and $\mathbb{F}_{q^2}$ its unique quadratic extension. We denote by $\mathbb{F}_q^*$ and $\mathbb{F}_{q^2}^*$ the multiplicative groups of $\mathbb{F}_q$ and $\mathbb{F}_{q^2}$, respectively. Let $V$ be a $2$-dimensional vector space over $\mathbb{F}_q$ then $GL(V)$ denotes the group of all invertible linear transformations on $V$. The subgroup of all invertible linear transformations on $V$ with determinant $1$ is known as the special general linear group $SL(V)$.  We denote by $Z(GL(V))$ and $Z(SL(V))$ the centers of the groups $GL(V)$ and $SL(V)$, respectively.

The projective general linear group of $V$ is defined as
$
PGL(V)= GL(V)/Z(GL(V)),
$
and the projective special linear group of $V$ is defined as
$
PSL(V)= SL(V)/ Z(SL(V)).
$

Choosing a basis for $V$ provides an isomorphism between $GL(V)$ and the group $GL(2,q)$ of all invertible $2 \times 2$ matrices over $\mathbb{F}_q$. Analogously, the group $SL(2,q)$ of all invertible $2 \times 2$ matrices  with determinant $1$ is isomorphic to $SL(V)$.  The center of $GL(2,q)$, denoted by $Z(GL(2,q))$, consists of all non-zero scalar matrices while the center of $SL(2,q)$ is equal to $SL(2,q) \cap Z(GL(2,q))$. Therefore, the groups 
\[ 
PGL(2,q)= GL(2,q)/Z(GL(2,q)) \quad \mbox{and} \quad PSL(2,q)=SL(2,q)/(SL(2,q)  \cap Z(SL(2,q)))
\]
are isomorphic to $PGL(V)$ and $PSL(V)$, respectively. If $q$ is odd then $PSL(2,q)$ is a subgroup of $PGL(2,q)$ of index $2$. On the other hand, if $q$ is even then $PGL(2,q)= PSL(2,q)$.

We denote by $PG(1,q)$ the set of $1$-dimensional subspaces  of $V$. Thus, $PG(1,q)$ is a projective line over $\mathbb{F}_q$ and its elements are called projective points. An easy computation shows that $PG(1,q)$ has cardinality $q+1$. From the above definitions, it is clear that the groups $PGL(2,q)$ and $PSL(2,q)$ define a natural right action on $PG(1,q)$. Moreover, the action of $PGL(2,q)$ on $PG(1,q)$ is sharply $3$-transitive.

We briefly describe the character table of $G_q:=PGL(2,q)$. We refer the reader to  \cite{Pia1} for a complete study of the complex irreducible characters of $G_q$.  We start by describing its conjugacy classes. By abuse of notation we will denote the elements of $G_q$ by $2$ by $2$ matrices with entries from $\mathbb{F}_q$.  We choose the following representatives for the conjugacy classes of $G_q$:
\[ 
I=\left(\begin{array}{cc}
1 & 0 \\
0 & 1
\end{array}
\right),
\quad
u= \left(\begin{array}{cc}
 1 & 1\\
 0 & 1
\end{array}\right),
\quad
d_x=\left(\begin{array}{cc}
 x & 0\\
 0 & 1
\end{array}\right),
\quad
v_r=\left(\begin{array}{cc}
 0 & 1\\
 -r ^{1+q} & r + r^q
\end{array}\right),
\] 
where the label $x$ runs through all the elements of $\mathbb{F}_q^*$ of order greater  than $1$ up to inversion, and the label $r$ runs through all the elements of $\mathbb{F}_{q^2}^* / \mathbb{F}_q^*$ of order greater than $1$ up to inversion.    

The complex irreducible characters of $G_q$ are described in Table \ref{table1}. The trivial character is denoted by $\lambda_1$. The character $\psi_1$ corresponds to the standard character which is an  irreducible character of $G_q$. Thus,  for every $g  \in G_q$,  the value of $\psi_{1}(g)$ is equal to the number of projective points fixed by $g$ in $PG(1,q)$ minus $1$. The label $\beta$ in Table \ref{table1} runs through all homomorphism $\beta: \mathbb{F}_{q^2}^*/ \mathbb{F}_{q}^* \rightarrow \mathbb{C}$ of order greater than $2$ up to inversion.  Therefore, the number of irreducible characters $\{\eta_{\beta}\}_{\beta}$ is $q/2$ if $q$ is even and $(q-1)/2$ if $q$ is odd. The label $\gamma$ in Table \ref{table1}  runs through all the homomorphism $\gamma : \mathbb{F}_{q}^* \rightarrow \mathbb{C}$ of order greater than 2 up to inversion.  Therefore, the number of irreducible characters $\{\nu_{\gamma}\}_{\gamma}$ is $q/2 -1$ if $q$ is even and $(q-3)/2$ if $q$ is odd.

If $q$ is odd then $G_q$ has two more irreducible characters denoted by $\lambda_{-1}$ and $\psi_{-1}$ in Table \ref{table1}. The values of these characters depend on the function $\delta$. We define $\delta(x)=1$ if $d_x \in PSL(2,q)$ and $\delta(x)=-1$ otherwise. Similarly, $\delta(r)=1$  if $v_r \in PSL(2,q)$ and $\delta(r)=-1$ otherwise.   


Using the notation introduced in the above paragraphs we can write
\[
\mathbb{C}[G_q]= V_{\lambda_1} \oplus V_{\psi_1} \oplus \bigoplus_{\beta} V_{\eta_{\beta}} \oplus \bigoplus_{\gamma} V_{\nu_{\gamma}}
\]
when $q$ is even, and 
\[
\mathbb{C}[G_q]= V_{\lambda_1} \oplus V_{\lambda_{-1}} \oplus  V_{\psi_1} \oplus V_{\psi_{-1}} \oplus  \bigoplus_{\beta} V_{\eta_{\beta}} \oplus \bigoplus_{\gamma} V_{\nu_{\gamma}}
\]
when $q$ is odd.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{The eigenvalue method}

As was remarked in the introduction, the eigenvalue method has been used several times to get upper bounds on the size of intersecting families for EKR-type problems. In this section, we apply the eigenvalue method to show that the characteristic function of every extremal family of $G_q$ has a Fourier transform supported on just two irreducible representations of $G_q$. In the next section, we will show that almost extremal families have a similar Fourier characterization. 

The first step of the method is to reformulate the problem  in graph theory terminology. Indeed, the problem of finding the maximum size of an intersecting family in $G_q$ is equivalent to the problem of finding the maximum size of an independent set in a certain graph. Then, we can apply  Hoffman's bound to get an upper bound on the size of an independent set. The following variant of Hoffman's theorem will be enough for our purposes.

\begin{theorem}
 (Hoffman's bound) Let $\Gamma$ be a $k$-regular, $n$-vertex graph. Let $A$ be the adjacency matrix of $\Gamma$ and let $\lambda_{min}$ be the minimum eigenvalue of $A$. If $S$ is an independent set in $\Gamma$, then
\[
\frac{|S|}{n} \leq \frac{-\lambda_{\min}}{k - \lambda_{\min}}.
\]
If equality holds then the characteristic function $1_S$ of $S$ satisfies:
\[
1_S \in V_1 \oplus V_{\lambda_{\min}}
\]
where $V_1$ is the vector space spanned by the all-ones vector and $V_{\lambda_{\min}}$ is the $\lambda_{\min}$-eigenspace. 
\end{theorem}

Recall that an element $g \in G_q$ is a derangement if for any $\alpha \in PG(1,q)$ we have that $\alpha \neq \alpha^{g}$. Denote by $D_q$ the set of derangements in $G_q$. We define $\Gamma$ as the Cayley graph on $G_q$ with generating set $D_q$. This graph is known as the derangement graph of $G_q$.  Note that every independent set in  $\Gamma$ corresponds to an intersecting family in $G_q$. Hence, an upper bound on the size of independent sets in $\Gamma$ is also an upper bound on the size of  intersecting families in $G_q$. 

To apply Hoffman's bound, we need to compute the eigenvalues of $\Gamma$. Note that the set $D_q$ is a union of conjugacy classes and inverse-closed. Therefore, $\Gamma$ satisfies the conditions of Lemma \ref{lemma22}. Thus, to compute the eigenvalues of $\Gamma$ we just need to evaluate the character sum  $ \frac{1}{\chi(1)} \sum_{x \in D_q} \chi(x) $ for every irreducible character $\chi$ of $G_q$.



Now, using the character table of $G_q$ (Table \ref{table1}) and Lemma \ref{lemma22}, Meagher and Spiga \cite{Karen1}  computed the eigenvalues of $\Gamma$ for every $q$:
\begin{center}
\begin{tabular}{|c|c|c|c|c|}
\hline 
q even & $\lambda_1$ & $\psi_1$ & $\eta_{\beta}$ & $\nu_{\gamma}$ \\ 
\hline 
eigenvalues & $\frac{q^2(q-1)}{2}$ & $-\frac{q(q-1)}{2}$ & $q$ & $0$ \\ 
\hline 
\end{tabular} 
\end{center}

\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline 
q odd 	 & $\lambda_1$ & $\lambda_{-1}$ & $\psi_{1}$ & $\psi_{-1}$ & $\eta_{\beta}$ & $\nu_{\gamma}$ \\ 
\hline 
eigenvalues & $\frac{q^2(q-1)}{2}$ & $-\frac{q(q-1)}{2}$ & $-\frac{q(q-1)}{2}$ & $\frac{q-1}{2}$ & $q$ & $0$ \\ 
\hline 
\end{tabular} 
\end{center}
Then, applying  Hoffman's bound, they proved that the maximum size of an intersecting family in $G_q$ is $q(q-1)$. Therefore, the cosets of point stabilizers in $G_q$ are extremal families.  For every $\alpha, \beta \in PG(1,q)$, we denote by $T_{\alpha,\beta}$ the coset of a point stabilizer sending $\alpha$ to $\beta$. 


Furthermore, Hoffman's bound also provides information about the characteristic function of an extremal family. Indeed, if $S$ is an intersecting family of maximum size then its characteristic function $1_S$ is contained in $V_{\lambda_1} \oplus V_{\psi_1}$ when $q$ is even, and in $V_{\lambda_1} \oplus V_{\psi_1} \oplus V_{\lambda_{-1}}$ when $q$ is odd. In the next lemma, we show that it is possible to improve  this  result  in the case when $q$ is odd.

\begin{lemma}\label{lemma10}
Let $q$ be odd. Let $S \subset G_q$ be an intersecting family of size $q(q-1)$ and denote by $1_{S}$ its characteristic function. Then
\[
1_S \in V_{\lambda_1} \oplus V_{\psi_1}.
\]
\end{lemma}


To prove  Lemma \ref{lemma10}, we will need the following result proved by Meagher and Spiga in \cite{Karen1}.

\begin{lemma}\label{lemma11}
Consider the natural right action of $PSL(2,q)$ on the projective points of $PG(1,q)$. Let $X$ be the set of derangements of $PSL(2,q)$. An independent set of maximum size in $Cay(PSL(2,q), X)$ has size $q(q-1)/2$.
\end{lemma}


\begin{proof}[Proof of Lemma \ref{lemma10}]
We already know that $1_S \in V_{\lambda_1} \oplus V_{\psi_1} \oplus V_{\lambda_{-1}}$. The vector space $V_{\lambda_{-1}}$ is one dimensional so $V_{\lambda_{-1}} = \mbox{span}_{\mathbb{C}}\{\lambda_{-1}\}$. Hence, it is enough to show that $\langle 1_S, \lambda_{-1} \rangle=0$. 


Recall that $PSL(2,q)$ is a subgroup of $G_q$. The irreducible character $\lambda_{-1}$ is a function on $G_q$ such that $\lambda_{-1}(g)=1$ if $g \in PSL(2,q)$ and $-1$, otherwise. Therefore,  $\langle 1_S, \lambda_{-1} \rangle=0$ if and only if exactly half of the elements in $S$ are in $PSL(2,q)$.

From Lemma \ref{lemma11} it follows that he maximum size of an intersecting family in $PSL(2,q)$ is $q(q-1)/2$.  Therefore, at most $q(q-1)/2$ elements of $S$ are contained in $PSL(2,q)$. 

Since $PSL(2,q)$ is a subgroup of index $2$, there exists $g' \in G_q$ such that $G_q = g'PSL(2,q) \cup PSL(2,q)$. Assume to the contrary, that more than $q(q-1)/2$ elements of $S$ are contained in $g'PSL(2,q)$. If we multiply each of these elements by $g'$ then we get an intersecting family in $PSL(2,q)$. This is a contradiction because the maximum size of an intersecting family in $PSL(2,q)$ is $q(q-1)/2$. Therefore, exactly half of the elements in $S$ are contained in $PSL(2,q)$.
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Fourier characterization}\label{sec2}


Let $S$ be an intersecting family of maximum size in $G_q$.  It follows from Section \ref{sec1} that the Fourier transform of $1_S$  is supported only on the irreducible representations affording the characters $\lambda_1$ and $\psi_1$. In this section, we prove that the characteristic functions of almost extremal families in $G_q$ have Fourier transforms highly concentrated on the irreducible representations affording the characters $\lambda_1$ and $\psi_1$.  To do this we apply a stability version of  Hoffman's bound (this term was coined by Ellis in \cite{Ellis1}).  The next two lemmas show that if an intersecting family $S \subset G_q$ satisfies that $|S|$ is very close to $q(q-1)$ then $1_{S}$ must be close to $U:=V_{\lambda_1} \oplus V_{\psi_1}$.


\begin{lemma}\label{lemma1}
Let $S$ be an intersecting family in $G_q$. If $q$ is a power of $2$ then,
\[
  \Vert P_{U^{\bot}}(1_S) \Vert^2 \leq \left( 1 - \frac{|S|}{q(q-1)}\right) \Vert 1_{S}\Vert^2. 
\]
\end{lemma}

\begin{proof}
Let $A$ be the adjacency matrix of the graph $\Gamma=Cay(G_q,D_q)$. Let $\{x_1, \ldots, x_N\} \subset \mathbb{C}[G_q]$ be an orthonormal basis of real eigenvectors for $A$ (recall that $A$ is symmetric). Let $\theta_i$ be the eigenvalue of $A$ such that  $A x_i = \theta_i x_i$, for $1 \leq i \leq N$. Note that,
\begin{itemize}
\item $1_{S} = \sum_{i=1}^{N} \epsilon_i x_i$ where $\epsilon_i = \langle 1_S, x_i\rangle$ for every $i=1, \ldots, N$.
\item $\Vert 1_{S}\Vert^2 = \sum_{i=1}^{N} \epsilon_i^{2}$.
\item $\langle 1_{S},1\rangle = \Vert 1_{S}\Vert^2 = \epsilon_1$.
\end{itemize}

Let $x_1$ be the all $1'$s vector with eigenvalue $q^{2}(q-1)/2$.  Since every intersecting family corresponds to an independent set in the graph $\Gamma$ we get
\begin{equation}\label{ecu1}
     0 = 1_{S}^TA 1_{S} = \sum_{i=1}^N \theta_i \epsilon_i^{2} = \theta_1\epsilon_1^2  + \sum_{i: i\neq 1, \theta_i \neq \lambda_{\min}} \theta_i \epsilon_i^2 - \frac{q(q-1)}{2}  \sum_{i: \theta_i = \lambda_{\min}}  \epsilon_i^2,
\end{equation}
where $\lambda_{\min}= -q(q-1)/2$.

Recall that the second smallest eigenvalue of $\Gamma$ is zero. Therefore, from equation (\ref{ecu1}) we obtain the following inequality
\begin{equation}\label{ecu2}
 \theta_1 \Vert  1_{S} \Vert^4 - \frac{q(q-1)}{2} \sum_{i: \theta_i = \lambda_{\min}}  \epsilon_i^2 \leq 0.
\end{equation}

By definition we have
\[
\Vert P_{U^{\bot}} (1_{S} )\Vert^2 = \sum_{i: i \neq 1, \theta_i \neq  \lambda_{\min}}  \epsilon_i^2,
\]
hence
\begin{equation}\label{ecu3}
\sum_{i: \theta_i = \lambda_{\min}}  \epsilon_i^2 = \Vert 1_{S} \Vert^2 - \Vert 1_{S} \Vert^4 - \Vert P_{U^{\bot}} (1_{S} )\Vert^2.
\end{equation}

Combining  (\ref{ecu2}) and (\ref{ecu3})  we get
\[
\Vert P_{U^{\bot}} (1_{S} )\Vert^2  \leq \left( 1 - \frac{|S|}{q(q-1)}\right)  \Vert 1_{S} \Vert^2. \qedhere
\]
\end{proof}


The next lemma deals with the case $q$ odd. The proof is a little more complicated because in that case  the minimum eigenvalue of $\Gamma$ is afforded by two distinct irreducible characters, $\psi_1$ and $\lambda_{-1}$.


\begin{lemma}\label{lemma2}
Let $S$ be an intersecting family in $G_q$  such that $|S|=(1-\delta)q(q-1)$, $\delta >0$.  If $q$ is an odd prime power then 
\[
  \Vert P_{U^{\bot}}(1_S) \Vert^2 \leq \left( 1 - \frac{|S|}{q(q-1)}\right) \Vert 1_{S}\Vert^2 +\left(\frac{\delta}{q+1}\right)^{2}.
\]
\end{lemma}

\begin{proof}

 Using the notation introduced in the proof of Lemma \ref{lemma1} we get
\begin{equation}\label{ecu4}
 \frac{q^2(q-1)}{2}\Vert  1_{S} \Vert^4 - \frac{q(q-1)}{2} \sum_{i: \theta_i = \lambda_{min}}  \epsilon_i^2 \leq 0.
\end{equation}

Recall that the vector space $V_{\lambda_{-1}}$ is one dimensional. Hence, we denote by $x_{\lambda_{-1}}$ the only eigenvector in the set $\{x_i\}_{i=1}^N$ contained in  $V_{\lambda_{-1}}$. We claim that $\epsilon_{\lambda_{-1}}^2 = \langle 1_S,  x_{\lambda_{-1}} \rangle^2\leq (\delta/(q+1))^2$.

Note that $x_{\lambda_{-1}}$ is the irreducible character $\lambda_{-1}$.  Hence,  $x_{\lambda_{-1}}$ is a function on $G_q$ such that $x_{\lambda_{-1}}(g)=1$ if $g \in PSL(2,q)$ and $-1$, otherwise. Besides, note that $S \cap PSL(2,q)$ and $S \cap (G_q \setminus PSL(2,q))$ have size at most $q(q-1)/2$ because the maximum size of an intersecting family in $PSL(2,q)$ is $q(q-1)/2$. Putting all the above remarks together
\begin{equation}\label{ecu5}
\epsilon_{\lambda_{-1}}^2 = \langle 1_{S}, x_{\lambda_{-1}} \rangle^2= \frac{1}{|G_q|^2} ( |S \cap PSL(2,q)| - |S \cap \left(G_q \setminus PSL(2,q))\right| )^2 \leq  \left(\frac{\delta}{q+1}\right)^2.
\end{equation}

By definition we have
\[
\Vert P_{U^{\bot}} (1_S ) \Vert^2 = \sum_{i: i \neq 1, \theta_i \neq \lambda_{min}} \epsilon_i^2 + \epsilon_{\lambda_{-1}}^2,
\]
hence
\begin{equation}\label{ecu6}
 \sum_{i: \theta_i = \lambda_{min}} \epsilon_i^2 = \Vert 1_{S}\Vert^2 - \Vert 1_{S}\Vert^4 - \Vert P_{U^{\bot}} (1_{S} ) \Vert^2 + \epsilon^2_{\lambda_{-1}}.
\end{equation} 

Combininig (\ref{ecu4}), (\ref{ecu5}) and (\ref{ecu6}) we get
$$
	\Vert P_{U^{\bot}} (1_S ) \Vert^2 \leq \left( 1 - \frac{|S|}{q(q-1)}\right)  \Vert 1_{S} \Vert^2 + \left( \frac{\delta}{q+1} \right)^2. \qedhere
$$
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Structural Characterization}\label{sec3}

In this section we  give a characterization of the structure of Boolean functions on $G_q$ whose Fourier transform is highly concentrated on $U$. The technique used to prove this result is from \cite{Ellis2}. In that paper,  Ellis, Filmus and Friedgut proved that if a Boolean function on $S_n$ has Fourier transform that is highly concentrated on the first two irreducible representations of $S_n$ (which correspond to the trivial and standard representation) then it must be close to a union of cosets of points stabilizers. Their proof is only based  on the fact that the action of $S_n$ on $[n]$ is $3$-transitive. 

Let $G$ be a group acting $3$-transitively on a set $\Omega$. It is well-known (and easy to show) that the standard representation is irreducible for any $2$-transitive group. Also, recall that $V_1$ and $V_{\chi_{std}}$ are the vector subspaces of  complex-valued functions on $G$ whose Fourier transform has support on the trivial and the standard representation, respectively. The following proposition is a generalization of Theorem 1 from \cite{Ellis2}\footnote{Actually, Proposition \ref{pro1} is a generalization of a special case of Theorem 1 from \cite{Ellis2}. To fully generalize that theorem we need to consider $S \subset G$ with $|S|=c|G|/n$, where $c= o(n)$.}.

\begin{proposition}\label{pro1}
There exist absolute constants $C_1, \epsilon_1 > 0$ such that the following holds. Let $G$ be a finite group acting $3$-transitively on a set $\Omega$ of size $n$. Let $S \subset G$ with $|S|= (1-\delta)|G|/n$, where $0 \leq \delta < 1/2$. Let $V=V_1 \oplus V_{std}$. If $\|P_{V^{\perp}}(1_S)\|^2= \epsilon \| 1_S\|^2$, where $\epsilon \leq \epsilon_1$, then there exists $T \subset G$ such that $T$ is a coset of the stabilizer of an element of $\Omega$, and
\[
|S \triangle T| \leq C_1 \left(\epsilon^{1/2} + \frac{1}{n}\right)|S|.
\]   
\end{proposition}


The proof of this proposition is exactly the same as the proof of Theorem 1 in \cite{Ellis2}. Since the action of $G_q$ on $PG(1,q)$ is $3$-transitive, Proposition \ref{pro1} can be used to characterize  Boolean functions on $G_q$ whose Fourier transform is highly concentrated on $U$. Recall that $U$ is the vector subspace of all of  complex-valued functions on $G_q$ whose Fourier transform has support on the trivial and the standard representation.

\begin{corollary}\label{lemma3}
There exist absolute constants $C_1, \epsilon_1>0$ such that the following holds. Let  $S \subset G_q$ with $|S|= (1-\delta)q(q-1)$, where $0 \leq \delta < 1/2$. If $\Vert P_{U^{\bot}}(1_S)\Vert^2 = \epsilon \Vert 1_S \Vert^2$ where $\epsilon \leq \epsilon_1$, then  there exist $\alpha, \beta \in PG(1,q)$  such that $T_{\alpha,\beta}$ satisfies that
\[
	|S \triangle T_{\alpha,\beta}| \leq C_1  \left(  \epsilon^{1/2} + \frac{1}{q+1} \right)  |S|.
\]
\end{corollary}



Now we are ready to prove Theorem 1. 

\begin{proof}[Proof of Theorem \ref{teo1}] 
We choose $C_0= \max(\frac{4\sqrt{2}}{\sqrt{\epsilon_1}}, \sqrt{2}C_1)$ where $C_1$ and $\epsilon_1$ are the absolute constants from Corollary \ref{lemma3}. With this choice of $C_0$, if $\epsilon_1/2 \leq \delta \leq 1/2$ then the statement of the theorem holds trivially with any choice of a coset of a point stabilizer $T$.

Now, we consider the case where $\delta < \epsilon_1/2$. By assumption we know that $|S|=(1-\delta)q(q-1)$. Thus, it follows from Lemmas \ref{lemma1}  and \ref{lemma2} that $\Vert P_{U^{\bot}}(1_S) \Vert^2 \leq \delta \Vert 1_S \Vert^2$ when $q$ is even and  $\Vert P_{U^{\bot}}(1_S) \Vert^2 \leq 2\delta \Vert 1_S \Vert^2$ when $q$ is odd. This implies that the characteristic function $1_S$ is highly concentrated on $U$. Hence, we can apply Corollary \ref{lemma3} to conclude that
\[
|S \triangle T| \leq C_0  \left(  \delta^{1/2} + \frac{1}{q+1} \right)  |S|,
\]
where $T$ is some coset of a point stabilizer.
\end{proof}


Theorem \ref{teo1} implies that almost extremal families are almost contained in a coset of a point stabilizer. Furthermore, we can refine this result to conclude that almost extremal families are fully contained in a coset of a point stabilizer. 

\begin{proof}[Proof of Theorem \ref{teo2}]
First assume that $q \leq 4C_0-1$, where $C_0$ is the absolute constant from Theorem \ref{teo1}. Note that we can choose $\delta_1>0$ small enough such that for all $q \leq 4C_0-1$ we have
\[
(1-\delta_1)q(q-1) > q(q-1)-1.
\]
Hence, if $S$ is an intersecting family of $G_q$ with $|S| \geq (1 - \delta_1)q(q-1)$ then $|S|=q(q-1)$. Therefore, by the characterization of intersecting families of maximum size in $G_q$ given in \cite{Karen1}, we conclude that $S$ must be equal to a coset of the stabilizer of a point.

Now, we assume that $q > 4C_0-1$. It is clear that if we choose $\delta_2$ such that $0 \leq \delta_2 \leq 1/(16 C_0^2)$ then
\begin{equation}\label{ecus1}
C_0  \left(  \delta_2^{1/2} + \frac{1}{q+1} \right)  < \frac{1}{2}.
\end{equation}
From Theorem \ref{teo1} it follows that if $|S| \geq (1-\delta_2) q(q-1)$ then  
\begin{equation}\label{ecu11}
|S \triangle T| \leq C_0  \left(  \delta_2^{1/2} + \frac{1}{q+1} \right)  |S|,
\end{equation}
where $T$ is a coset of a point stabilizer.  Combining (\ref{ecus1}) and (\ref{ecu11}),  we get that $|S \triangle T| < \frac{1}{2}q(q-1)$.

Suppose without loss of generality that $T=T_{\alpha,\alpha}$ for some $\alpha \in PG(1,q)$.  Assume for a contradiction that there exists $g \in S$ such that $\alpha^g = \beta$ with $\beta\in PG(1,q)$, $\beta \neq \alpha$. We use this assumption to estimate the size of $T_{\alpha,\alpha} \setminus S$.

If $h \in S \cap T_{\alpha,\alpha}$ then $g^{-1}h$ contains at least one fixed point (recall that $S$ is an intersecting family). Hence, the elements $h \in T_{\alpha,\alpha}$ such that $g^{-1}h$ is a derangement must be contained in $T_{\alpha, \alpha} \setminus S$.  

We compute the number of derangements in $g^{-1}T_{\alpha,\alpha}= T_{\beta, \alpha}$. The number of derangements in $T_{\alpha, \alpha}$ is zero. Thus, the $\frac{q^2(q-1)}{2}$ derangements in $G_q$ are contained in $\bigcup_{\delta \neq \alpha} T_{\delta, \alpha}$. Using the 2-transitivity of the action of $G_q$ on $PG(1,q)$, we get that the number of derangements in $T_{\delta, \alpha}$ is the same for every $\delta \neq \alpha$.  Indeed, for any two distinct $\delta, \delta' \in PG(1,q)$ with $\delta, \delta' \neq \alpha$, let $m \in G_q$ such that $\alpha^m = \alpha$ and $\delta^m = \delta'$. Then the bijection $\Phi : G_q \rightarrow G_q: g \mapsto m^{-1}gm$ satisfies $\Phi(D_q)=D_q$, and $\Phi(T_{\delta,\alpha})=T_{\delta',\alpha}$, so $|T_{\delta', \alpha} \cap D_q | = |\Phi(T_{\delta, \alpha} \cap D_q)|= |T_{\delta,\alpha} \cap D_q |$.


Therefore, the number of derangements in $T_{\beta,\alpha}$ is $q(q-1)/2$. Hence, there are at least $q(q-1)/2$ elements in $T_{\alpha, \alpha} \setminus S$ which implies
\[
|S \triangle T_{\alpha, \alpha}| \geq \frac{q(q-1)}{2}.
\] 
Thus, we get a contradiction.  Finally, we choose the universal constant $\delta_0$ to be equal to  $\min(\delta_1, \delta_2)$.
\end{proof}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Conclusions and Open Problems}\label{sec4}

In this paper we prove that extremal families in $G_q$ are not only unique, but also stable: any intersecting family in $G_q$ of size close to $q(q-1)$ must be close in structure to a coset of a point stabilizer. Actually, Theorem \ref{teo2} implies that for $q$ sufficiently large the cosets of point stablizers are the only extremal families in $G_q$. This result was already proven by Meagher and Spiga \cite{Karen1} using different methods.    


It is possible to apply the ideas used in this paper to prove similar results for  some $3$-transitive groups. Let $G$ be a finite group acting $3$-transitively on a finite set $\Omega$. Suppose that this action satisfies the following conditions: 
\begin{enumerate}
 \item The maximum size of an intersecting family in $G$  is $|G|/|\Omega|$ (note that this number is equal to the size of a coset of a point stabilizer in $G$).
 \item Let $D$ be the set of derangements of $G$ with respect to its action on $\Omega$.  The standard character is the unique irreducible character affording the minimum eigenvalue of the derangement graph $Cay(G,D)$ (recall that since $D$ is inverse-closed and conjugation-invariant there is a correspondence, given by Lemma \ref{lemma22}, between the eigenvalues of $Cay(G,D)$ and the irreducible characters of $G$).
 \end{enumerate} 
 
Thus, applying Hoffman's bound it follows that the characteristic vector of any intersecting family of maximum size lies in the vector subspace $V=V_{1} \oplus V_{\chi_{std}}$ of $\mathbb{C}[G]$. Recall that $V_1$ and $V_{\chi_{std}}$ are the vector subspaces of  complex-valued functions on $G$ whose Fourier transform has support on the trivial and the standard representation, respectively.
 
Now, let $S \subset G$ be an intersecting family. If the size of $S$ is close to $|G|/|\Omega|$ and the size of the gap between the smallest and the second-smallest eigenvalue of $Cay(G,D)$ is big enough then we can use analogues of Lemmas \ref{lemma1} and \ref{lemma2} to conclude that the characteristic function $1_S$ is close to $V$. Moreover, as was remarked in Section \ref{sec3},  the result of Ellis, Filmus and Friedgut in  \cite{Ellis2}, for Boolean functions on $S_n$,  can be generalized to any $3$-transitive action of a finite group on a finite set. Thus, if $1_S$ is  close to the vector space $V$ then it must be close in structure to some coset of a point stabilizer in $G$. Therefore, we can use these ideas to prove that extremal families in $G$ are unique and stable. 

Consider the action of $PSL(2,q)$ on the points of $PG(1,q)$ for $q$ an odd prime power. This action is $2$-transitive.  Using the eigenvalue method it is easy to prove that the maximum size of an intersecting family in $PSL(2,q)$ is $q(q-1)/2$. Furthermore, the characteristic vector of any extremal family in $PSL(2,q)$ lies in $V=V_1 \oplus V_{\chi_{std}}$ (recall that the standard character is irreducible for $2$-transitive actions). However, the argument used here cannot be applied in a straightforward way to solve the uniqueness or stability problems because the action of $PSL(2,q)$ on $PG(1,q)$ is not $3$-transitive. It was conjectured by Meagher and Spiga \cite{Karen1} that the cosets of points stabilizers are the only extremal families in $PSL(2,q)$. Here, we extend their conjecture: the extremal families in $PSL(2,q)$ are not only unique but also stable.

\begin{conjecture}
Let $S$ be an intersecting family in $PSL(2,q)$ with $q$ an odd prime power. Then
\begin{enumerate}
\item Uniqueness: If $|S|=\frac{q(q-1)}{2}$ then $S$ is a coset of a point stabilizer.
\item Stability: There exists $\delta > 0$ such that if $|S| \geq (1-\delta) q(q-1)/2$ then $S$ is contained within a coset of a point stabilizer.
\end{enumerate}
\end{conjecture} 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
We would like to thank the referees for their helpful suggestions and comments.





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\SquashBibFurther
\begin{thebibliography}{99}

\bibitem{Alon1}
  N. Alon, I. Dinur, E. Friedgut and B. Sudakov. 
   \newblock Graph products, Fourier analysis and spectral techniques. 
   \newblock {\em Geom. Funct. Anal.}, 14:913--940,  2004.
    
    \bibitem{Babai}
     L.  Babai. 
     \newblock Spectra of Cayley graphs.
     \newblock {\em J. Combin. Theory Ser. B}, 27:180--189, 1979.

\bibitem{Cameron1}
    P. J. Cameron and C. Y. Ku. 
    \newblock Intersecting families of permutations.
     \newblock {\em European J. Combin.}, 24:881--890, 2003. 
 
    \bibitem{Diaconis}
     P. Diaconis, M. Shahshahani. 
     \newblock Generating a random permutation with random
transpositions. 
     \newblock {\em Probab. Theory and Related Fields}, 57:159--179, 1981.  

\bibitem{Ellis1}
  D. Ellis.
   \newblock Stability for $t$-intersecting families of permutations.
   \newblock {\em J. Combin. Theory Ser. A}, 118:208--227, 2011. 
   
  \bibitem{Ellis5}
  D. Ellis.
   \newblock A Proof of the Cameron-Ku Conjecture. 
   \newblock {\em J. London Math. Soc.}, 85:165--190, 2012. 

 \bibitem{Filmus}
    D. Elllis, Y. Filmus and E. Friedgut.
     \newblock Triangle-intersecting families of graphs. 
     \newblock {\em J. Eur. Math. Soc.}, 14:841--885,  2012.  

\bibitem{Ellis2} 
    D. Ellis, Y. Filmus, and E. Friedgut. 
    \newblock A quasi-stability result for dictatorships in $S_n$.
    \newblock {\em Combinatorica}, 1--46, 2014.
 
\bibitem{Ellis4} 
    D. Ellis, Y. Filmus, and E. Friedgut. 
     \newblock  A stability result for balanced dictatorships in $S_n$. 
     \newblock {\em Random Structures and Algorithms}, 2015.
 
\bibitem{Frankl1}
    P. Frankl and M. Deza. 
    \newblock On the maximum number of permutations with given maximal or minimal distance.
     \newblock {\em J. Combin. Theory Ser. A}, 22:352--360, 1977.

\bibitem{Frankl2}
    P. Frankl
     \newblock Erd\H{o}s-Ko-Rado theorem with conditions on the maximal degree.
     \newblock {\em J. Combin. Theory Ser. A}, 46:252--263, 1987.     
     
\bibitem{Friedgut2}
  E. Friedgut, G. Kalai, A. Naor.
   \newblock Boolean functions whose Fourier transform is concentrated on the first two levels. 
   \newblock {\em Advances in Applied Mathematics}, 29:427--437, 2002.
   
 \bibitem{Karen4}
    C. Godsil and K. Meagher. 
     \newblock  A new proof of the Erd\H{o}s-Ko-Rado theorem for intersecting families of permutations. 
     \newblock  {\em European J. Combin.}, 30:404--414, 2009.  

\bibitem{Hatami1}
  H. Hatami, M. Ghandehari.
   \newblock Fourier analysis and large independent sets in powers of complete graphs.
   \newblock {\em J. Combin. Theory Ser.  B},  98:164--172, 2008.
  
  \bibitem{Larose1}
   B. Larose and C. Malvenuto.
    \newblock Stable sets of maximal size in Kneser-type graphs.
    \newblock {\em European J. Combin.},  25:657--673, 2004. 
  
   \bibitem{Lo1}
    L. Lov\'{a}sz.
    \newblock On the Shannon Capacity of a Graph. 
    \newblock {\em IEEE Transactions on Information Theory},  IT--25, 1979.      

 \bibitem{Karen1}
    K. Meagher, P. Spiga. 
    \newblock An Erd\H{o}s-Ko-Rado theorem for the derangement graph of $PGL(2,q)$ acting on the projective line.
     \newblock {\em J. Combin. Theory Ser. A},  118:532--544, 2011.   
 
\bibitem{Pia1}
  I. Piatetski-Shapiro.
   \newblock Complex Representations of $GL(2,K)$ for finite fields $K$.
   \newblock {\em Contemporary mathematics}, 1983.
  

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

 


   
    
    
    

    

       
    

      

      


    

    

 
\end{thebibliography}











 

\end{document}
