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
Abstract:
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.