Intersecting families, cross-intersecting families, and a proof of a conjecture of Feghali, Johnson and Thomas

Abstract

A family $\mathcal{A}$ of sets is said to be intersecting if every two sets in $\mathcal{A}$ intersect. Two families $\mathcal{A}$ and $\mathcal{B}$ are said to be cross-intersecting if each set in $\mathcal{A}$ intersects each set in $\mathcal{B}$. For a positive integer $n$, let $[n]=\{1,\dots ,n\}$ and ${\mathcal{S}}_n=\{A\subseteq [n]:1\in A\}$. In this note, we extend the Erdős-Ko-Rado Theorem by showing that if $\mathcal{A}$ and $\mathcal{B}$ are non-empty cross-intersecting families of subsets of $[n]$, $\mathcal{A}$ is intersecting, and $a_0,a_1,\dots ,a_n,b_0,b_1,\dots ,b_n$ are non-negative real numbers such that $a_i+b_i\ge a_{n-i}+b_{n-i}$ and $a_{n-i}\ge b_i$ for each $i\le n/2$, then \[\sum_{A \in \mathcal{A}} a_{|A|} + \sum_{B \in \mathcal{B}} b_{|B|} \leq \sum_{A \in \mathcal{S}_n} a_{|A|} + \sum_{B \in \mathcal{S}_n} b_{|B|}.\] For a graph $G$ and an integer $r$, let ${{\mathcal{I}}_G}^{(r)}$ denote the family of $r$-element independent sets of $G$. Inspired by a problem of Holroyd and Talbot, Feghali, Johnson and Thomas conjectured that if $r<n$ and $G$ is a depth-two claw with $n$ leaves, then $G$ has a vertex $v$ such that $\{A\in {{\mathcal{I}}_G}^{(r)}:v\in A\}$ is a largest intersecting subfamily of ${{\mathcal{I}}_G}^{(r)}$. They proved this for $r\le \frac{n+1}{2}$. We use the result above to prove the full conjecture.

arXiv comment8 pages