Frankl-Rödl-type theorems for codes and permutations
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...
| Main Authors: | , |
|---|---|
| Format: | Journal article |
| Published: |
American Mathematical Society
2016
|
| _version_ | 1797078376800845824 |
|---|---|
| author | Keevash, P Long, E |
| author_facet | Keevash, P Long, E |
| author_sort | Keevash, P |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-03-07T00:31:05Z |
| format | Journal article |
| id | oxford-uuid:7fd3369d-d863-4cd8-ac29-e12083c1c595 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:31:05Z |
| publishDate | 2016 |
| publisher | American Mathematical Society |
| record_format | dspace |
| spelling | oxford-uuid:7fd3369d-d863-4cd8-ac29-e12083c1c5952022-03-26T21:19:19ZFrankl-Rödl-type theorems for codes and permutationsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:7fd3369d-d863-4cd8-ac29-e12083c1c595Symplectic Elements at OxfordAmerican Mathematical Society2016Keevash, PLong, EWe 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. |
| spellingShingle | Keevash, P Long, E Frankl-Rödl-type theorems for codes and permutations |
| title | Frankl-Rödl-type theorems for codes and permutations |
| title_full | Frankl-Rödl-type theorems for codes and permutations |
| title_fullStr | Frankl-Rödl-type theorems for codes and permutations |
| title_full_unstemmed | Frankl-Rödl-type theorems for codes and permutations |
| title_short | Frankl-Rödl-type theorems for codes and permutations |
| title_sort | frankl rodl type theorems for codes and permutations |
| work_keys_str_mv | AT keevashp franklrodltypetheoremsforcodesandpermutations AT longe franklrodltypetheoremsforcodesandpermutations |