Extremal Combinatorics I: Extremal Problems on Set Systems

The “basic notion seminar” is an initiative of David Kazhdan who joined HU math department  around 2000. People give series of lectures about basic mathematics (or not so basic at times). Usually, speakers do not talk about their own research and not even always about their field. I gave two lecture series, one about “computational complexity theory” a couple of years ago, and one about extremal combinatorics or Erdös-type combinatorics a few months ago, which later I expanded to a series of five+one talks at Yale. One talk was on  the Borsuk Conjecture,  which I will discuss separately, and five were titled: “Extremal Combinatorics: A working tool in mathematics and computer science.”  Let me try blogging about it. The first talk was devoted to extremal problems concerning systems of sets.

Paul Erdös

1. Three warm up problems

Here is how we move very quickly from very easy problems to very hard problems with a similar flavour.

Problem I: Let  N = {1,2, … , n } . What is the largest size of a family $\cal F$  of subsets of $N$ such that every two sets in $\cal F$ have non empty intersection? (Such a family is called intersecting.)