When: Sunday, June 11, 10am
Where: Schreiber 309
Speaker: Ehud Friedgut, Weizmann Institute
Title: Almost-intersecting families are almost intersecting-families
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.
