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 X, and answered the question for |X| \geq r, the size of the sets in the set family. This paper answers the question for |X| < r, provided n, 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, \mathcal F(2, n, G)(X) has size polynomial in n …” should read “By Lemma 9, \mathcal F( r, n, G)( X) …”. Thanks to Candida Bowtell for spotting this.

Leave a Reply

Your email address will not be published.