% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P17}{20(1)}{2013}

\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 Cross-intersecting families of labeled sets}

% 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{Huajun Zhang\thanks{The author is  supported by the National
Natural Science Foundation of China  (No.11001249 and No.11171310) and the Natural Science Foundation of Zhejiang Province (No.LY12A01006.)}\\
\small Department of Mathematics,
Zhejiang Normal University, Jinhua 321004, P.R. China\\
\small\tt huajunzhang@zjnu.cn
}




% \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{Jan 30, 2012}{Jan 14, 2013}{Jan 21, 2013}\\
\small Mathematics Subject Classifications:  05D05, 06A07}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
  For two positive integers $n$ and $p$, let $\mathcal{L}_{p}$
 be the family of labeled $n$-sets given by  \begin{align*}\mathcal{L}_{p}=\big\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}:
\ell_i\in[p], i=1,2\ldots,n\big\}.\end{align*} Families $\mathcal{A}$ and
$\mathcal{B}$ are said to be cross-intersecting if $A\cap
B\neq\emptyset$
   for all $A\in \mathcal{A}$ and $B\in\mathcal{B}$. In this paper, we will prove that for
    $p\geq 4$,  if $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting subfamilies of $\mathcal{L}_{\mathfrak{p}}$, then
    $|\mathcal{A}||\mathcal{B}|\leq p^{2n-2}$, and equality holds if and only
    if $\mathcal{A}$ and $\mathcal{B}$ are an identical largest intersecting  subfamily of  $\mathcal{L}_{p}$.


  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} EKR theorem; Intersecting family; cross-intersecting family; labeled set
\end{abstract}


\section{Introduction}
For a positive integer $n$, let $[n]$ denote the set
$\{1,2,\ldots,n\}$. Given a set $X$, by $\binom{X}{k}$ we denote the
set of all $k$-subsets of $X$, and let $2^X$ denote the set of all
subsets of $X$. A family $\mathcal{A}$ of sets  is said to be
$t$-intersecting  if $|A\cap B|\geq
 t$ for every pair $A, B\in\mathcal{A}$. Usually,
$\mathcal{A}$ is called intersecting if $t=1$.

The Erd\H{o}s-Ko-Rado Theorem \cite{EKR} says that if $\mathcal{A}$
is an intersecting subfamily of $\binom{[n]}{k}$ where $n\geq 2k$, then
$|\mathcal A|\leq \binom{n-1}{k-1}$. This theorem is a central
result in extremal set theory and inspires abundant fruits in this
field, for an excellent introduction to this we recommend the
survey paper \cite{Dezaf}.

This theorem  has many  generalizations, analogs and variations.
First,   finite sets are analogous to finite vector spaces
(\cite{Frankl-Wilson,Greene-Kleit,Hsieh}),
permutations (\cite{Cameron,DF,wjz}) and labeled sets
(signed sets \cite{Bollobas,borg-dm} or colored sets
\cite{LIW}), etc. Second, the intersection condition was generalized to
$t$-intersection and cross-intersection. Here, families $\mathcal
A_1,\mathcal A_2, \ldots, \mathcal A_m$ are said to be
cross-intersecting if $A\cap B\neq\emptyset$ for any $A\in\mathcal
A_i$ and $B\in\mathcal A_j$, $i\neq j$. Many authors studied the
bound of $\sum_{i=1}^m| \mathcal A_i|$
(\cite{hilton,borg,borg-dm,borg5,pborg1,pborg,borg6,wz,wz2}), and
 Pyber \cite{Pyber} first considered the bound of $|\mathcal A||\mathcal B|$ for cross-intersecting families $\mathcal A$ and $\mathcal B$. His
 result was slightly refined by Matsumoto and Tokushige
\cite{Matsumoto} and Bey \cite{Bey} as follows.


\begin{theorem}\label{pmb} If $\mathcal{A}\subseteq\binom{[n]}{k}$ and $\mathcal{B}\subseteq\binom{[n]}{\ell}$
are cross-intersecting with $n\geq \max\{2k,2\ell\}$, then
\begin{align*}|\mathcal{A}||\mathcal{B}|\leq \binom{n-1}{k-1}\binom{n-1}{\ell-1}.\end{align*}
Moreover, the equality holds if and only if $\mathcal{A}=\{A\in \binom{[n]}{k}: i\in A\}$ and
$\mathcal{B}=\{B\in \binom{[n]}{\ell}: i\in B\}$
for some $i\in [n]$, unless $n=2k=2\ell$.
\end{theorem}
 Tokushige \cite{Tokushige} and   Ellis, Friedgut
  and  Pilpel \cite{Ellis} generalized the above result to cross-$t$-intersecting families
  of finite sets and  cross-t-intersecting subfamilies of the symmetric group
   $S_n$, respectively.
     This paper provides an analogue of Theorem \ref{pmb} for families whose sets we refer to as labeled sets, following \cite{borg}.

