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.

A note on balanced independent sets in the cube

Australas. J. Combin. 52 (2012), 205–207. PDF

How large can an independent set in the discrete cube be if it contains equal numbers of sets of even and odd size? Take odd sets starting from the bottom of the cube, and even sets starting from the top. Proving that this works uses an isoperimetric inequality: if you know the proof of Harper’s theorem that uses codimension 1 compressions then you know how to prove the inequality that’s quoted without proof in this paper.