Compression and Erd\H os-Ko-Rado graphs
Fred Holroyd$^{1}$ and John Talbot$^{2}$
[3mm] $^{1}$Department of Pure Mathematics
Walton Hall
Milton Keynes MK7~6AA
United Kingdom
OX1 4JD
For a graph $G$ and integer $r\geq 1$ we denote the collection of independent $r$-sets of $G$ by $\I^{(r)}(G)$. If $v\in V(G)$ then $\I_v^{(r)}(G)$ is the collection of all independent $r$-sets containing $v$. A graph $G$, is said to be $r$-EKR, for $r\geq 1$, iff no intersecting family $\A\subseteq \I^{(r)}(G)$ is larger than $\max_{v\in V(G)}|\I^{(r)}_v(G)|$. There are various graphs which are known to have his property: the empty graph of order $n\geq 2r$ (this is the celebrated Erd\H os-Ko-Rado theorem), any disjoint union of at least $r$ copies of $K_t$ for $t\geq 2$, and any cycle. In this paper we show how these results can be extended to other classes of graphs via a compression proof technique. In particular we show that any disjoint union of at least $r$ complete graphs, each of order at least two, is $r$-EKR. We also show that paths are $r$-EKR for all $r\geq 1$.
math0307072.tex
\documentclass[12pt]{article}
\usepackage[fleqn]{amsmath}
\usepackage{latexsym}
\usepackage[dvips]{graphicx}
\usepackage{psfrag}
\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{con}[thm]{Conjecture}
\newtheorem{obs}[thm]{Observation}
\newtheorem{cla}{Claim}
\newtheorem{cas}{Case}
\def\qed{$\hfill \Box$}
\def\prf{\emph{Proof: }} 
\def\b{\backslash}
\def\con{/}
\def\split{\uparrow}
\def\indr{\mc{I}^{(r)}(G)}
\def\indrm{\mc{I}^{(r-1)}(G)}
\def\del{\!\downarrow\!}
\def\tr{\textrm}
\def\mb{\mathbf}
\def\A{\mathcal{A}}
\def\B{\mathcal{B}}
\def\C{\mathcal{C}}
\def\D{\mathcal{D}}
\def\E{\mathcal{E}}
\def\F{\mathcal{F}}
\def\I{\mathcal{I}}
\def\mc{\mathcal}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
\begin{document}
\title{Compression and Erd\H os-Ko-Rado graphs}
\author{Fred Holroyd$^{1}$ and John Talbot$^{2}$\\[3mm]
$^{1}$Department of Pure Mathematics, The Open University,\\
Walton Hall, Milton Keynes MK7~6AA, United Kingdom\\
\texttt{f.c.holroyd@open.ac.uk}\\ \\
$^{2}$Merton College and the Mathematical Institute,\\
Oxford University, OX1 4JD\\
\texttt{talbot@maths.ox.ac.uk}}
\maketitle
\begin{abstract}
For a graph $G$ and integer $r\geq 1$ we denote the collection of independent $r$-sets of $G$ by $\I^{(r)}(G)$. If $v\in V(G)$ then $\I_v^{(r)}(G)$ is the collection of all independent $r$-sets containing $v$. A graph $G$, is said to be \emph{$r$-EKR}, for $r\geq 1$, iff no intersecting family $\A\subseteq \I^{(r)}(G)$ is larger than $\max_{v\in V(G)}|\I^{(r)}_v(G)|$. There are various graphs which are known to have his property: the empty graph of order $n\geq 2r$ (this is the celebrated Erd\H os-Ko-Rado theorem), any disjoint union of at least $r$ copies of $K_t$ for $t\geq 2$, and any cycle. In this paper we show how these results can be extended to other classes of graphs via a compression proof technique.

In particular we show that any disjoint union of at least $r$ complete graphs, each of order at least two, is $r$-EKR. We also show that paths are $r$-EKR for all $r\geq 1$.
\end{abstract}
\section{Introduction}
An \emph{independent} set in a graph $G=(V,E)$, is a subset of the vertices not containing any edges. For an integer $r\geq 1$ we denote the collection of independent $r$-sets of $G$ by\[
\I^{(r)}(G)=\{A\subset V(G):|A|=r\tr{ and $A$ is an independent set}\}.\]
If $v\in V(G)$ then the collection of independent $r$-sets containing $v$ is \[
\I_v^{(r)}(G)=\{A\in \I^{(r)}(G):v\in A\}.\] Such a family is called a \emph{star}.

A graph $G$ is \emph{$r$-EKR} iff no intersecting family of independent $r$-sets is larger than the largest star in $\I^{(r)}(G)$. If $G$ is $r$-EKR and any intersecting family $\A\subseteq\I^{(r)}(G)$ of maximum size is a star then $G$ is said to be \emph{strictly $r$-EKR}.

