Erdos-Ko-Rado and Kruskal-Katona Theorem for Discrete Structures

Abstract

The project we have undertaken concerns extremal combinatorics. Two core concepts in extremal set theory are intersecting families and shadows. A family of subsets of a given set X whose members have size k and pair wise intersect is called an intersecting family. The main results for intersecting families are the Erdos-Ko-Rado and Hilton-Milner theorems, which give an upper bound on the maximum size of intersecting families. Shadow is a property of a family of k-element subsets of a set X. It consists of all (k-1) element subsets of the set X contained in at least one member of the family. The principal result for shadows is the Kruskal-Katona theorem, which gives a lower bound on the size of a shadow. This thesis aims to further understand analogs of Erdos-Ko-Rado, Hilton-Milner and Kruskal-Katona Theorems for other discrete structures such as vector spaces and multisets.