EKR sets for large n and r

الأصل · EN

Let ⊂[n]r be a compressed, intersecting family and let X⊂[n]. Let (X)=A∈:A∩ X≠ and §ₙ,ᵣ=[n]r(1). Motivated by the Erdős-Ko-Rado theorem, Borg asked for which X⊂[2,n] do we have |(X)|≤|§ₙ,ᵣ(X)| for all compressed, intersecting families? We call X that satisfy this property EKR. Borg classified EKR sets X such that |X|≥ r. Barber classified X, with |X|≤ 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 has a maximal element, we are able to sharpen this bound to n>φ²r implies |(X)|≤|§ₙ,ᵣ(X)|. We conclude by giving a generating function that speeds up computation of |(X)| in comparison with the naïve methods.