For an $n$-tuple $\mathfrak{p}=(p_1,p_2,\ldots,p_n)$ such that $p_1,p_2,\ldots,p_n$ are positive integers
with $p_1\leq p_2\leq\cdots\leq p_n$, we define the family
$\mathcal{L}_{\mathfrak{p}}$ of labeled sets by
\begin{align*}\mathcal{L}_{\mathfrak{p}}=\big\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}:
\ell_i\in[p_i], i=1,2\ldots,n\big\}.\end{align*}
  Berge \cite{Berge} determined the maximum size of
intersecting families of labeled $n$-sets, Livingston
\cite{Livingston} characterized partial optimal intersecting
families and Borg \cite{borg} completely solved it by using the
shift operator in an inductive argument.
\begin{theorem}[Berge, Livingston, Borg]\label{2}
If $\mathcal A$ is an intersecting subfamily of  $\mathcal
L_{\mathfrak{p}}$, then $|\mathcal A|\leq p_2p_3\cdots p_n$. When
$p_1\geq 3$, equality holds if and only if $\mathcal
A=\big\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}: \ell_i=j
\big\}$, where $ p_i=p_1$ and $j\in[p_1]$.
\end{theorem}

In \cite{borg}, Borg also determined the upper bound of
$\sum_{1\leq i\leq m}|\mathcal A_i|$ for cross-intersecting subfamilies
$\mathcal A_1,\mathcal A_2,\ldots,\mathcal A_m$ of  $\mathcal
L_{\mathfrak{p}}$.



   In this paper, we consider a special case: $p_1=p_2=\cdots=p_n=p$. In this case, we write $\mathcal{L}_{\mathfrak{p}}$ as $\mathcal{L}_{p}$. The
    main result in this paper  is  the following theorem.
\begin{theorem}\label{mr}
Let $n$ and $p$ be two positive integers with $p\geq 4$. If
$\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting families in
$\mathcal{L}_{p}$, then
\begin{align*}|\mathcal{A}||\mathcal{B}|\leq p^{2n-2},\end{align*} and
equality holds if and only if
$\mathcal{A}=\mathcal{B}=\big\{\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}:
\ell_i=j \big\}$ for some $i\in[n]$ and  $j\in [p]$.
\end{theorem}

We will present some preliminary results in the next section, and
complete the proof of the above theorem  in Section 3.


\section{Preliminary Results}
For the labeled set  $\mathcal{L}_{p}$, we can construct a simple
graph, whose vertex set is $\mathcal{L}_{p}$, and $A,B\in
\mathcal{L}_{p}$ are adjacent if and only if $A\cap B=\emptyset$.
For convenience, this graph is also denoted by $\mathcal{L}_{p}$.
Set $\Gamma=S_n\wr S_p=\{(f,g_1,g_2,\ldots,g_n):\mbox{$f\in S_n$ and $g_1,g_2,\ldots,g_n\in S_p$} \}$, the wreath product of the symmetric
groups on $[n]$ and $[p]$. For $\sigma=(f,g_1,g_2,\ldots,g_n)\in\Gamma$ and
$\{(1,\ell_1),(2,\ell_2),\ldots,(n,\ell_n)\}\in\mathcal{L}_{p}$,
define
$$\sigma(\{(1,\ell_1),\ldots,(n,\ell_n)\})=\{(f(1),g_{1}(\ell_1)),
\ldots,  (f(n),g_{n}(\ell_n))\}.$$ Then $\Gamma$ acts
transitively on $\mathcal{L}_{p}$. In other words, the graph
$\mathcal{L}_{p}$ is vertex-transitive. Moreover, every intersecting
subfamily of the labeled  set  $\mathcal{L}_{p}$ corresponds to an
independent set of the graph $\mathcal{L}_{p}$. In the sequel we
shall alternatively use the terms ``set" and ``graph" when referring to $\mathcal{L}_{p}$.

For a graph $G$, let $\alpha(G)$ denote the independence number of
$G$. Given a subset $A$  of $V(G)$, we define
\begin{align*}N_G(A)=\{b\in V(G):\mbox{$\{a,b\}\in E(G)$ for some $a\in A$}\}
\end{align*}
\begin{align*}\overline{N}_G(A)=V(G)-N_G(A).\end{align*}
If $G$ is clear from the context, for simplicity, we will omit the
index $G$. For $B\subseteq V(G)$, by $G[B]$ we denote the induced
subgraph of $G$.  For short, we abbreviate  $\alpha(G[B])$ to
$\alpha(B)$.

 For the labeled set $\mathcal{L}_{p}$ we  construct another graph
