Frankl-Rödl-type theorems for codes and permutations

Research output: Contribution to journalArticlepeer-review

Authors

Colleges, School and Institutes

External organisations

  • University of Oxford

Abstract

We give a new proof of the Frankl-Rödl theorem on forbidden intersections, via the probabilistic method of dependent random choice. 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. We
also apply our bound to a question of Ellis on sets of permutations with forbidden distances and to establish a weak form of a conjecture of Alon, Shpilka
and Umans on sunflowers.

Details

Original languageEnglish
Pages (from-to)1147-1162
Number of pages16
JournalTransactions of the American Mathematical Society
Volume369
Issue number2
Early online date7 Oct 2016
Publication statusPublished - 1 Feb 2017

Keywords

  • Frankl-Rödl theorem, forbidden intersections, extremal set theory