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

Peter Keevash; Eoin Long

doi:10.1090/tran/7015

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

Peter Keevash, Eoin Long

Mathematics

Research output: Contribution to journal › Article › peer-review

7 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1147-1162
Number of pages	16
Journal	Transactions of the American Mathematical Society
Volume	369
Issue number	2
Early online date	7 Oct 2016
DOIs	https://doi.org/10.1090/tran/7015
Publication status	Published - 1 Feb 2017

Keywords

Frankl-Rödl theorem
forbidden intersections
extremal set theory

Access to Document

10.1090/tran/7015Licence: None: All rights reserved

Cite this

@article{856ce091bb9f4e6587c10d4af450f9b3,

title = "Frankl-R{\"o}dl-type theorems for codes and permutations",

abstract = "We give a new proof of the Frankl-R{\"o}dl theorem on forbidden intersections, via the probabilistic method of dependent random choice. Ourmethod extends to codes with forbidden distances, where over large alphabetsour bound is significantly better than that obtained by Frankl and R{\"o}dl. Wealso 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, Shpilkaand Umans on sunflowers.",

keywords = "Frankl-R{\"o}dl theorem, forbidden intersections, extremal set theory",

author = "Peter Keevash and Eoin Long",

year = "2017",

month = feb,

day = "1",

doi = "10.1090/tran/7015",

language = "English",

volume = "369",

pages = "1147--1162",

journal = "Transactions of the American Mathematical Society",

issn = "0002-9947",

publisher = "American Mathematical Society",

number = "2",

}

TY - JOUR

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

AU - Keevash, Peter

AU - Long, Eoin

PY - 2017/2/1

Y1 - 2017/2/1

N2 - We give a new proof of the Frankl-Rödl theorem on forbidden intersections, via the probabilistic method of dependent random choice. Ourmethod extends to codes with forbidden distances, where over large alphabetsour bound is significantly better than that obtained by Frankl and Rödl. Wealso 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, Shpilkaand Umans on sunflowers.

AB - We give a new proof of the Frankl-Rödl theorem on forbidden intersections, via the probabilistic method of dependent random choice. Ourmethod extends to codes with forbidden distances, where over large alphabetsour bound is significantly better than that obtained by Frankl and Rödl. Wealso 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, Shpilkaand Umans on sunflowers.

KW - Frankl-Rödl theorem

KW - forbidden intersections

KW - extremal set theory

U2 - 10.1090/tran/7015

DO - 10.1090/tran/7015

M3 - Article

SN - 0002-9947

VL - 369

SP - 1147

EP - 1162

JO - Transactions of the American Mathematical Society

JF - Transactions of the American Mathematical Society

IS - 2

ER -

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

Abstract

Keywords

Access to Document

Fingerprint

Cite this