$\widehat{\mathcal{L}}_{p}$, whose vertex set
 is the set $\{(A,B)\in
\mathcal{L}_{p}\times\mathcal{L}_{p}: A\cap B\neq\emptyset\}$, and
$(A_1,B_1)$ and $(A_2,B_2)$ are non-adjacent if and only if $A_1\cap
B_2\neq \emptyset$ and $B_1\cap A_2\neq\emptyset$. By definition it
is easy to see that if  $\mathcal{A}$ and $\mathcal{B}$
 are cross-intersecting subfamilies of $\mathcal{L}_{p}$, then $\mathcal{A}\times
\mathcal{B}$ is an independent set of $\widehat{\mathcal{L}}_{p}$.
Therefore,
$|\mathcal{A}||\mathcal{B}|\leq\alpha(\widehat{\mathcal{L}}_{p})$.
To complete the proof of Theorem \ref{mr}, it suffices to determine
the size and  structure of the maximum independent sets in
$\widehat{\mathcal{L}}_{p}$.

Note that the action of $\Gamma$ on $\mathcal{L}_{p}$ induces an
action on  the graph $\widehat{\mathcal{L}}_{p}$ defined by
$\sigma(A,B)=(\sigma(A),\sigma(B))$ for $\sigma\in\Gamma$ and
$(A,B)\in \widehat{\mathcal{L}}_{p}$.
 For $1\leq i\leq n$, set
$\widehat{\mathcal{L}}_{p,i}=\{(A,B)\in
\mathcal{L}_{p}\times\mathcal{L}_{p}: |A\cap B|=i\}$.  Clearly,
$|A\cap B|=|\sigma(A)\cap \sigma(B)|$ holds for all
$\sigma\in\Gamma$ and $A,B\in \mathcal{L}_{p}$, and it is easy to verify that
$\widehat{\mathcal{L}}_{p,1}, \widehat{\mathcal{L}}_{p,2},
\ldots,\widehat{\mathcal{L}}_{p,n}$ are all orbits of  $\Gamma$ on
$\widehat{\mathcal{L}}_{p}$. In other words, every induced subgraph
$\widehat{\mathcal{L}}_{p,i}$ is vertex-transitive.





