by
Prof.Dhruv Mubayi(University of Illinois, USA,)
→
Asia/Kolkata
AG-66 (Colaba Campus)
AG-66
Colaba Campus
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.