Zero-one law for random distance graphs with vertices in {−1, 0, 1} n | Problems of Information Transmission Skip to main content
Springer Nature Link
Log in

Zero-one law for random distance graphs with vertices in {−1, 0, 1}n

  • Large Systems
  • Published:
Problems of Information Transmission Aims and scope Submit manuscript

Abstract

We study zero-one laws for random distance graph with vertices in {−1, 0, 1}n depending on a set of parameters. We give some conditions under which sequences of random distance graphs obey or do not obey the zero-one law.

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
¥17,985 /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 includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Glebskii, Yu.V., Kogan, D.I., Liogon’kii, M.I., and Talanov, V.A., Volume and Fraction of Satisfiability of Formulas of the Lower Predicate Calculus, Kibernetika (Kiev), 1969, no. 2, pp. 17–26.

    Google Scholar 

  2. Fagin, R., Probabilities on Finite Models, J. Symbolic Logic, 1976, vol. 41, no. 1, pp. 50–58.

    Article  MATH  MathSciNet  Google Scholar 

  3. Shelah, S. and Spencer, J.H., Zero-One Laws for Sparse Random Graphs, J. Amer. Math. Soc., 1988, vol. 1, no. 1, pp. 97–115.

    Article  MATH  MathSciNet  Google Scholar 

  4. Zhukovskii, M.E., Zero-One Laws for First-Order Formulas with a Bounded Quantifier Depth, Dokl. Ross. Akad. Nauk, 2011, vol. 436, no. 1, pp. 14–18 [Dokl. Math. (Engl. Transl.), 2011, vol. 83, no. 1, pp. 8–11].

    MathSciNet  Google Scholar 

  5. Zhukovskii, M.E., Weak Zero-One Law for Random Distance Graphs, Vestn. Ross. Univ. Druzhby Narodov, Ser. Mat. Inform. Fiz., 2010, no. 2 (1), pp. 11–25.

    Google Scholar 

  6. Zhukovskii, M.E., Weak Zero-One Laws for Random Distance Graphs, Dokl. Ross. Akad. Nauk, 2010, vol. 430, no. 3, pp. 314–317 [Dokl. Math. (Engl. Transl.), 2010, vol. 81, no. 1, pp. 51–54].

    MathSciNet  Google Scholar 

  7. Zhukovskii, M.E., The Weak Zero-One Law for Random Distance Graphs, Teor. Veroyatn. Primen., 2010, vol. 55, no. 2, pp. 344–349 [Theory Probab. Appl. (Engl. Transl.), 2010, vol. 55, no. 2, pp. 356–360].

    Article  MathSciNet  Google Scholar 

  8. Zhukovskii, M.E., On a Sequence of Random Distance Graphs Subject to the Zero-One Law, Probl. Peredachi Inf., 2011, vol. 47, no. 3, pp. 39–58 [Probl. Inf. Trans. (Engl. Transl.), 2011, vol. 47, no. 3, pp. 251–268].

    MathSciNet  Google Scholar 

  9. Raigorodskii, A.M., The Borsuk Problem and the Chromatic Numbers of Some Metric Spaces, Uspekhi Mat. Nauk, 2001, vol. 56, no. 1, pp. 107–146 [Russian Math. Surveys (Engl. Transl.), 2001, vol. 56, no. 1, pp. 103–139].

    Article  MathSciNet  Google Scholar 

  10. Raigorodskii, A.M., Lineino-algebraicheskii metod v kombinatorike (Linear-Algebraic Method in Combinatorics), Moscow: MCCME, 2007.

    Google Scholar 

  11. MacWilliams, F.J. and Sloane, N.J.A., The Theory of Error-Correcting Codes, Amsterdam: North-Holland, 1977. Translated under the title Teoriya kodov, ispravlyayushchikh oshibki, Moscow: Svyaz’, 1979.

    MATH  Google Scholar 

  12. Alon, N. and Spencer, J.H., The Probabilistic Method, New York: Wiley, 2000, 2nd ed. Translated under the title Veroyatnostnyi metod, Moscow: BINOM, 2007.

    Book  MATH  Google Scholar 

  13. Kolchin, V.F., Random Graphs, Cambridge: Cambridge Univ. Press, 1999. Translated under the title Sluchainye grafy, Moscow: Fizmatlit, 2004, 2nd ed.

    MATH  Google Scholar 

  14. Raigorodskii, A.M., Modeli sluchainykh grafov (Models of Random Graphs), Moscow: MCCME, 2011.

    Google Scholar 

  15. Bollobás, B., Random Graphs, Cambridge: Cambridge Univ. Press, 2001, 2nd ed.

    Book  MATH  Google Scholar 

  16. Janson, S., _Luczak, T., and Ruciński, A., Random Graphs, New York: Wiley, 2000.

    Book  MATH  Google Scholar 

  17. Uspensky, V.A., Vereshchagin, N.K., and Plisko, V.E., Vvodnyi kurs matematicheskoi logiki (Introductory Course on Mathematical Logic), Moscow: Moscow State Univ., 1997.

    Google Scholar 

  18. Vereshchagin, N.K. and Shen, A., Yazyki i ischisleniya (Languages and Calculi), Moscow: MCCME, 2000.

    Google Scholar 

  19. Brass, P., Moser, W., and Pach, J., Research Problems in Discrete Geometry, Berlin: Springer, 2005.

    MATH  Google Scholar 

  20. Raigorodskii, A.M., On the Chromatic Numbers of Spheres in Euclidean Spaces, Dokl. Akad. Nauk, 2010, vol. 432, no. 2, pp. 174–177 [Dokl. Math. (Engl. Transl.), 2010, vol. 81, no. 3, pp. 379–382].

    Google Scholar 

  21. Raigorodskii, A.M., On the Chromatic Numbers of Spheres in ℝn, Combinbatorica, 2012, vol. 32, no. 1, pp. 111–123.

    Article  MATH  MathSciNet  Google Scholar 

  22. Raigorodskii, A.M., On the Chromatic Number of a Space with the Metric ℓ q, Uspekhi Mat. Nauk, 2004, vol. 59, no. 5 (359), pp. 161–162 [Russian Math. Surveys (Engl. Transl.), 2004, vol. 59, no. 5, pp. 973–975].

    Article  MathSciNet  Google Scholar 

  23. Gorskaya, E.S., Mitricheva, I.M., Protasov, V.Yu., and Raigorodskii, A.M., Estimation of the Chromatic Numbers of Euclidean Space by Convex Minimization Methods, Mat. Sb., 2009, vol. 200, no. 6, pp. 3–22 [Sb. Math. (Engl. Transl.), 2009, vol. 200, no. 5–6, pp. 783–801].

    Article  MathSciNet  Google Scholar 

  24. Raigorodskii, A.M. and Shitova, I.M., On the Chromatic Numbers of Real and Rational Spaces with Real or Rational Forbidden Distances, Mat. Sb., 2008, vol. 199, no. 4, pp. 107–142 [Sb. Math. (Engl. Transl.), 2008, vol. 199, no. 3–4, pp. 579–612].

    Article  MathSciNet  Google Scholar 

  25. Moshchevitin, N.G. and Raigorodskii, A.M., Colorings of the Space ℝn with Several Forbidden Distances, Mat. Zametki, 2007, vol. 81, no. 5, pp. 733–743 [Math. Notes (Engl. Transl.), 2007, vol. 81, no. 5–6, pp. 656–664].

    Article  MathSciNet  Google Scholar 

  26. Raigorodskii, A.M., On the Chromatic Number of a Space with Two Forbidden Distances, Dokl. Akad. Nauk, 2006, vol. 408, no. 5, pp. 601–604 [Dokl. Math. (Engl. Transl.), 2006, vol. 73, no. 3, pp. 417–420].

    MathSciNet  Google Scholar 

  27. Raigorodskii, A.M., On Dimensionality in the Borsuk Problem, Uspekhi Mat. Nauk, 1997, vol. 52, no. 6, pp. 181–182 [Russian Math. Surveys (Engl. Transl.), 1997, vol. 52, no. 6, pp. 1324–1325].

    Article  MathSciNet  Google Scholar 

  28. Raigorodskii, A.M., On a Bound in the Borsuk Problem, Uspekhi Mat. Nauk, 1999, vol. 54, no. 2, pp. 185–186 [Russian Math. Surveys (Engl. Transl.), 1999, vol. 54, no. 2, pp. 453–454].

    Article  MathSciNet  Google Scholar 

  29. Raigorodskii, A.M., Three Lectures on the Borsuk Partition Problem, Surveys in Contemporary Mathematics, Young, N. and Choi, Y., Eds., London Math. Soc. Lect. Note Ser., vol. 347. Cambridge: Cambridge Univ. Press, 2007, pp. 202–248.

    Chapter  Google Scholar 

  30. Raigorodskii, A.M., Around the Borsuk Conjecture, Sovrem. Mat. Fundam. Napravl., 2007, vol. 23, pp. 147–164 [J. Math. Sci. (N.Y.) (Engl. Transl.), 2007, vol. 154, no. 4, pp. 604–623].

    Google Scholar 

  31. Raigorodskii, A.M., Counterexamples to Borsuk’s Conjecture on Spheres of Small Radius, Dokl. Akad. Nauk, 2010, vol. 434, no. 2, pp. 161–163 [Dokl. Math. (Engl. Transl.), 2010, vol. 82, no. 2, pp. 719–721].

    MathSciNet  Google Scholar 

  32. Raigorodskii, A.M., Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, Pach, J., Ed., Berlin: Springer, 2013, pp. 429–460.

    Chapter  Google Scholar 

  33. Mikhailov, K.A. and Raigorodskii, A.M., On the Ramsey Numbers for Complete Distance Graphs with Vertices in {0, 1}n, Mat. Sb., 2009, vol. 200, no. 12, pp. 63–80 [Sb. Math. (Engl. Transl.), 2009, vol. 200, no. 11–12, pp. 1789–1806].

    Article  MathSciNet  Google Scholar 

  34. Yarmukhametov, A.R., Gigantic Component in Random Distance Graphs of Special Form, Mat. Zametki, 2012, vol. 92, no. 3, pp. 463–480 [Math. Notes (Engl. Transl.), 2012, vol. 92, no. 3–4, pp. 426–441].

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Mechanics and Mathematics, Lomonosov Moscow State University, Moscow, Russia

    S. N. Popova

Authors
  1. S. N. Popova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. N. Popova.

Additional information

Original Russian Text © S.N. Popova, 2014, published in Problemy Peredachi Informatsii, 2014, Vol. 50, No. 1, pp. 64–86.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Popova, S.N. Zero-one law for random distance graphs with vertices in {−1, 0, 1}n . Probl Inf Transm 50, 57–78 (2014). https://doi.org/10.1134/S0032946014010049

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1134/S0032946014010049

Keywords

Search

Navigation