In the context of vertex-transitive graphs, the following result named
the ``no-homo\-morphism lemma'' is useful to get bounds on the size of
independent sets.
\begin{lemma}[Albertson and Collins \cite{makl}]\label{ac}
Let $G$ and $G'$ be two graphs such that  $G$ is vertex-transitive
and there exists a homomorphism $\phi: G'\mapsto G$. Then
$\frac{\alpha(G)}{|V(G)|}\leq \frac{\alpha(G')}{|V(G')|},$ and the
equality holds if and only if for any independent set $I$ of
cardinality $\alpha(G)$ in $G$, $\phi^{-1}(I)$ is an independent set
of  cardinality $\alpha(G')$ in $G'$.
\end{lemma}



The following Lemma is a variation of the above.

\begin{lemma}\label{jgt}(see \cite[Theorem 3]{Cameron}) Let $G$ be a vertex-transitive graph, and $\Omega$ a transitive subgroup of $\mbox{Aut}(G)$.
Let $I$ be an independent set of
$G$, and let $B\subseteq V(G)$, then $\frac{|I|}{|V(G)|}\leq \frac{\alpha(B)}{|B|}$. Equality holds if and only if  $|I\cap
\sigma(B)|=\alpha(B)$ holds for all $\sigma\in\Omega$.
\end{lemma}
 \begin{proof}
Set  $\mathcal{D}=\{\sigma(B): \sigma\in \Omega\}$ and
$\mathcal{D}_u=\{D\in\mathcal{D}: u\in D\}$ for $u\in V(G)$.
 Note that the action of $\Omega$ on
$V(G)$ is transitive. The size of $\mathcal{D}_u$, denoted by
$r$, is independent of the choice of $u$.
 Hence,
$r|V(G)|=|B||\mathcal{D}|$. On the other hand, for each $D\in \mathcal{D}$, $I\cap D$ is also an independent set of $D$, and so $|D\cap I|\leq
\alpha(G[B])$. Therefore,
$r|I|\leq\alpha(G[B])|\mathcal{D}|$. Combining the above two inequalities
gives  $\frac{|I|}{|V(G)|}\leq\frac{\alpha(G[B])}{|B|}$, and equality holds if and only if $|D\cap I|=
\alpha(G[B])$ for each $D\in\mathcal{D}$. \end{proof}



Since all  $\widehat{\mathcal{L}}_{p,i}$ are  vertex-transitive, the
above lemma can  be applied to them.  In more detail, let
$\widehat{\mathcal{K}}$ be a subset of $\widehat{\mathcal{L}}_{p}$
such that $\widehat{\mathcal{K}}\cap \widehat{\mathcal{L}}_{p,i}\neq
\emptyset$ for $1\leq i\leq n$. Write
$\widehat{\mathcal{K}}_{i}=\widehat{\mathcal{K}}\cap
\widehat{\mathcal{L}}_{p,i}$ for $i\in[n]$. Then, for any
 independent set $\widehat{\mathcal{I}}$ of
 $\widehat{\mathcal{L}}_{p}$ and $i\in [n]$,
 $|\widehat{\mathcal{I}}\cap \widehat{\mathcal{L}}_{p,i}|\leq \alpha(\widehat{\mathcal{L}}_{p,i})$, and by Lemma \ref{jgt},
$\alpha(\widehat{\mathcal{L}}_{p,i})\leq
|\widehat{\mathcal{L}}_{p,i}|\frac{\alpha(\widehat{\mathcal{K}}_i)}{|\widehat{\mathcal{K}}_i|}$.
 Therefore,\begin{align*}|\widehat{\mathcal{I}}|=\sum_{i=1}^n|\widehat{\mathcal{I}}\cap \widehat{\mathcal{L}}_{p,i}|\leq \sum_{i=1}^k|\widehat{\mathcal{L}}_{p,i}
 |\frac{\alpha(\widehat{\mathcal{K}}_i)}{|\widehat{\mathcal{K}}_i|},\end{align*} and
  equality holds if and only if  $|\widehat{\mathcal{I}}\cap \widehat{\mathcal{L}}_{p,i}|=\alpha(\widehat{\mathcal{L}}_{p,i})$ and
  $|\widehat{\mathcal{I}}\cap \widehat{\mathcal{L}}_{p,i}\cap\sigma(\widehat{\mathcal{K}})|=\alpha(\widehat{\mathcal{K}}_i)$ for all $i=1,2,\ldots,n$ and $\sigma\in \Gamma$.
  Equivalently,  for each $\sigma\in\Gamma$,
\begin{align*}|\widehat{\mathcal{I}}\cap \sigma(\widehat{\mathcal{K}})|=\sum_{i=1}^n|\sigma^{-1}(\widehat{\mathcal{I}})\cap
 \widehat{\mathcal{K}}\cap \widehat{\mathcal{L}}_{p,i}
|=\sum_{i=1}^n\alpha(\widehat{\mathcal{K}}_i)=\alpha(\widehat{\mathcal{K}}).\end{align*}
We state it as a lemma as follows.
\begin{lemma}\label{trt} Let $\widehat{\mathcal{K}}$ be a
subset of $\widehat{\mathcal{L}}_{p}$ such that
$\widehat{\mathcal{K}}_i\neq \emptyset$ for $1\leq i\leq n$, where
$\widehat{\mathcal{K}}_{i}=\widehat{\mathcal{K}}\cap
\widehat{\mathcal{L}}_{p,i}$.  If $\widehat{\mathcal{I}}$ is an
independent set of $\widehat{\mathcal{L}}_{p}$, then
\begin{align*}|\widehat{\mathcal{I}}|\leq
\sum_{i=1}^n|\widehat{\mathcal{L}}_{p,i}
 |\frac{\alpha(\widehat{\mathcal{K}}_i)}
 {|\widehat{\mathcal{K}}_i|},\end{align*}
 and
  equality holds if and only if  $|\widehat{\mathcal{I}}\cap \sigma(\widehat{\mathcal{K}})|=\sum_{i=1}^n\alpha(\widehat{\mathcal{K}}_i)=\alpha(\widehat{\mathcal{K}})$
for each $\sigma\in\Gamma$.
\end{lemma}





 Arrange the elements
\begin{align*}(1,1),(2,1),\ldots,(n,1),(1,2),(2,2),\ldots,(n,2),\ldots,(1,p),(2,p),\ldots,(n,p)\end{align*}
in a cycle. Let $R_i$ denote the $i$th $n$-interval
$\{(s,j),(s+1,j)\ldots,(n,j),(1,j+1),\ldots,(s-1,j+1)\}$ of this
cycle, where $i=n(j-1)+s$ with $1\leq s\leq n$. Set
$\mathcal{R}=\{R_1,R_2,\ldots,R_{np}\}$ and
$\widehat{\mathcal{R}}=\{(A,B)\in\mathcal{R}\times\mathcal{R}: A\cap
B\neq \emptyset\}$. Then, $\widehat{\mathcal{R}}\subseteq
\widehat{\mathcal{L}}_{p}$ and
$\widehat{\mathcal{R}}_i=\widehat{\mathcal{R}}\cap\widehat{\mathcal{L}}_{p,i}\neq
\emptyset$ for each $1\leq i\leq n$.

%For convenience, we also use
%$\widehat{\mathcal{L}}$ to denote the induced subgraph of
%$\widehat{\mathcal{L}}_{p}$ by $\widehat{\mathcal{L}}$,
%and similarly for $\widehat{\mathcal{L}}_{p,i}$.

Clearly,  $R_i\cap R_j\neq\emptyset$ if and only if $|i-j|< n$ or
$|i+np-j|<n$ for $R_i,R_j\in\mathcal{R}$, and the subgraph
of $\mathcal{L}_{p}$ induced by $\mathcal{R}$, which will also be denoted by
$\mathcal{R}$, is isomorphic to the well-known circular graph
$\mbox{Circ}(n,np)$.  Here, the  graph $\mbox{Circ}(n,np)$ has the
vertex set $[np]$, and $i$ and $j$ are
  not adjacent if and only if $|i-j|<n$ or $|np+i-j|<n$.  Hence, $\alpha(\mathcal{R})=n$, and by
  the well-known  result of Katona \cite{Katona},
  the  maximum independent
  sets of $\mathcal{R}$ are stars. In the following we will prove that
  $\widehat{\mathcal{R}}$ is the desired subset.


   Let $\mathcal{A}$ and
  $\mathcal{B}$ be cross-intersecting subfamilies of $\mathcal{R}$. Then, it
  is obvious that $\mathcal{B}\subseteq
  \overline{N}_{\mathcal{R}}(\mathcal{A})$. For every non-empty $A\subset V(\mbox{Circ}(n,np))$($p\geq 3$),
  we have   proved
  that if $|A|\geq 2n$, $\overline{N}(A)=\emptyset$; if $|A|<2n$, $|\overline{N}(A)|+|A|\leq
  2n$, and equality holds if and only if $A=\{i,i+1,
  \ldots,i+|A|-1\}$ for some $i$ (see \cite[Lemma 3.1]{GWZ} or \cite[Lemma 2.3]{WZ}). Therefore, if $\mathcal{A}$ and $\mathcal{B}$ are both non-empty, then
  $|\mathcal{A}|+|\mathcal{B}|\leq
  |\mathcal{A}|+|\overline{N}_{\mathcal{R}}(\mathcal{A})|\leq 2n$. Note that $|\mathcal{A}||\mathcal{B}|=0$ if one of $\mathcal{A}$ and $\mathcal{B}$ is empty. So
  we have that
  $|\mathcal{A}||\mathcal{B}|\leq
  |\mathcal{A}|(2n-|\mathcal{A}|)\leq n^2$, and equality holds if
  and only if $\mathcal{A}$ and $\mathcal{B}$ are some identical maximum independent set of
  $\mathcal{R}$. Therefore, $\alpha(\widehat{\mathcal{R}})=n^2$. In the following, we give a stronger result.

\begin{lemma}\label{l4} Suppose $p\geq 4$. Then \begin{align*}\alpha(\widehat{\mathcal{R}})=n^2=\sum_{i=1}^n\alpha(\widehat{\mathcal{R}}_i),\end{align*}
 and $\widehat{\mathcal{I}}$ is a maximum independent set of $\widehat{\mathcal{R}}$ if and only if
  $\widehat{\mathcal{I}}=\mathcal{S}\times \mathcal{S}$ for some maximum independent set of
  $\mathcal{R}$.\end{lemma}
\begin{proof} For any subsets $\mathcal{A},\mathcal{B}$ of
$\mathcal{R}$ and  $1\leq i\leq n$, set
$(\mathcal{A},\mathcal{B})_i=|(\mathcal{A}\times\mathcal{B})\cap
\widehat{\mathcal{R}}_{i}|$. Let $\mathcal{S}$ be a  fixed maximum
independent set of $\mathcal{R}$ and write
$(\mathcal{S}, \mathcal{S})_{i}=a_i$. Clearly, $a_i$ does not
depend on the choice of $\mathcal{S}$, and $\alpha(\widehat
{\mathcal{R}})=n^2=\sum_{1\leq i\leq n}a_i$.
 To complete the proof, it suffices to prove that $\alpha(\widehat
{\mathcal{R}}_i)=a_i$ for each $1\leq i\leq n$. To do this, we only
need to verify that for every independent set
$\widehat{\mathcal{I}}$ of $\widehat {\mathcal{R}}$,
$|\widehat{\mathcal{I}}\cap \widehat{\mathcal{R}}_i|\leq a_i$ for
$1\leq i\leq n$.

Let $\widehat{\mathcal{I}}$ be an independent set of
$\widehat{\mathcal{R}}$. Then there exists a pair of cross-intersecting
 subfamilies $\mathcal{C}$ and $\mathcal{D}$ of $\mathcal{R}$ such that
$\widehat{\mathcal{I}}\subseteq\mathcal{C}\times \mathcal{D}$. Since
$|\mathcal{C}|+|\mathcal{D}|\leq 2n$, we may assume
$|\mathcal{C}|=s\leq n$.

We first consider the simple case when $\mathcal{C}$ consists of
consecutive elements of $\mathcal{R}$. Without loss of generality,
assume $\mathcal{C}=\{R_n,R_{n+1},\ldots, R_{n+s-1}\}$.
 For $1\leq t\leq n$, set
$\mathcal{C}_t=\{R_n,R_{n+1},\ldots, R_{n+t-1}\}$.
 Then,
$\mathcal{D}\subseteq \overline{N}(\mathcal{C}_{s})$. For each
$1\leq t<n$ and $1\leq i\leq n$,  it is easy to verify that
\begin{align*} \mathcal{C}_{t+1}\times \overline{N}(\mathcal{C}_{t+1})&=
[\mathcal{C}_{t}\times \overline{N}(\mathcal{C}_{t+1})]\cup [\{R_{n+t}\}\times\overline{N}(\mathcal{C}_{t+1})]\\
&=[\mathcal{C}_{t}\times \overline{N}(\mathcal{C}_{t})]\cup
[\{R_{n+t}\}\times\overline{N}(\mathcal{C}_{t+1})]-[\mathcal{C}_t\times
\{R_{t}\}]
\end{align*}
and $(\{R_{n+t}\},\overline{N}(\mathcal{C}_{t+1}))_i\geq
(\mathcal{C}_t, \{R_{t}\})_i$, and consequently we have
\begin{align*}(\mathcal{C}_{t+1},\overline{N}(\mathcal{C}_{t+1}))_i=(\mathcal{C}_{t},\overline{N}
(\mathcal{C}_{t}))_i+(\{R_{n+t}\},\overline{N}(\mathcal{C}_{t+1}))_i-
(\mathcal{C}_t,
\{R_{t}\})_i\geq(\mathcal{C}_{t},\overline{N}(\mathcal{C}_{t}))_i.\end{align*}
Therefore, for  $1\leq i\leq n$,
\begin{align*}(\mathcal{C},\mathcal{D})_i\leq(\mathcal{C}_s,\overline{N}(\mathcal{C}_s))_i\leq
(\mathcal{C}_{s+1},\overline{N}(\mathcal{C}_{s+1}))_i\leq \cdots\leq
(\mathcal{C}_{n},\overline{N}(\mathcal{C}_{n}))_i=a_i\end{align*} because
$\mathcal{C}_{n}=\overline{N}(\mathcal{C}_{n})$ is a maximum
independent set of $\mathcal{R}$.


Now we consider the general case. Without loss of generality, assume
 $R_{2n}\in \mathcal{D}$. Then $\mathcal{C}\subseteq
\overline{N}(\mathcal{D})\subseteq
\overline{N}(\{R_{2n}\})=\{R_{n+1},R_{n+2},\ldots,R_{3n-1}\}$.
Suppose $\mathcal{C}=\{R_{i_1},R_{i_2},\ldots,R_{i_s}\}$, where
$n+1\leq i_1< i_2<\cdots<i_s\leq 3n-1$. Noting $p\geq 4$, if $R_j\in
\overline{N}(\{R_{i_1}\})\cap \overline{N}(\{R_{i_s}\})$, then it
follows from definition that $|j-i_1|<n$ and $|j-i_s|<n$, that is,
$i_s-n+1\leq j\leq i_1+n-1$. Therefore,
$\overline{N}(\{R_{i_1}\})\cap
\overline{N}(\{R_{i_s}\})=\{R_{i_s-n+1},R_{i_s-n+2},\ldots,R_{i_1+n-1}\}=\overline{N}(\mathcal{C})$.
Set $\mathcal{C}'=\{R_{i_1},R_{i_1+1},\ldots, R_{i_s}\}$ and $\mathcal{D}'=\{R_{i_s-n+1},R_{i_s-n+2},\ldots,R_{i_1+n-1}\}$. Then, $\mathcal{C}'=\overline{N}(\mathcal{D}')$, and the
above argument implies that the inequality
$(\mathcal{C}',\mathcal{D}')_i\leq a_i$ holds for each $1\leq i\leq
n$. Note that $\mathcal{C}\subseteq \mathcal{C}'$ and
$\mathcal{D}\subseteq\mathcal{D}'$. Hence,
$(\mathcal{C},\mathcal{D})_i\leq (\mathcal{C}',\mathcal{D}')_i\leq
a_i$.\end{proof}
\noindent \textbf{Remark.} In the above result,  the condition that
$p\geq 4$ is necessary. For example, assume $n=6$ and $p=3$, set
$\mathcal{S}=\{R_1,R_2,R_3,R_4,R_5,R_6\}$,
$\mathcal{C}=\{R_6, R_{14}\}$ and
$\mathcal{D}=\{R_1,R_{11}\}$, it is easy to see that
$\mathcal{S}$ is a maximum independent set of $\mathcal{R}$ and
$\mathcal{C}\times\mathcal{D}$ is an independent set of
$\widehat{\mathcal{R}}$, but
$2=(\mathcal{S},\mathcal{S})_1<(\mathcal{C},\mathcal{D})_1=3\leq
\alpha(\widehat{\mathcal{R}}_1)$, and so
$\sum_{i=1}^6\alpha(\widehat{\mathcal{R}}_i)>\sum_{i=1}^6(\mathcal{S},\mathcal{S})_i=\alpha(\widehat{\mathcal{R}})$.


