8.4 Exercises

Let $ℱ$ be an anti-chain consisting of sets of cardinality at most $k\le n/2$. Show that $|ℱ|\le \left(\genfrac{}{}{0pt}{}{n}{k}\right)$.

Let $A_i,1\le i\le k$ be distinct subsets of $[n]$ such that $A_i\cap A_j\ne \mathrm{\varnothing }$ for all $i,j$. Show that $k\le 2^{n-1}$ and give an example where equality holds.