Journal article icon

Journal article

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

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.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


Files:
Publisher copy:
10.1090/tran/7015

Authors


More by this author
Department:
Mansfield College
More by this author
Department:
Oxford, MPLS, Mathematical Institute
Publisher:
American Mathematical Society Publisher's website
Journal:
Transactions of the American Mathematical Society Journal website
Volume:
369
Issue:
2
Pages:
1147-1162
Publication date:
2016-10-05
Acceptance date:
2016-06-16
DOI:
ISSN:
0002-9947
Pubs id:
pubs:453016
URN:
uri:7fd3369d-d863-4cd8-ac29-e12083c1c595
UUID:
uuid:7fd3369d-d863-4cd8-ac29-e12083c1c595
Local pid:
pubs:453016

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP