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

DOI10.1090/TRAN/7015zbMATH Open1350.05170arXiv1402.6294OpenAlexW2964212244MaRDI QIDQ2833012FDOQ2833012

Authors: Peter Keevash, Eoin Long 

Publication date: 16 November 2016

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

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.

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

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

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)

Cites Work

• Forbidden Intersections
• Title not available (Why is that?)
• Intersection theorems with geometric consequences
• On the maximum number of permutations with given maximal or minimal distance
• The diametric theorem in Hamming spaces---optimal anticodes
• Intersection theorems for systems of finite sets
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Compressions and isoperimetric inequalities
• On hypergraphs without two edges intersecting in a given number of vertices
• Dependent random choice
• On sunflowers and matrix multiplication
• Orthogonal vectors in the \(n\)-dimensional cube and codes with missing distances
• A new proof of several inequalities on codes and sets
• A Partition Property of Simplices in Euclidean Space
• Title not available (Why is that?)
• On an isoperimetric problem for Hamming graphs
• Forbidding just one intersection, for permutations
• Specified intersections
• Bounds on pairs of families with restricted intersections
• 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)