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
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.
- © Copyright 2016 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 1147-1162
- MSC (2010): Primary 05D05; Secondary 05D40, 94B65
- DOI: https://doi.org/10.1090/tran/7015
- MathSciNet review: 3572268