Maximum hitting for n sufficiently large

Barber, B. Graphs and Combinatorics (2014) 30: 267. PDF

Borg asked what happens to the Erdős-Ko-Rado theorem if we only count sets meeting some fixed set , and answered the question for , the size of the sets in the set family. This paper answers the question for , provided , the size of the ground set, is sufficiently large.

There is a typo in the proof of Theorem 4 in the journal version. The line beginning "By Lemma 9, has size polynomial in ..." should read "By Lemma 9, ...". Thanks to Candida Bowtell for spotting this.

Leave a Reply

Your email address will not be published.