Computer Science/Discrete Mathematics Seminar I

Four and a half proofs of a product-measure version of the Erdös-Ko-Rado Theorem.

The EKR theorem, which is the cornerstone of extremal combinatorics, characterizes maximal intersecting families of sets. Its setting fixes a ground set of size n, and then studies the size and structure of intersecting families of subsets of fixed size k. A setting which many might consider no less natural, is considering the Boolean lattice of all subsets of {1,...,n} endowed with a product measure, and studying the structure and measure of maximal intersecting families.

In this talk we´ll see the simple theorem which is the natural product-measure analog of the EKR theorem, and the tip of an iceberg, and study a plethora of proofs which hopefully illuminate various aspects of it.

Date & Time

September 24, 2018 | 2:00pm – 3:00pm

Location

Simonyi Hall 101

Affiliation

The Weizmann Institute of Science