Dhruv Mubayi
University of Illinois, USA
August 11, 2014
Intersection Theorems for Finite Sets: Finite extremal set theory is concerned with the following general problem: Suppose we have a collection $F$ of subsets of an $n$-element set and we have some restriction on the possible intersection sizes of pairs of sets in $F$. What is the maximum number of subsets that $F$ can contain? Surprisingly, solutions to various special cases of this problem have deep implications in many other areas, including coding theory, geometry, and computer science. A particular famous example is due to Frankl and Rodl, who solved a 250-dollar problem of Erdos by proving that if $n$ is a multiple of 4 and $n/4$ is excluded as an intersection size, then $|F|<(1.99)^n$. We extend this result by showing that if some additional (rather mild) restrictions are placed on the possible intersection sizes, then $|F|<(1.63)^n$. The talk is intended for a general mathematical audience. This is joint work with Vojtech Rodl.
University of Illinois, USA
August 11, 2014
Intersection Theorems for Finite Sets: Finite extremal set theory is concerned with the following general problem: Suppose we have a collection $F$ of subsets of an $n$-element set and we have some restriction on the possible intersection sizes of pairs of sets in $F$. What is the maximum number of subsets that $F$ can contain? Surprisingly, solutions to various special cases of this problem have deep implications in many other areas, including coding theory, geometry, and computer science. A particular famous example is due to Frankl and Rodl, who solved a 250-dollar problem of Erdos by proving that if $n$ is a multiple of 4 and $n/4$ is excluded as an intersection size, then $|F|<(1.99)^n$. We extend this result by showing that if some additional (rather mild) restrictions are placed on the possible intersection sizes, then $|F|<(1.63)^n$. The talk is intended for a general mathematical audience. This is joint work with Vojtech Rodl.