Frankl-Rödl-type theorems for codes and permutations
Authors:
Peter Keevash and Eoin Long
Journal:
Trans. Amer. Math. Soc. 369 (2017), 1147-1162
MSC (2010):
Primary 05D05; Secondary 05D40, 94B65.
DOI:
https://doi.org/10.1090/tran/7015
Published electronically:
October 7, 2016
MathSciNet review:
3572268
Full-text PDF
Abstract | References | Similar Articles | Additional Information
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.
- 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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0097-3165%2891%2990021-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 https://doi.org/10.1016/0097-3165%2895%2990021-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 https://doi.org/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 https://doi.org/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) Utilitas Math., Winnipeg, Man., 1976, pp. 169–192. Congressus Numerantium, No. XV. MR 0409246
- David Ellis, Forbidding just one intersection, for permutations, J. Combin. Theory Ser. A 126 (2014), 136–165. MR 3213310, DOI https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1016/0097-3165%2884%2990008-6
- Peter Frankl and Vojtěch Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259–286. MR 871675, DOI https://doi.org/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 https://doi.org/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 https://doi.org/10.1007/BF02579457
- Gy. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar. 15 (1964), 329–337. MR 168468, DOI https://doi.org/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 https://doi.org/10.1016/S0166-218X%2899%2900082-7
- Dhruv Mubayi and Vojtech Rödl, Specified intersections, Trans. Amer. Math. Soc. 366 (2014), no. 1, 491–504. MR 3118403, DOI https://doi.org/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 https://doi.org/10.1007/s004939970007
Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 05D05, 05D40, 94B65.
Retrieve articles in all journals with MSC (2010): 05D05, 05D40, 94B65.
Additional Information
Peter Keevash
Affiliation:
Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom
MR Author ID:
670477
Email:
Peter.Keevash@maths.ox.ac.uk
Eoin Long
Affiliation:
Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom
Address at time of publication:
School of Mathematical Sciences, Tel Aviv University, 69978 Tel Aviv, Israel
MR Author ID:
1040049
Email:
Eoin.Long@maths.ox.ac.uk, eoinlong@post.tau.ac.il
Received by editor(s):
February 25, 2014
Received by editor(s) in revised form:
February 12, 2015
Published electronically:
October 7, 2016
Additional Notes:
This research was supported in part by ERC grant 239696 and EPSRC grant EP/G056730/1.
Article copyright:
© Copyright 2016
American Mathematical Society
