Erdős-Ko-Rado Theorems for a Family of Trees

Abstract

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 and $v$ is the centre of the star. Then $G$ is said to be $r$-EKR if no pairwise intersecting subfamily of ${\mathcal{I}}^{(r)}(G)$ is bigger than the largest $r$-star, and if every maximum size pairwise intersecting subfamily of ${\mathcal{I}}^{(r)}(G)$ is an $r$-star, then $G$ is said to be strictly $r$-EKR. Let $\hat{I}¼(G)$ denote the minimum size of a maximal independent set of $G$. Holroyd and Talbot conjectured that if $2r\le \hat{I}¼(G)$, then $G$ is $r$-EKR and strictly $r$-EKR if $2r<\hat{I}¼(G)$. An elongated claw is a tree in which one vertex is designated the root and no vertex other than the root has degree greater than 2. A depth-two claw is an elongated claw in which every vertex of degree~1 is at distance 2 from the root. We show that if $G$ is a depth-two claw, then $G$ is strictly $r$-EKR if $2r\le \hat{I}¼(G)+1$, confirming the conjecture of Holroyd and Talbot for this family. We also show that if $G$ is an elongated claw with $n$ leaves and at least one leaf adjacent to the root, then $G$ is $r$-EKR if $2r\le n$. Hurlbert and Kamat had conjectured that one can always find a largest $r$-star of a tree whose centre is a leaf. Baber and Borg have separately shown this to be false. We show that, moreover, for all $n\ge 2$, $d\ge 3$, there exists a positive integer $r$ such that there is a tree where the centre of the largest $r$-star is a vertex of degree $n$ at distance at least $d$ from every leaf.

Added new section on "Centres of Largest $r$-stars in Trees"