Title: Intersecting Families
Speaker: Arran Hamm, Rutgers University
Date: Wednesday, March 7, 2012 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Intersecting Families A classic set system question is, how many k-subsets of [n] can you have such that every pair of sets is intersecting (i.e. an intersecting family)? This, of course, was answered by the Erd\"{o}s-Ko-Rado Theorem stating that the maximum is {n-1\choose k-1}. One construction of a maximum sized intersecting family is to take all k-sets containing a particular element of [n]. Observe that for this type of family the intersection over all members of the family is nonempty. So naturally one can ask, how large of an intersecting family of k-subsets of [n] can you have such that the intersection over all members of the family is empty? This was answered by the Hilton-Milner Theorem whose statement and proof will be given. The remainder of the talk will be on a threshold-type question about random k-uniform hypergraphs with respect to the "EKR Property".