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

Keevash, Peter; Long, Eoin

doi:10.1090/tran/7015

Frankl-Rödl-type theorems for codes and permutations
HTML articles powered by AMS MathViewer

by Peter Keevash and Eoin Long PDF

Trans. Amer. Math. Soc. 369 (2017), 1147-1162 Request permission

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

Rudolf Ahlswede and Levon H. Khachatrian, The diametric theorem in Hamming spaces—optimal anticodes, Adv. in Appl. Math. 20 (1998), no. 4, 429–449. MR 1612850, DOI 10.1006/aama.1998.0588
Noga Alon, Amir Shpilka, and Christopher Umans, On sunflowers and matrix multiplication, Comput. Complexity 22 (2013), no. 2, 219–243. MR 3055780, DOI 10.1007/s00037-013-0060-1
Béla Bollobás and Imre Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991), no. 1, 47–62. MR 1082842, DOI 10.1016/0097-3165(91)90021-8
László Babai, Hunter Snevily, and Richard M. Wilson, A new proof of several inequalities on codes and sets, J. Combin. Theory Ser. A 71 (1995), no. 1, 146–153. MR 1335782, DOI 10.1016/0097-3165(95)90021-7
R. C. Baker and G. Harman, The three primes theorem with almost equal summands, R. Soc. Lond. Philos. Trans. Ser. A Math. Phys. Eng. Sci. 356 (1998), no. 1738, 763–780. MR 1620832, DOI 10.1098/rsta.1998.0184
Harry Buhrman, Richard Cleve, and Avi Wigderson, Quantum vs. classical communication and computation, STOC ’98 (Dallas, TX), ACM, New York, 1999, pp. 63–68. MR 1731563
Herman Chernoff, A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations, Ann. Math. Statistics 23 (1952), 493–507. MR 57518, DOI 10.1214/aoms/1177729330
Péter Frankl and Mikhail Deza, On the maximum number of permutations with given maximal or minimal distance, J. Combinatorial Theory Ser. A 22 (1977), no. 3, 352–360. MR 439648
P. Erdős, Problems and results in graph theory and combinatorial analysis, Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) Congressus Numerantium, No. XV, Utilitas Math., Winnipeg, Man., 1976, pp. 169–192. MR 0409246
David Ellis, Forbidding just one intersection, for permutations, J. Combin. Theory Ser. A 126 (2014), 136–165. MR 3213310, DOI 10.1016/j.jcta.2014.04.011
Jacob Fox and Benny Sudakov, Dependent random choice, Random Structures Algorithms 38 (2011), no. 1-2, 68–99. MR 2768884, DOI 10.1002/rsa.20344
P. Frankl, Orthogonal vectors in the $n$-dimensional cube and codes with missing distances, Combinatorica 6 (1986), no. 3, 279–285. MR 875296, DOI 10.1007/BF02579389
P. Frankl and Z. Füredi, On hypergraphs without two edges intersecting in a given number of vertices, J. Combin. Theory Ser. A 36 (1984), no. 2, 230–236. MR 734980, DOI 10.1016/0097-3165(84)90008-6
Peter Frankl and Vojtěch Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259–286. MR 871675, DOI 10.1090/S0002-9947-1987-0871675-6
P. Frankl and V. Rödl, A partition property of simplices in Euclidean space, J. Amer. Math. Soc. 3 (1990), no. 1, 1–7. MR 1020148, DOI 10.1090/S0894-0347-1990-1020148-2
P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357–368. MR 647986, DOI 10.1007/BF02579457
Gy. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964), 329–337. MR 168468, DOI 10.1007/BF01897141
L. H. Harper, On an isoperimetric problem for Hamming graphs, Proceedings of the Conference on Optimal Discrete Structures and Algorithms—ODSA ’97 (Rostock), 1999, pp. 285–309. MR 1708844, DOI 10.1016/S0166-218X(99)00082-7
Dhruv Mubayi and Vojtech Rödl, Specified intersections, Trans. Amer. Math. Soc. 366 (2014), no. 1, 491–504. MR 3118403, DOI 10.1090/S0002-9947-2013-05877-1
Jiří Sgall, Bounds on pairs of families with restricted intersections, Combinatorica 19 (1999), no. 4, 555–566. MR 1773657, DOI 10.1007/s004939970007