Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 

 

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


Authors: Peter Keevash and Eoin Long
Journal: Trans. Amer. Math. Soc. 369 (2017), 1147-1162
MSC (2010): Primary 05D05; Secondary 05D40, 94B65
DOI: https://doi.org/10.1090/tran/7015
Published electronically: October 7, 2016
MathSciNet review: 3572268
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05D05, 05D40, 94B65

Retrieve articles in all journals with MSC (2010): 05D05, 05D40, 94B65


Additional Information

Peter Keevash
Affiliation: Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom
Email: Peter.Keevash@maths.ox.ac.uk

Eoin Long
Affiliation: Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom
Address at time of publication: School of Mathematical Sciences, Tel Aviv University, 69978 Tel Aviv, Israel
Email: Eoin.Long@maths.ox.ac.uk, eoinlong@post.tau.ac.il

DOI: https://doi.org/10.1090/tran/7015
Received by editor(s): February 25, 2014
Received by editor(s) in revised form: February 12, 2015
Published electronically: October 7, 2016
Additional Notes: This research was supported in part by ERC grant 239696 and EPSRC grant EP/G056730/1.
Article copyright: © Copyright 2016 American Mathematical Society