\section{Proof of Theorem \ref{mr}}
In this section we complete the proof of Theorem~\ref{mr}.

\begin{proof}[Proof of Theorem~\ref{mr}]

Take a  maximum independent set $\mathcal{S}'$ of $\mathcal{L}_{p}$
and set $\widehat{\mathcal{I}}'=\mathcal{S}'\times\mathcal{S}'$.
Then  $\widehat{\mathcal{I}}'$ is an independent set of
$\widehat{\mathcal{L}}_{p}$ with
$|\widehat{\mathcal{I}}'|=p^{2n-2}$. Note that
$\frac{\alpha(\mathcal{R})}{|\mathcal{R}|}=
  \frac{\alpha(\mathcal{L}_{p})}{|\mathcal{L}_{p}|}=\frac{|\mathcal{S}'|}{|\mathcal{L}_{p}|}=\frac1p$.
For each $\sigma\in\Gamma$,
   Lemma \ref{jgt} implies $|\mathcal{S}'\cap \sigma(\mathcal{R})|=\alpha(\mathcal{R})=n$, that is to say, $|\widehat{\mathcal{I}}'\cap \sigma(\widehat{\mathcal{R}})|=n^2$, and so the equalities $|\widehat{\mathcal{I}}'\cap \sigma(\widehat{\mathcal{R}})|=\alpha(\widehat{\mathcal{R}})=\sum_{i=1}^n\alpha(\widehat{\mathcal{R}}_i)$ hold by Lemma \ref{l4}. Then, it follows from Lemma \ref{trt} that  $p^{2n-2}=|\widehat{\mathcal{I}}'|=
\sum_{i=1}^n|\widehat{\mathcal{L}}_{p,i}
 |\frac{\alpha(\widehat{\mathcal{R}}_i)}
 {|\widehat{\mathcal{R}}_i|}$. Therefore, for every independent set $\widehat{\mathcal{I}}$ of $\widehat{\mathcal{L}}_p$, we have $|\widehat{\mathcal{I}}|\leq \sum_{i=1}^n|\widehat{\mathcal{L}}_{p,i}
 |\frac{\alpha(\widehat{\mathcal{R}}_i)}
 {|\widehat{\mathcal{R}}_i|}=p^{2n-2}$. Furthermore, the equality holds if and only if
$|\widehat{\mathcal{I}}\cap
\sigma(\widehat{\mathcal{R}})|=\alpha(\widehat{\mathcal{R}})$ for
all $\sigma\in\Gamma$. Then, for each $\sigma\in \Gamma$, by Lemma \ref{l4}, $\widehat{\mathcal{I}}\cap
\sigma(\widehat{\mathcal{R}})=\mathcal{S}_{\sigma}\times \mathcal{S}_{\sigma}$ for some maximum independent set $\mathcal{S}_{\sigma}$ of $\sigma(\mathcal{R})$. Set $\mathcal{S}=\cup_{\sigma\in\Gamma}\mathcal{S}_{\sigma}$. Noting that the maximality of $\widehat{\mathcal{I}}$ implies that $\widehat{\mathcal{I}}=\mathcal{C}\times\mathcal{D}$ for a pair of cross-intersecting subfamilies $\mathcal{C}$ and $\mathcal{D}$ of $\mathcal{L}_{p}$.
Then we have that $\mathcal{S}$ is an independent set and $\mathcal{S}\times\mathcal{S}\subseteq \widehat{\mathcal{I}}$. On the other hand,  it is easy to see that $|\mathcal{S}\cap \sigma(\mathcal{R})|=\alpha(\mathcal{R})$ holds for all $\sigma\in\Gamma$,
so  Lemma \ref{jgt} implies $\mathcal{S}$ is a maximum independent set of $\mathcal{L}_{p}$. Then we obtain $\widehat{\mathcal{I}}=\mathcal{S}\times\mathcal{S}$ since $|\widehat{\mathcal{I}}|=p^{2n-2}=|\mathcal{S}\times\mathcal{S}|$.   This completes the proof of Theorem~\ref{mr}.
\end{proof}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The author is greatly indebted to
the anonymous referees for giving
  useful comments and suggestions that have considerably improved the
  manuscript. He  also thanks Jun Wang for giving many valuable 
  suggestions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}

