Question

Let n be a positive integer and let F = {X 5 [n]: X|2|[n] \X]} Prove that F is a maximum intersecting family.

Answer 1

We can prove it by contradiction, it follows directly from this lemma: (if there existed a family F with more than 2n−2 elements then the set F′ of all sets that are a subset of at least one element of F has at least 2n−1+2 elements and no two of its elements give all of [n] as their union). Note that the proof of the linked result is a little bit similar to what I was trying to do below.

Flawed attempt ( in fact the lemma is false, consider taking n=2k, and letting A just have the subset {1,2,…k} and letting B contain the 2n−2k+1+1 suitable subsets). Lemma: let n≥2 and let A and B be non-empty subsets of 2[n] such that if a∈A,b∈B then we have a∪b≠[n] and a∩b≠∅, then |A|+|B|≤2n−1.

Proof: We proceed by induction, the base case is n=2, cleary A and B must both be equal and only contain one singleton. So we must have |A|+|B|=2=2n−1. Inductive step: Suppose it is true for n and now let us prove it for n+1. Take A and B as in the theorem, now let A0={a|n∉a,a∈A} and

let A0={a|n∉a,a∈A} and A1={a∖{n}|n∈a,a∈A}. Define B0 and B1 analogously. Notice that A0 and B1 satisfy the conditions of the theorem, because if we have a∈A0 and b∈B1 such that a∪b=[n−1] this would force the existance of two elements in A,B such that their union is [n], we also must have a∩b≠∅. It follows that |A0|+|B1|≤2n−1−1 by the induction hypothesis. Analogously |A1|+|B0|≤2n−1−1. It follows that |A|+|B|≤2n−1. The gap is when one of the auxiliary sets is empty. To conclude notice that what you want is just the particular result of this theorem in which A=B.