Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • [1] 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, https://doi.org/10.1006/aama.1998.0588
  • [2] Noga Alon, Amir Shpilka, and Christopher Umans, On sunflowers and matrix multiplication, Comput. Complexity 22 (2013), no. 2, 219-243. MR 3055780, https://doi.org/10.1007/s00037-013-0060-1
  • [3] Béla Bollobás and Imre Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991), no. 1, 47-62. MR 1082842, https://doi.org/10.1016/0097-3165(91)90021-8
  • [4] 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, https://doi.org/10.1016/0097-3165(95)90021-7
  • [5] 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, https://doi.org/10.1098/rsta.1998.0184
  • [6] 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
  • [7] 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 0057518
  • [8] 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 0439648
  • [9] 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
  • [10] David Ellis, Forbidding just one intersection, for permutations, J. Combin. Theory Ser. A 126 (2014), 136-165. MR 3213310, https://doi.org/10.1016/j.jcta.2014.04.011
  • [11] Jacob Fox and Benny Sudakov, Dependent random choice, Random Structures Algorithms 38 (2011), no. 1-2, 68-99. MR 2768884, https://doi.org/10.1002/rsa.20344
  • [12] P. Frankl, Orthogonal vectors in the $ n$-dimensional cube and codes with missing distances, Combinatorica 6 (1986), no. 3, 279-285. MR 875296, https://doi.org/10.1007/BF02579389
  • [13] 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, https://doi.org/10.1016/0097-3165(84)90008-6
  • [14] Peter Frankl and Vojtěch Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), no. 1, 259-286. MR 871675, https://doi.org/10.2307/2000598
  • [15] 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, https://doi.org/10.1090/S0894-0347-1990-1020148-2
  • [16] P. Frankl and R. M. Wilson, Intersection theorems with geometric consequences, Combinatorica 1 (1981), no. 4, 357-368. MR 647986, https://doi.org/10.1007/BF02579457
  • [17] Gy. Katona, Intersection theorems for systems of finite sets, Acta Math. Acad. Sci. Hungar 15 (1964), 329-337. MR 0168468
  • [18] 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, https://doi.org/10.1016/S0166-218X(99)00082-7
  • [19] Dhruv Mubayi and Vojtech Rödl, Specified intersections, Trans. Amer. Math. Soc. 366 (2014), no. 1, 491-504. MR 3118403, https://doi.org/10.1090/S0002-9947-2013-05877-1
  • [20] Jiří Sgall, Bounds on pairs of families with restricted intersections, Combinatorica 19 (1999), no. 4, 555-566. MR 1773657, https://doi.org/10.1007/s004939970007

Similar Articles

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
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
Email: Eoin.Long@maths.ox.ac.uk, eoinlong@post.tau.ac.il

DOI: https://doi.org/10.1090/tran/7015
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

American Mathematical Society