\begin{thebibliography}{10}

\bibitem{makl}
M.O. Albertson and K.L. Collins, Homomorphisms of $3$-chromatic
graphs, Discrete Math., 54: 127--132, 1985.


\bibitem{Berge}
C. Berge, Nombres de coloration de 1'hypegraphe h-parti complet, in:
Hypergraph Seminar(Columbus, Ohio 1972), volume 411 of Lecture Notes in Math.,
Page 13--20. Springer, 1974.


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

\bibitem{Bollobas}
B. Bollob\'as and I. Leader, An Erd\H{o}s-Ko-Rado theorem for signed
sets, Comput. Math. Applic.,  34: 9--13, 1997.

\bibitem{borg}
P. Borg, Intersecting and cross-intersecting families of labeled
sets, Electron. J. Combin., 15: N9, 2008.

\bibitem{borg-dm}
P. Borg,  On t-intersecting families of signed sets and
permutations, Discrete Math., 309:  3310--3317, 2009.

\bibitem{borg5}
P. Borg, Extremal $t$-intersecting sub-families of hereditary
families, J. London Math. Soc., 79:  167--185, 2009.

\bibitem{pborg1}
P. Borg, A short proof of a cross-intersection theorem of Hilton,
Discrete Math., 309:  4750--4753, 2009.

