Combinatorics Seminar

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.

w3c valid   accessible website
redesigned by barak soreq