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

DOI10.1090/TRAN/7015MaRDI QIDQ2833012zbMATH OpenOpenAlexFDO

Authors Peter Keevash, Eoin Long

Publication date 16 November 2016

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.6294

zbMATH Keywords

forbidden intersectionscodes with forbidden distancesprobabilistic method of dependent random choice

Mathematics Subject Classification ID

Bounds on codes (94B65) Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We give a new proof of the Frankl-R"odl 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"odl. 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.

Recommendations

• Forbidden Intersections
• Improvement of the Frankl-Rödl theorem on the number of edges in hypergraphs with forbidden cardinalities of edge intersections
• Improvements of the Frankl-Rödl theorem and geometric consequences
• A new proof of several inequalities on codes and sets
• Approximation by juntas in the symmetric group, and forbidden intersection problems

Cites work

• scientific article; zbMATH DE number 3523543 (Why is no real title available?)
• scientific article; zbMATH DE number 1775389 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A Partition Property of Simplices in Euclidean Space
• A new proof of several inequalities on codes and sets
• Bounds on pairs of families with restricted intersections
• Compressions and isoperimetric inequalities
• Dependent random choice
• Forbidden Intersections
• Forbidding just one intersection, for permutations
• Intersection theorems for systems of finite sets
• Intersection theorems with geometric consequences
• On an isoperimetric problem for Hamming graphs
• On hypergraphs without two edges intersecting in a given number of vertices
• On sunflowers and matrix multiplication
• On the maximum number of permutations with given maximal or minimal distance
• Orthogonal vectors in the \(n\)-dimensional cube and codes with missing distances
• Specified intersections
• The diametric theorem in Hamming spaces---optimal anticodes
• The three primes theorem with almost equal summands

Cited in

(14)

• Unavoidable hypergraphs
• Forbidden intersections for codes
• Fractional \(L\)-intersecting families
• On a Frankl-Wilson theorem
• Bisecting and \(D\)-secting families for set systems
• System of unbiased representatives for a collection of bicolorings
• Forbidding intersection patterns between layers of the cube
• On a Frankl-Wilson theorem and its geometric corollaries
• Spread approximations for forbidden intersections problems
• The junta method for hypergraphs and the Erdős-Chvátal simplex conjecture
• Invitation to intersection problems for finite sets
• On the partition of an odd number into three primes in a prescribed proportion
• Turán numbers of sunflowers
• Approximation by juntas in the symmetric group, and forbidden intersection problems

This page was built for publication: Frankl-Rödl-type theorems for codes and permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2833012)