\bibitem{pborg}
P. Borg, Cross-intersecting families of permutations, J. Combin.
Theory Ser. A,  117: 483--487, 2010.


\bibitem{borg6}
P. Borg and I. Leader, Multiple cross-intersecting families of
signed sets, J. Combin. Theory Ser. A, 117:  583--588, 2010.

\bibitem{Cameron}
P.J. Cameron, C.Y. Ku, Intersecting families of permutations,
European J. Combin., 24:  881--890, 2003.

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

 \bibitem{Dezaf}
M. Deza and P. Frankl, Erd\H{o}s-Ko-Rado theorem--22 years later,
SIAMJ. Alg. Disc. Methods, 4: 419--431, 1983.


\bibitem{Ellis} D. Ellis, E. Friedgut, H. Pilpel, Intersecting families of
permutations, J. Amer. Math. Soc., 24: 649--682, 2011.


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

\bibitem{GWZ}
X.B. Geng, J. Wang and H.J. Zhang, Structures of Independent Sets in
Direct Products of Some Vertex-transitive Graphs, Acta Math. Sin.
(Engl. Ser.), 28: 697--706, 2012.


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

\bibitem{Greene-Kleit}
        C. Greene and D.J. Kleitman, Proof techniques in the ordered sets,
        in:  Studies in Combinatorics (Math. Assn. America,
        Washington DC, 1978), pp. 22--79.

