EKR sets for large $n$ and $r$

Abstract

Let $\A\subset\binom{[n]}{r}$ be a compressed, intersecting family and let $X\subset [n]$. Let $\A(X)={A\in\A:A\cap X\ne\emptyset}$ and ${\S }_{n,r}=\left(\genfrac{}{}{0ex}{}{[n]}{r}\right)(1)$. Motivated by the Erdős-Ko-Rado theorem, Borg asked for which $X\subset [2,n]$ do we have $|\A(X)|\le|§_{n,r}(X)|$ for all compressed, intersecting families $\A$? We call $X$ that satisfy this property EKR. Borg classified EKR sets $X$ such that $|X|\ge r$. Barber classified $X$, with $|X|\le r$, such that $X$ is EKR for sufficiently large $n$, and asked how large $n$ must be. We prove $n$ is sufficiently large when $n$ grows quadratically in $r$. In the case where $\A$ has a maximal element, we are able to sharpen this bound to $n>{\phi }^{2}r$ implies $|\A(X)|\le|§_{n,r}(X)|$. We conclude by giving a generating function that speeds up computation of $|\A(X)|$ in comparison with the naïve methods.