Skip to main content
SpringerLink
Log in

Probabilistic existence of regular combinatorial structures

  • Published:
Geometric and Functional Analysis Aims and scope Submit manuscript

Abstract

We show the existence of regular combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, t-designs, and t-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. The proof of existence is probabilistic. We show that a randomly chosen structure has the required properties with positive yet tiny probability. Our method allows also to give rather precise estimates on the number of objects of a given size and this is applied to count the number of orthogonal arrays, t-designs and regular hypergraphs. The main technical ingredient is a special local central limit theorem for suitable lattice random walks with finitely many steps.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Noga Alon and Shachar Lovett. Almost k-wise vs k-wise independent permutations, and uniformity for general group actions, (2011), ECCC TR11-049.

  2. Noga Alon and Van H. Vu. Anti-Hadamard matrices, coin weighing, threshold gates and indecomposable hypergraphs, J. Combin. Theory Ser. A 79(1) (1997), 133–160

  3. Nikhil Bansal. Constructive algorithms for discrepancy minimization. Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS ’10, IEEE Computer Society, (2010), arXiv:1002.2259, pp. 3–10.

  4. Bapat R.B.: Moore-Penrose inverse of set inclusion matrices. Linear Algebra Appl. 318(1-3), 35–44 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  5. A. Barvinok. Combinatorics and complexity of partition functions, Algorithms and Combinatorics, Springer International Publishing, (2017)

  6. Barvinok Alexander, Hartigan J.A.: Maximum entropy gaussian approximations for the number of integer points and volumes of polytopes. Advances in Applied Mathematics 45(2), 252–289 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. Barvinok Alexander, Hartigan J.: An asymptotic formula for the number of non-negative integer matrices with prescribed row and column sums. Transactions of the American Mathematical Society 364(8), 4323–4368 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  8. Alexander Barvinok and John A Hartigan. The number of graphs and a random graph with a given degree sequence. Random Structures & Algorithms, (3)42 (2013), 301–348

  9. Andriy Bondarenko, Danylo Radchenko and Maryna Viazovska. Optimal asymptotic bounds for spherical designs, Ann. of Math. (2) (2)178 (2013), 443–452.

  10. P.J. Cameron. Permutation groups. Handbook of combinatorics, Vol. 1, 2, Elsevier, (1995), pp. 611–645.

  11. Charles J. Colbourn and Jeffrey H. Dinitz (eds.), The CRC handbook of combinatorial designs, 2nd ed., Discrete Mathematics and its Applications, Chapman & Hall/CRC, (2007)

  12. E. Rodney Canfield, Zhicheng Gao, Catherine Greenhill, Brendan D. McKay, and Robert W. Robinson. Asymptotic enumeration of correlation-immune Boolean functions. Cryptogr. Commun. (1)2 (2010), 111–126

  13. E. Rodney Canfield and Brendan D. McKay. Asymptotic enumeration of dense 0-1 matrices with equal row sums and equal column sums. Electron. J. Combin. 12 (2005), Research Paper 29, 31 pp. (electronic).

  14. Warwick de Launey, Levin David A: A fourier-analytic approach to counting partial hadamard matrices. Cryptography and Communications 2(2), 307–334 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  15. Paul Erdős and László Lovász. Problems and results on 3-chromatic hypergraphs and some related questions. Infinite and Finite Sets, Coll. Math. Soc. J. Bolyai, no. 11, North-Holland, (1975) pp. 609–627.

  16. Farhi B.: An identity involving the least common multiple of binomial coefficients and its application. Amer. Math. Monthly, 116(9), 836–839 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  17. Fulton W., Harris J.: Representation theory. Graduate Texts in Mathematics, vol. 129. Springer, New York (1991)

    Google Scholar 

  18. Hilary Finucane, Ron Peled, and Yariv Yaari. A recursive construction of t-wise uniform permutations, arXiv:1111.0492.

  19. Graver J.E., Jurkat W.B.: The module structure of integral designs. J. Combinatorial Theory Ser. A, 15, 75–90 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  20. Stefan Glock, Daniela Kühn, Allan Lo and Deryk Osthus. The existence of designs via iterative absorption, arXiv preprint arXiv:1611.06827 (2016)

  21. Shoni Gilboa and Ron Peled. Chebyshev-type quadratures for doubling weights. Constructive Approximation(2016), 1–24.

  22. A.S. Hedayat, N.J.A. Sloane, and John Stufken, Orthogonal arrays: Theory and applications, Springer-Verlag, (1999)

  23. Mikhail Isaev and Brendan D McKay. Complex martingales and asymptotic enumeration, arXiv preprint arXiv:1604.08305 (2016).

  24. James G.D.: The representation theory of the symmetric groups. Lecture Notes in Mathematics, vol. 682. Springer, Berlin (1978)

    Google Scholar 

  25. Kane Daniel: Small designs for path-connected spaces and path-connected homogeneous spaces. Transactions of the American Mathematical Society 367(9), 6387–6414 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  26. Peter Keevash, The existence of designs, arXiv preprint arXiv:1401.3665 (2014).

  27. Peter Keevash. Counting designs, arXiv preprint arXiv:1504.02909 (2015).

  28. Greg Kuperberg, Shachar Lovett and Ron Peled. Probabilistic existence of rigid combinatorial structures. Proceedings of the 44th annual ACM symposium on Theory of computing, STOC, ACM, (2012) arXiv:1111.0492, pp. 1091–1106.

  29. Koller Daphne, Megiddo Nimrod: Constructing small sample spaces satisfying given constants. SIAM J. Discrete Math. 7(2), 260–274 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  30. E. Kaplan, M. Naor and O. Reingold, Derandomized constructions of k-wise (almost) independent permutations. Approximation, randomization and combinatorial optimization (C. Chekuri, K. Jansen, J. D. P. Rolim, and L. Trevisan, eds.), Lecture Notes in Computer Science, vol. 3624, Springer, (2005) pp. 354–365.

  31. Richard M. Karp and Christos H. Papadimitriou. On linear characterizations of combinatorial optimization problems. SIAM J. Comput. (4)11 (1982), 620–632

  32. Shachar Lovett and Raghu Meka. Constructive discrepancy minimization by walking on the edges, (2012) arXiv:1203.5747.

  33. Anita Liebenau and Nick Wormald. Asymptotic enumeration of graphs by degree sequence, and the degree sequence of a random graph, arXiv preprint arXiv:1702.08373 (2017)

  34. Magliveras Spyros S.: Large sets of t-designs from groups. Mathematica Slovaca 59(1), 1–20 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  35. Aaron M Montgomery. An asymptotic formula for the number of balanced incomplete block design incidence matrices, arXiv preprint arXiv:1407.4552 (2014).

  36. Robin A. Moser. A constructive proof of the Lovász local lemma. Proceedings of the 41st annual ACM symposium on Theory of computing, STOC, ACM, (2009) arXiv:0810.4812, pp. 343–350.

  37. Robin A. Moser and Gábor Tardos A constructive proof of the general Lovász local lemma. J. ACM (2)57 (2010), 11:1–11:15, arXiv:0903.0544.

  38. McKay Brendan D., Wormald Nicholas C.: Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin. 11(6), 565–580 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  39. C. Radhakrishna Rao. Some combinatorial problems of arrays and applications to design of experiments. Survey of combinatorial theory (J. N. Srivastava, ed.), North-Holland, (1973), pp. 349–359.

  40. Ray-Chaudhuri Dijen K., Wilson Richard M.: On t-designs. Osaka J. Math. 12(3), 737–744 (1975)

    MathSciNet  MATH  Google Scholar 

  41. G. de B. Robinson. On the representations of the symmetric group. American Journal of Mathematics (3)60 (1938), 745–760

  42. Schensted C.: Longest increasing and decreasing subsequences. Canadian Journal of Mathematics 13, 179–191 (1961)

    Article  MathSciNet  MATH  Google Scholar 

  43. Spencer Joel: Six standard deviations suffice. Trans. Amer. Math. Soc. 289(2), 679–706 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  44. Seymour P.D., Zaslavsky Thomas: Averaging sets: a generalization of mean values and spherical designs. Adv. in Math. 52(3), 213–240 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  45. Teirlinck Luc. Non-trivial t-designs without repeated blocks exist for all t. Discrete Math. 65(3), 301–311 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  46. Wilson Richard M.: The necessary conditions for t-designs are sufficient for something. Utilitas Math. 4, 207–215 (1973)

    MathSciNet  MATH  Google Scholar 

  47. Wilson Richard M.: diagonal form for the incidence matrices of t-subsets vs. k-subsets. European J. Combin. 11(6), 609–615 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  48. Yekhanin Sergey: Locally decodeable codes. Foundations and Trends in Theoretical Computer Science 7(1), 1–117 (2011)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California, Davis, Davis, CA, USA

    Greg Kuperberg

  2. University of California, San Diego, San Diego, CA, USA

    Shachar Lovett

  3. Tel Aviv University, Tel Aviv, Israel

    Ron Peled

Authors
  1. Greg Kuperberg
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shachar Lovett
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ron Peled
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ron Peled.

Additional information

An extended abstract [KLP12] of this paper appeared in the 44th ACM Symposium on Theory of Computing (STOC 2012).

G. Kuperberg: Supported by NSF Grant CCF-1013079. S. Lovett: Supported by an NSF CAREER award 1350481 and NSF CCF award 1614023. R. Peled: Supported by ISF Grant 1048/11 and by IRG Grant SPTRF.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kuperberg, G., Lovett, S. & Peled, R. Probabilistic existence of regular combinatorial structures. Geom. Funct. Anal. 27, 919–972 (2017). https://doi.org/10.1007/s00039-017-0416-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00039-017-0416-9

Search

Navigation