The Erdős-Ko-Rado property of trees of depth two

Abstract

A family of sets is intersecting if any two sets in the family intersect. Given a graph $G$ and an integer $r\ge 1$, let ${\mathcal{I}}^{(r)}(G)$ denote the family of independent sets of size $r$ of $G$. For a vertex $v$ of $G$, let ${\mathcal{I}}_v^{(r)}(G)$ denote the family of independent sets of size $r$ that contain $v$. This family is called an $r$-star. Then $G$ is said to be $r$-EKR if no intersecting subfamily of ${\mathcal{I}}^{(r)}(G)$ is bigger than the largest $r$-star. Let $k,n,r\ge 1$, and let $T(n,k)$ be the tree of depth two in which the root has degree $n$ and every neighbour of the root has the same number $k+1$ of neighbours. For each $k\ge 2$, we show that $T(n,k)$ is $r$-EKR if $2r\le n$, extending results of Borg and of Feghali, Johnson and Thomas who considered the case $k=1$.

As kindly pointed out to me by Hurlbert, the proof of Claim 2 has a serious error. As a result, the article has been withdrawn