\bibitem{hilton} A.J.W. Hilton, An intersection theorem for a
collection of families of subsets of a finite set, J. London Math.
Soc., 2: 369--384, 1977.

\bibitem{Hsieh}
      W.N. Hsieh,  Intersection theorems for systems of finite vector
      spaces,  Discrete Math., 12: 1--16, 1975.

\bibitem{Katona}
G. O. H. Katona, A simple proof of the Erd\H{o}s--Ko--Rado theorem,
J. Combin. Theory Ser. B, 13:183--184, 1972.


\bibitem{LIW}
 Y.S. Li, J. Wang, Erd\H{o}s-Ko-Rado-Type Theorems for Colored Sets,  Electron. J.
Combin., 14(1), 2007.


\bibitem{Livingston}
M. L. Livingston, An ordered version of the Erd\H{o}s-Ko-Rado
theorem, J. Combin. Theory Ser. A, 26: 162--165, 1979.


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




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

\bibitem{Tokushige}
N. Tokushige, On cross t-intersecting families of sets, J. Combin.
Theory Ser. A, 117: 1167--1177, 2010.

\bibitem{wjz}
J. Wang, S.J. Zhang, An Erd\H{o}s-Ko-Rado-type theorem in Coxeter
groups, European J. Combin., 29: 1112--1115, 2008.
\bibitem{WZ}
J. Wang and H.J. Zhang, Intersecting families in a subset of boolean
lattices, Electron. J. Combin., 18(P237), 2011.


 %\bibitem{GWZ}
 %X.B. Geng, J. Wang and H.J. Zhang, Structures of Independent Sets in Direct Product of Some Vertex-transitive Graphs, to appear


\bibitem{wz}
J. Wang and H.J. Zhang, Cross-intersecting families and primitivity
of symmetric systems, J. Combin. Theory Ser. A, 118: 455--462, 2011.


\bibitem{wz2}
J. Wang and H.J. Zhang,  Nontrivial independent sets of bipartite
graphs and cross-intersecting families, J. Combin. Theory Ser. A,
120: 129--141, 2013.


\end{thebibliography}

\end{document}