In this setting the classical Erd\H os-Ko-Rado theorem can be stated as follows.
\begin{thm}[Erd\H os-Ko-Rado\cite{EKR}]\label{EKR}If $E_n$ is the empty graph of order $n$ then $E_n$ is $r$-EKR for $n\geq 2r$ and strictly so for $n>2r$. 
\end{thm}
There are a number of other recent results of this type. 
\begin{thm}[Bollob\'as and Leader\cite{BL}]\label{BLthm}
If $n \geq r$, $t\geq 2$ and $G$ is the disjoint union of $n$ copies of $K_t$ then $G$ is $r$-EKR and strictly so unless $t=2$ and $n=r$.
\end{thm}
The following result was previously a conjecture of Holroyd and Johnson \cite{HJ}.
\begin{thm}[Talbot\cite{JT}]\label{cyclethm}
For $1\leq k \leq n$ the $k^{\tr{th}}$ power of the $n$-cycle, $C_n^k$, is the graph with vertex set $[n]=\{1,2,\ldots,n\}$ and edges between $a,b \in [n]$ iff $1\leq |a-b\mod n|\leq k$. Then $C_n^k$ is $r$-EKR for all $r\geq 1$ and strictly so unless $n=2r+2$ and $k=1$.
\end{thm}

Although this is not made explicit in \cite{JT}, the proof of Theorem \ref{cyclethm} uses a type of compression that is essentially equivalent to contracting an edge in the underlying graph. In the present paper we wish to show how this idea can be used to show that various other graphs are also $r$-EKR.

In particular we have the following result extending Theorem \ref{BLthm}.

\begin{thm}\label{completethm}If $G$ is the disjoint union of $n\geq r$ complete graphs each of order at least two then $G$ is $r$-EKR.
\end{thm} 

We also show that an analogue of Theorem \ref{cyclethm} holds for paths.
\begin{thm}\label{paththm}
For $1\leq k \leq n$ the $k^{\tr{th}}$ power of the $n$-path, $P_n^k$, is the graph with vertex set $[n]=\{1,2,\ldots,n\}$ and edges between $a,b \in [n]$ iff $1\leq |a-b|\leq k$. Then $P_n^k$ is $r$-EKR for all $r\geq 1$.
\end{thm}

Our main results are Theorems \ref{completethm} and \ref{paththm} but the proof technique also extends to other types of graph and our final theorem gives
 a large class of graphs which are all $r$-EKR.

\begin{thm}\label{messthm}
If $G$ is a disjoint union of $n\geq 2r$ complete graphs, cycles and paths, including an isolated singleton, then $G$ is $r$-EKR.\end{thm}

In  order to state the two key lemmas we require some notation.

If $e$ is an edge of the graph $G=(V,E)$ we define $G/e$ to be the graph obtained from $G$ by contracting the edge $e$. We also define $G\del e$ to be the graph obtained from $G$ by removing the vertices in $e$ as well as their neighbours. As usual we denote the neighbours of a vertex $v$ by $\Gamma(v)$.

The following two technical lemmas relate intersecting families and stars in $\I^{(r)}(G)$ to intersecting families and stars in $\I^{(r)}(G/e)$ and $\I^{(r-1)}(G\del e)$. These will enable us to prove our main results by induction.

\begin{lem}
\label{partlem}
Let $G=(V,E)$ be a graph and $\A\subseteq \mc{I}^{(r)}(G)$ be an intersecting family. If $e=\{v,w\}\in E$ is an edge in $G$ then there exist families $\B,\C,\D$ and $\E$ satisfying:
\begin{itemize}
\item[(i)] $|\A|=|\B|+|\C|+|\D|+|\E|$.
\item[(ii)] $\B\subseteq \mc{I}^{(r)}(G\con e)$ is intersecting.
\item[(iii)] $\C\subseteq \mc{I}^{(r-1)}(G\del e)$ is intersecting.
\item[(iv)] $\D=\{A\in\A:v\in A\tr{ and }\Gamma(w)\cap (A\b\{v\})\neq \emptyset\}$.
\item[(v)] $\E=\{A\in\A:w\in A\tr{ and }\Gamma(v)\cap (A\b\{w\})\neq \emptyset\}$.
\item[(vi)] If $C\in \C$ and $F\in\D\cup \E$ then $C\cap F\cap V(G\del e)\neq \emptyset$.
\item[(vii)] If $D\in \D$ and $E\in\E$ then $D\cap E\cap V(G\del e)\neq \emptyset$.
\end{itemize}
\end{lem}

\begin{lem}
\label{starlem}If $e=\{v,w\}$ is an edge in the graph $G=(V,E)$ and $x\in V(G\del e)$ then
\[
|\mc{I}_x^{(r)}(G)|=|\mc{I}_x^{(r)}(G\con e)|+ |\mc{I}_x^{(r-1)}(G\del e)|+|\D_x|+|\E_x|.\] Where \[\D_x=\{A\in \mc{I}_x^{(r)}(G):v\in A\tr{ and }\Gamma(w)\cap (A\b\{v\})\neq \emptyset\}\] and \[\E_x=\{A\in \mc{I}_x^{(r)}(G):w\in A\tr{ and }\Gamma(v)\cap (A\b\{w\})\neq \emptyset\}.\]
\end{lem}

\section{Proofs}
\emph{Proof of Lemma \ref{partlem}:}
Let $\A\subseteq \indr$ be intersecting. We consider the effect of contracting an edge $e=\{v,w\}$ in $G$. We define a contraction function, $c:V(G)\to V(G/e)$ by \[
c(x)=\left\{\begin{array}{ll}v, & x=w,\\ x,& x\neq w.\end{array}\right.\]
Let \begin{eqnarray*}
\B&=&\{c(A):A\in \A\tr{ and $c(A)\in\I^{(r)}(G/e)$}\},\\
 \C&=&\{A\b\{v\}:v\in A\in\A\tr{ and }A\b\{v\}\cup\{w\}\in\A\},\\
\D&=&\{A\in\A:v\in A\tr{ and }\Gamma(w)\cap (A\b\{v\})\neq \emptyset\},\\
\E&=&\{A\in\A:w\in A\tr{ and }\Gamma(v)\cap (A\b\{w\})\neq \emptyset\}.
\end{eqnarray*}
If $A,B\in\A$ then $c(A)=c(B)$ iff $A\Delta B=\{v,w\}$. Hence\[ |\{A\in\A:c(A)\in\I^{(r)}(G/e)\}|=|\B|+|\C|.\] Also if $A\in\A$ then $c(A)\not\in \I^{(r)}(G/e)$ iff $A\in \D\cup \E$. Hence $|\A|=|\B|+|\C|+|\D|+|\E|$, which is (i).


The fact that $\B\subseteq\I^{(r)}(G/e)$ is  an intersecting family follows simply because $\A$ is intersecting, so (ii) holds.  

If $C\in\C$ then $C\cup\{v\},C\cup\{w\}\in \A$ hence $C\in I^{(r-1)}(G\del e)$.
With a little more thought it is also clear that $\C$ is an intersecting family. Let $C,D\in\C$, if $C\cap D=\emptyset$ then $\A$ contains the two disjoint sets $C\cup\{v\}$ and $D\cup\{w\}$. This contradicts the fact that $\A$ is intersecting. Hence $\C$ is also intersecting, and so (iii) holds.

The definitions of the families $\D$ and $\E$ give (iv) and (v).

To see that (vi) holds let $C\in \C$, so $C\cup\{v\},C\cup\{w\}\in \A$. If $F\in\D\cup\E\subseteq \A$ then $(C\cup\{w\})\cap F\neq\emptyset$ and $(C\cup\{v\})\cap F\neq\emptyset$ but either $v\not\in F$ or $w \not\in F$. Hence $C\cap F\cap V(G\del e)\neq\emptyset$.

Finally if $D\in\D$ and $E\in \E$ then $v\in D$ and $w\in E$ imply that \[D\cap E\cap (\Gamma(v)\cup\Gamma(w)\cup\{v,w\})=\emptyset.\] So $D\cap E\neq\emptyset$ implies that (vii) must hold. \qed

\emph{Proof of Lemma \ref{starlem}:} This follows similarly to the proof of Lemma \ref{partlem}, via contracting the edge $e=\{v,w\}$. Let $c:V(G)\to V(G/e)$ be as defined in the proof of Lemma \ref{partlem}. 

Then $c$ is a surjection between the families $\I_x^{(r)}(G)\b(\D_x\cup \E_x)$ and $\I_x^{(r)}(G/e)$. Moreover $c(A)=c(B)$ iff $A\Delta B=\{v,w\}$ and the number of sets in $\I_x^{(r)}(G/e)$ with two preimages under $c$ is exactly $|\I_x^{(r-1)}(G\del e)|$. Hence
\[
|\mc{I}_x^{(r)}(G)|=|\mc{I}_x^{(r)}(G\con e)|+ |\mc{I}_x^{(r-1)}(G\del e)|+|\D_x|+|\E_x|.\] 
\qed

\emph{Proof of Theorem \ref{completethm}:} We prove this result by induction on $r$. It is clearly true for $r=1$ so we may suppose that $r\geq 2$ and the result holds for smaller values of $r$. 

We now use induction on the number of vertices in $G$. Theorem \ref{BLthm} implies that the result holds when $G$ consists of $n\geq r$ copies of $K_t$, for $t\geq 2$. So let \[G=K_{t_1}\cup\cdots\cup K_{t_n},\] with $2\leq t_1\leq t_2\leq \cdots \leq t_n$, not all equal. We may suppose that the result holds for all graphs of the correct form with fewer vertices.

Suppose that $\A\subseteq\I^{(r)}(G)$ is intersecting. Let $v,w\in K_{t_n}$, we will  contract the edge $e=\{v,w\}$. Then \[
G/e= K_{t_1}\cup\cdots\cup K_{t_n-1},\] and \[ G\del e= K_{t_1}\cup\cdots\cup K_{t_{n-1}}.\] 
Using the notation of Lemma \ref{partlem} we have $\D=\E=\emptyset$. Hence by Lemma \ref{partlem} (i) 
\begin{equation}\label{eq1}
|\A|=|\B|+|\C|.\end{equation}  Then for any $x\in K_{t_1}\subseteq G\del e$ we have, in notation of Lemma \ref{starlem}, that $\D_x=\E_x=\emptyset$. So Lemma \ref{starlem} implies that \begin{equation}\label{eq2}|\I_x^{(r)}(G)|=|\I_x^{(r)}(G/e)|+|\I_x^{(r-1)}(G\del e)|.\end{equation} 


The observation that $t_1\leq t_i$, for any $1\leq i\leq n$, implies that we also have \begin{equation}\label{eq3}
 |\I_x^{(r)}(G/e)|=\max_{v\in V(G/e)}|\I_v^{(r)}(G/e)|\end{equation} and
\begin{equation}\label{eq4}
 |\I_x^{(r-1)}(G\del e)|=\max_{v\in V(G\downarrow e)}|\I_v^{(r-1)}(G\del e)|.\end{equation}
Now $t_n\geq 3$ so $G/e$ is a smaller graph of the correct form and hence is $r$-EKR. Then Lemma \ref{partlem} (ii) and (\ref{eq3}) imply that \begin{equation}\label{eq5}
|\B|\leq |\I_x^{(r)}(G/e)|.\end{equation} Also $G\del e$ is $(r-1)$-EKR, since the result holds for smaller values of $r$. So Lemma \ref{partlem} (iii) and (\ref{eq4}) imply that \begin{equation}\label{eq6}
|\C|\leq |\I_x^{(r-1)}(G\del e)|\end{equation} 
Hence, using equations (\ref{eq1}), (\ref{eq2}), (\ref{eq5}) and (\ref{eq6}), we obtain
\[
|\A|\leq |\I_x^{(r)}(G)|.\]\qed

\emph{Proof of Theorem \ref{paththm}:}
We first note that for any $n$, $r$ and $k$\[\max_{x\in V(P_n^k)}|\mc{I}_x^{(r)}(P_n^k)|\] is achieved  by taking $x\in\{1,n\}$. 

Again we prove this result by induction on $r$. The result clearly holds for $r=1$ so we may assume $r\geq 2$ and that the result is true for smaller values of $r$. 

We now prove the result for $r$ by induction on $n$. For $n<(r-1)k+r$ there is nothing to prove since $\I^{(r)}(P_n^k)$ is empty. For $n=(r-1)k+r$ the result also holds (since there is only one set in $\I^{(r)}(P_n^k)$). So we may assume that $n\geq (r-1)k+r+1$ and that the result holds for smaller values of $n$. In particular $n\geq k+3$.

Let $\A\subseteq \mc{I}^{(r)}(P_n^k)$ be intersecting. Set $w=n$, $v=n-1$ and $e=\{n-1,n\}$, and apply Lemma \ref{partlem}. Let $\B,\C,\D$ and $\E$ be the families defined in Lemma \ref{partlem}. In this case $G/e$ is $P_{n-1}^k$, while $G\del e$ is $P_{n-k-2}^k$. Note that $n\geq k+3$ implies that $G\del e$ is non-empty.

We see that in this case $\D$ is empty and \[\E=\{A\in\A: n,n-k-1\in A\}.\] Let \[\F=\{A\b\{n\}:A\in\E\}\] and consider $\C\cup\F$. Note that this is a disjoint union since $n-k-1$ belongs to every set in $\F$ but to no set in $\C$. Hence \begin{equation}\label{eq6b}
|\C\cup \F|=|\C|+|\F|=|\C|+|\E|.\end{equation}

Parts (iii) and (vi) of Lemma \ref{partlem} imply that $\C\cup\F$ is an intersecting family of independent $(r-1)$-sets in the subgraph of $P_n^k$ induced by $\{1,2,\ldots,n-k-1\}$, which is $P_{n-k-1}^k$. Our inductive hypothesis for $r$ then implies that \begin{equation}\label{eq7}|\C\cup\F|\leq |\mc{I}_1^{(r-1)}(P_{n-k-1}^k)|.\end{equation}
Now $G/e$ is $P_{n-1}^k$, so part (ii) of Lemma \ref{partlem} and our inductive hypothesis for $n$ imply that \begin{equation}\label{eq8}|\B|\leq |\mc{I}_1^{(r)}(P_{n-1}^k)|.\end{equation}
Lemma \ref{partlem} (i), together with equations (\ref{eq6b}), (\ref{eq7}) and (\ref{eq8}) imply that
\begin{equation}\label{eq9}
|\A|=|\B|+|\C|+|\D|+|\E|\leq |\I_1^{(r)}(P_{n-1}^k)|+|\I_1^{(r-1)}(P_{n-k-1}^{k})|.\end{equation}


Applying Lemma \ref{starlem} we obtain \begin{equation}\label{eq10}|\mc{I}_1^{(r)}(P_n^k)|=|\mc{I}_1^{(r)}(P_{n-1}^k)|+|\mc{I}_1^{(r-1)}(P_{n-k-2}^k)|+|\E_1|,\end{equation}
where \[
\E_1=\{A\in \I_1^{(r)}(P_n^k):n-k-1,n\in A\}.\]
Then it is easy to check that 
\[
|\I_1^{(r-1)}(P_{n-k-1}^k)|=|\I_1^{(r-1)}(P_{n-k-2}^k)|+|\E_1|,\]

  and so equations (\ref{eq9}) and (\ref{eq10}) imply that \[|\A|\leq|\mc{I}_1^{(r)}(P_n^k)|.\] as required.
\qed

We turn finally to a proof of Theorem \ref{messthm}. The key ideas have already been presented in Lemmas \ref{partlem} and \ref{starlem} as well as in the proofs of Theorems \ref{completethm} and \ref{paththm}. For this reason our proof is essentially a sketch. %The interested reader should easily be able to fill in the details.

\emph{Proof of Theorem \ref{messthm}:} We will say that a graph $G$ is \emph{$r$-mixed}, for an integer $r\geq 1$, if it satisfies the conditions of Theorem \ref{messthm}. So $G$ is $r$-mixed iff it is the disjoint union of at least $2r$ complete graphs, paths and cycles, including at least one isolated singleton.

We prove the result by induction on $r$. It is clearly true for $r=1$ so we may suppose $r\geq 2$ and that the result holds for smaller values of $r$.

We now prove the result for $r$ by induction on $|V(G)|$. If $G$ is $r$-mixed then $|V(G)|\geq 2r$ with equality iff $G=E_{2r}$.  So if $|V(G)|=2r$ then Theorem \ref{EKR} implies that $G$ is $r$-EKR. Hence we may suppose that $|V(G)|> 2r$ and that any $r$-mixed graph with fewer vertices is also $r$-EKR.

Now either $G$ is an empty graph of order at least $2r+1$, in which case the result holds by Theorem \ref{EKR}, or $G$ contains an edge. So we may suppose that $G$ contains an edge $e=\{v,w\}$. We also know that $G$ contains an isolated singleton $x$. 

It is easy to check that if $H$ is one of the three graphs $G$, $G/e$ or $G\del e$,  and $s\leq r$ then \begin{equation}\label{lasteq}
|\I_x^{(s)}(H)|=\max_{v\in V(H)}|\I_v^{(s)}(H)|.\end{equation}
Also $G/e$ is $r$-mixed and has less vertices than $G$, while $G\del e$ is $(r-1)$-mixed. Hence  by our two inductive hypotheses $G/e$ is $r$-EKR and $G\del e$ is $(r-1)$-EKR. The result then follows by applying Lemmas \ref{partlem} and \ref{starlem} together with (\ref{lasteq}). The details depend on whether $e$ was an edge from a complete graph, a cycle or a path but follow similarly to the proofs of Theorems \ref{cyclethm}, \ref{completethm} and \ref{paththm}.\qed 
\begin{thebibliography}{}
\bibitem{BL} B. Bollob\'as and I. Leader, An Erd\H os-Ko-Rado
theorem for signed sets, \emph{Computers Math. Applic.}
\textbf{34} (11) (1997), 9-13.
\bibitem{EKR} P. Erd\H os, C. Ko and R. Rado, Intersection theorems for systems of finite sets, \emph{Quart. J. Math. Oxford (2)} \textbf{12} (1961), 313-320.
\bibitem{HJ} F.C. Holroyd, `Problem 338 (BCC16.25), Erd\H os-Ko-Rado at the court of King Arthur', \emph{Discrete Mathematics} 197/198 (1999), 812.
\bibitem{JT} J. Talbot, Intersecting families of separated sets, \emph{J. London Math. Soc.} (to appear)
\end{thebibliography}
\end{document}
A very similar argument allows us to show that if $G$ is $r$-EKR and contains a vertex of degree 1 then  joining this vertex to a new vertex gives another $r$-EKR graph.
\begin{thm}\label{oneexthm}
Let $G=(V,E)$ be $r$-EKR and suppose $\{v,x\}\in E$ with $\deg(v)=1$. If $y\in V\b\{v,x\}$ is an $r$-centre for $G$ and an $(r-1)$-centre for $G\b\{v\}$ then $y$ is an $r$-centre for $G^*$, where $G^*$ is the graph obtained from $G$ by joining a new vertex $w$ to $v$.
\end{thm}
\prf Simlarly to previous theorem.$\hfill \Box$

The next theorem shows that unions of $n\geq 2r$ copies of paths, cycles, or complete graphs are all $r$-EKR. First we require two lemmas.
\begin{lem}\label{pathlem}
If $P$ is a path with $n$ vertices, say $V(P)=\{1,2,\ldots,n\}$ and for $i\in V(P)$ we denote $\alpha_i^{(r)}=|\{\A\in \mc{I}^{(r)}(P):i\in A\}$. Then \begin{itemize}
\item[(i)] If $i$ is odd and $j$ is even then $\alpha_i^{(r)}\geq \alpha_j^{(r)}$,
\item[(ii)] If $1\leq i \leq j \leq \lfloor n/2 \rfloor$ are both odd then $\alpha_i^{(r)}\geq \alpha_{j}^{(r)}$.\end{itemize}
\end{lem} 
\begin{lem}
\label{centrelem}
Let $G$ be a disjoint union of complete graphs, cycles and paths, not just containing complete graphs. For $x\in V(G)$ let $\alpha_x^{(r)}(G)=|\{\A\in \mc{I}^{(r)}(G):x\in A\}$. Then $\alpha_x^{(r)}(G)$ is maximized by taking $x$ to be (whichever is the first to exist in $G$):\begin{itemize}\item[(i)] an endpoint of a shortest odd length path, \item[(ii)] an endpoint of a shortest even length path, \item[(iii)] a vertex in a shortest even length cycle, \item[(iv)] a vertex in a shortest odd length cycle. \end{itemize}
\end{lem}
\prf  First suppose that $G$ contains a path. If the graph contains a singleton then the result holds trivially, so fix a shortest path $P$ containing at least two vertices. Let $z$ be an endpoint of $P$ and $w$ its unique neighbour. Now let $x\in V(G)$. We consider three cases, either $x$ belongs to a complete graph of order at least 3 or it belongs to a cycle of order at least 4 or it belongs to a path. 

In the first case $x\in V(K_t)$ for some $t\geq 3$. Now if $A\in \mc{I}_x^{(r)}(G)$ then either $A$ contains $z$ or $A\b\{x\}\cup \{z\}\in \mc{I}_z^{(r)}(G)$ the only problem is if $x,w\in A$. But we can then form $t-1\geq 2$ new independent $r$-sets containing $z$ by replacing $w$ by $z$ and $x$ by each of its $t-1$ neighbours in turn. Hence $\alpha_x^{(r)}(G)\leq \alpha_z^{(r)}(G)$.

In the second case we have $x\in C_k$ for some $k \geq 4$. We proceed as before and again the only problem is if $x,w\in A$. But we can now form a new independent $r$-set containing $z$ by replacing $w$ by $z$ and then rotating $A\cap C_k$ clockwise one position. Hence $\alpha_x^{(r)}(G)\leq \alpha_z^{(r)}(G)$.

In the third case we have $x\in Q$ for some path $Q$ with $|Q|\geq |P|$. This time we first show that if $a$ in an endpoint of $Q$ then $\alpha_x^{(r)}(G)\leq \alpha_a^{(r)}(G)$. Let $A\in \mc{I}_x^{(r)}(G)$, replace $x$ by $a$ and shift all those points in $A$ between $a$ and $x$ down one position (away from $a$). Then $A\in \mc{I}_a^{(r)}(G)$ and so $\alpha_x^{(r)}(G)\leq \alpha_a^{(r)}(G)$.
$\hfill \Box$ 
\begin{thm}\label{unionthm}
If $G=G_1\cup G_2\cup\cdots \cup G_n$ and each of the $G_i$'s is a path, cycle or complete graph then $G$ is $r$-EKR for $n\geq 2r$.
\end{thm}
\prf Let us suppose that $a+b+c=n$, $a,b,c\geq 0$, $G_1,\ldots,G_a$ are all complete graphs, $G_{a+1},\ldots,G_{a+b}$ are all paths and $G_{a+b+1},\ldots,G_{a+b+c}$ are all cycles. Assume also that inside each subcollection the graphs are non-decreasing in size.

We prove this by induction on the number of vertices in $G$. If $|V(G)|=2r$ then $G$ is simply the disjoint union of $2r$ vertices and so the result holds by the Erd\H os-Ko-Rado theorem. 
$\hfill \Box$



We now turn to unions of multipartite graphs and prove a simple lemma
\begin{lem}
Let $G=\bigcup\limits_{i=1}^tK_{a_i}(b_i)$, with $K_{a_i}(b_i)=V_{i,1}\cup V_{i,2} \cup\cdots \cup V_{i,a_i}$. If $\A\subseteq \mc{I}^{(r)}(G)$ is intersecting then there is another intersecting family $\B\subseteq \mc{I}^{(r)}(G)$ such that $|\A|=|\B|$ with the property that if $A,B\in \B$ then $A\cap B\cap V\neq \emptyset$, where $V=\bigcup\limits_{i=1}^t V_{i,1}$.
\end{lem}
\prf 
We describe a compression operation which for obvious reasons we call down-compression that will prove useful. Fix $1\leq i \leq t$ and $1\leq j < k \leq a_i$. We now compress $\A$ to give a new family $\B$ as follows. First if $A\in \A$ and $A\cap V_{i,k}=\emptyset$ then $A\in \B$.

Now suppose $A\in \A$ and $A\cap V_{i,k}=A_k\neq \emptyset$. Let $A_j\subseteq V_{i,j}$ be obtained from $A_k$ by the obvious identity map from $V_{i,k}$ to $V_{i,j}$. Then if $(A\b A_k)\cup A_j\not\in \A$ we put $(A\b A_k)\cup A_j$ in $\B$, otherwise we put $A$ in $\B$.

From the above it is clear that $|\A|=|\B|$ and $\B\subseteq \mc{I}^{(r)}(G)$. We now show that $\B$ is also intersecting.

Suppose $A,B\in \B$ are disjoint. Then since $\A$ is intersecting we can suppose that $B\not\in \A$ so there exists $C\in\A$ such that $B$ is the compressed version of $C$. If $A\not\in A$ also, say $A$ is the compressed version of $D$ then clearly $A\cap B=\emptyset$ iff $C\cap D=\emptyset$ which is impossible. So we may suppose that $A\in \A$.

Now if $A\in\A$ has not been compressed then either $A\cap V_{i,k}=\emptyset$ in which case $A\cap C\subseteq A\cap B=\emptyset$, a contradiction since $A,C\in\A$ which is intersecting. So the only other possibility is that $A\cap V_{i,k}=A_k$ and $(A\b A_k)\cup A_j\in \A$ already (where as before $A_j$ is the copy of $A_k$ in $V_{i,j}$ produced by the identity map from $V_{i,k}$ to $V_{i,j}$). But now $((A\b A_k)\cup A_j)\cap C=\emptyset$, a contradiction since both sets belong to $\A$. Hence $\B$ is also intersecting.
$\hfill \Box$

\begin{thm}
Let $G=K_a(b)\cup K_c(d)$ with $b,d\geq 2$ and $b+d\geq 2r$ then $G$ is $r$-EKR. Moreover if $b+d > 2r$ then $G$ is strictly $r$-EKR.
\end{thm}
\prf Let $K_a(b)=V_1\cup V_2 \cdots \cup V_a$, $K_c(d)=W_1\cup W_2 \cdots \cup W_b$ and $\A\subseteq \mc{I}^{(r)}(G)$ be an intersecting family. We may suppose that every set in $A$ meets $V_1$. Let $x\in V_1$ and $\F_x=\{A\in \mc{I}^{(r)}(G):x\in A\}$. We will show that $$|\A|\leq |\F_x|=\binom{b+d-1}{r-1}+(c-1)\left(\binom{b+d-1}{r-1}-\binom{b-1}{r-1}\right).$$ W may assume that $\A$ is down-compressed and so if $A,B\in \A$ then $A\cap B \cap (V_1\cup W_1) \neq \emptyset$. Partition $\A$ as $\A=\B\cup\C\cup\D$, where 
\begin{eqnarray*}
\B & = & \{A\in\A:A\subseteq V_1\},\\
\C & = & \{A\in\A:\exists B\in \A\tr{ such that }A\cap B\cap V_1=\emptyset\},\\
\D & = & \{A\in\A:A\subseteq V_1\cup W_1\tr{ and }A\not\in\B\cup\C\},\\
\E & = & \A\b(\B\cup\C\cup\D).
\end{eqnarray*}
Now since $\A$ is down-compressed we know that every set in $\C$ is contained in $V_1\cup W_1$. Then by the Erd\H os-Ko-Rado theorem we have $|\B|+|\C|+|\D|\leq \binom{b+d-1}{r-1}$.
The family $\F=\{A\cap V_1:A\in\E\}$ is an intersecting family in $V_1^{(<r)}$ and clearly \begin{equation}\label{first}|\E|\leq (c-1)\sum_{A\in\F}\binom{d}{r-|A|}.\end{equation}

We now wish to show that for any intersecting family $\mc{H}\subseteq V_1^{(<r)}$ we have 
\begin{equation}\label{last}\sum_{H\in\mc{H}}\binom{d}{r-|H|}\leq \sum_{x\in A\in V_1^{(<r)}}\binom{d}{r-|A|}=\binom{b+d-1}{r-1}-\binom{b-1}{r-1}.\end{equation}
Let $h_i=|\{H\in\mc{H}:|H|=i\}|$. Then inequality (\ref{last}) follows by noting that since $\mc{H}$ is intersecting, if $1\leq i \leq \lfloor b/2\rfloor$ then the Erd\H os-Ko-Rado theorem implies $h_i\leq \binom{b-1}{i-1}$ and moreover $h_i+h_{b-i}\leq \binom{b}{i}$. So by rearranging we have for any $1\leq i\leq \lfloor b/2 \rfloor$ 
\[
\sum_{H\in\mc{H},|H|\in\{i,b-i\}}\binom{d}{r-|H|}\leq  \sum_{x\in A \subset V_1, |A|\in \{i,b-i\}}\binom{d}{r-|A|}.\] The result then follows since the last inequality implies that 
$$|\E|\leq (c-1) \sum_{x\in A \in V_1^{(<r)}}\binom{d}{r-|A|}=(c-1)\left(\binom{b+d-1}{r-1}-\binom{b-1}{r-1}\right).$$

We will now show that $G$ is strictly $r$-EKR for $b+d> 2r$. First note that for $|\A|=|\F_x|$ equality must hold in every inequality given above. Then by the Erd\H os-Ko-Rado theorem $\B\cup\C\cup\D$ is centred on a point $y\in V_1\cup W_1$. If $ y\in W_1$ then, since $\A$ is down-compressed, we know that every set in $\A$ must contain a copy of $y$ from $\bigcup_{j=1}^c W_j$. Then since equality must hold in (\ref{first}) we must have $d=1$, but we know $d\geq 2$. So we can suppose that $y\in V_1$. 


If $d\geq r-1$ then $\B\cup \C \cup \D$ contains a set $A$ such that $A\cap V_1=\{y\}$. Then by definition of $\E$ we must have $y\in E$ for every $E\in \E$ so we can suppose $d\leq r-2$ and so $b>r$.

Let $\F=\{A\cap V_1:A\in\E\}$ and for $1\leq i \leq r$ let $\F^i=\{F\in \F:|F|=i\}$. Let $r-d\leq i\leq\lfloor b/2\rfloor$ then for equality to hold we must have $|\F^i|=\binom{b-1}{i-1}$ and there exists $v_i\in V_1$ such that $\F^i$ is centred on $v_i$. If $r-d\leq i,j\leq \lfloor b/2\rfloor$ then since $i+j\leq b$ we must have $v_i=v_j$ since otherwise there are $A\in \F^i$ and $B\in \F^j$ such that $A\cap B=\emptyset$. So we can suppose that $\bigcup_{i=r-d}^{\lfloor b/2 \rfloor} \F^i$ is centred on some vertex $v\in V_1$. Then clearly for $r-d \leq i \leq \lfloor b/2 \rfloor$ the family $\F^{b-i}$ is also centred on $v$. Hence every set in $\E$ contains $v$. If $v=y$ then we are done so suppose $v\neq y$. Let $A\in \E$ such that $|A\cap V_1|=r-d$ and $y\not\in A$. Then since $r-d+r\leq b$ there is $B\in \B$ such that $A\cap B \cap V_1= \emptyset$ a contradiction.$\hfill \Box$



math0307072.extracted_bib
\begin{thebibliography}{}
\bibitem{BL} B. Bollob\'as and I. Leader, An Erd\H os-Ko-Rado
theorem for signed sets, \emph{Computers Math. Applic.}
\textbf{34} (11) (1997), 9-13.
\bibitem{EKR} P. Erd\H os, C. Ko and R. Rado, Intersection theorems for systems of finite sets, \emph{Quart. J. Math. Oxford (2)} \textbf{12} (1961), 313-320.
\bibitem{HJ} F.C. Holroyd, `Problem 338 (BCC16.25), Erd\H os-Ko-Rado at the court of King Arthur', \emph{Discrete Mathematics} 197/198 (1999), 812.
\bibitem{JT} J. Talbot, Intersecting families of separated sets, \emph{J. London Math. Soc.} (to appear)
\end{thebibliography}