Combinatorics: Ehud Fridgut (Weizmann Institute) "Almost-intersecting families are almost intersecting-families."

Speaker: Ehud Fridgut (Weizmann Institute)
Title: Almost-intersecting families are almost intersecting-families.
Abstract: Consider a family of subsets of size k from a ground set of size n (with k < n/2). Assume most (in some well defined sense) pairs of sets in the family intersect. Is it then possible to remove few (in some well defined sense) sets, and remain with a family where every two sets intersect?
We will answer this affirmatively, and the route to the answer will pass through a removal lemma in product graphs.
There are some non-elementary techniques hidden in the background, but during this presentation we will mostly use them as black boxes, focusing on the proof of the removal lemma.
Joint work with Oded Regev.

Date: 

Sun, 18/06/2017 - 11:00 to 13:00

Location: 

Rothberg B221 (CS building)