Dec. 16, 3:30pm, Wean 8220

Dhruv Mubayi, University of Illinois at Chicago

Intersection Theorems for Finite Sets

Dhruv Mubayi, University of Illinois at Chicago

Intersection Theorems for Finite Sets

Abstract:

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 Rödl, who solved a 250-dollar problem of Erdős 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. This is joint work with Vojtěch Rödl.