Combinatorics Seminar

When: Sunday, November 2, 10am
Where: Schreiber 309
Speaker: Eoin Long, Tel Aviv University
Title: Frankl-Rödl type theorems for codes and permutations


How large can a family F of subsets of [n] be if the intersection of every two sets A,B in F has cardinality different from t? The Frankl-Rödl theorem shows that if t is between \epsilon n and (1/2-\epsilon)n, then |F|<(2-\delta)^n, where \delta=\delta(\epsilon )>0.

In this talk I will describe a new proof of this theorem. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rödl. One consequence of this result is a Frankl-Rödl type theorem for permutations with a forbidden distance.

Joint work with Peter Keevash.