Homework for Combinatorics 1
This is a homework from my Introductory course in Combinatorics at Rutgers. Some of the problems do not require any sophisticated tools, just an open mind. Enjoy !!
(1) Deduce Erdos-Ko-Rado theorem from Katona-Kruskal theorem.
(2) Prove that if and are two upsets, then . (Recall that a upset is a collection of subsets of the group set such that if
then $B \in F$ for any $A \subset B$.)
(3) Prove that in the random graph (having vertices and edge probability ), .
(4) Prove the 2-part Sperner theorem. If is partitioned into two non-empty sets and and is a family such that for any in , is not in or in , then .
(5) Prove that .
(6) Let be a upset. Prove that the average size of an element of is at least .