Intersection Theorems for Finite Sets

by Prof. Dhruv Mubayi (University of Illinois, USA,)

Monday, August 11, 2014 from 16:00 to 17:00 (Asia/Kolkata)
at Colaba Campus ( AG-66 )

Description

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.