General information
Latest issue
Forthcoming papers
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Mat. Sb.:

Personal entry:
Save password
Forgotten password?

Mat. Sb., 2013, Volume 204, Number 4, Pages 49–78 (Mi msb7830)  

This article is cited in 18 scientific papers (total in 18 papers)

Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size

E. E. Demekhina, A. M. Raigorodskiiab, O. I. Rubanovab

a M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Moscow Institute of Physics and Technology (State University)

Abstract: It is established that there exist sequences of distance graphs $G_n\subset\mathbb R^n$, with chromatic numbers which grow exponentially, but, at the same time, without cliques or cycles of a given size.
Bibliography: 42 titles.

Keywords: distance graph, random graph, chromatic number, clique, cycle.

Funding Agency Grant Number
Russian Foundation for Basic Research 12-01-00683
Ministry of Education and Science of the Russian Federation НШ-2519.2012.1

Author to whom correspondence should be addressed


Full text: PDF file (732 kB)
References: PDF file   HTML file

English version:
Sbornik: Mathematics, 2013, 204:4, 508–538

Bibliographic databases:

UDC: 519.112.4+519.174+519.176
MSC: 05C15, 05C35, 05D10
Received: 14.12.2010 and 09.12.2011

Citation: E. E. Demekhin, A. M. Raigorodskii, O. I. Rubanov, “Distance graphs having large chromatic numbers and containing no cliques or cycles of a given size”, Mat. Sb., 204:4 (2013), 49–78; Sb. Math., 204:4 (2013), 508–538

Citation in format AMSBIB
\by E.~E.~Demekhin, A.~M.~Raigorodskii, O.~I.~Rubanov
\paper Distance graphs having large chromatic numbers and containing no cliques or cycles of a~given size
\jour Mat. Sb.
\yr 2013
\vol 204
\issue 4
\pages 49--78
\jour Sb. Math.
\yr 2013
\vol 204
\issue 4
\pages 508--538

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. A. B. Kupavskii, A. M. Raigorodskii, “Obstructions to the realization of distance graphs with large chromatic numbers on spheres of small radii”, Sb. Math., 204:10 (2013), 1435–1479  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    2. A. B. Kupavskii, “Explicit and probabilistic constructions of distance graphs with small clique numbers and large chromatic numbers”, Izv. Math., 78:1 (2014), 59–89  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    3. S. N. Popova, “Zero-one laws for random distance graphs with vertices in $\{0,1\}^n$”, Dokl. Math., 90:2 (2014), 535–538  crossref  crossref  zmath  isi  elib  elib  scopus
    4. V. V. Utkin, “Hamiltonian Paths in Distance Graphs”, Math. Notes, 97:6 (2015), 919–929  mathnet  crossref  crossref  mathscinet  isi  elib
    5. M. M. Pyaderkin, “On the stability of the ErdH os-Ko-Rado theorem”, Dokl. Math., 91:3 (2015), 290–293  crossref  crossref  mathscinet  zmath  isi  elib  elib  scopus
    6. Ph. A. Pushnyakov, “A new estimate for the number of edges in induced subgraphs of a special distance graph”, Problems Inform. Transmission, 51:4 (2015), 371–377  mathnet  crossref  isi  elib
    7. M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of a Distance Graph”, Math. Notes, 99:2 (2016), 312–319  mathnet  crossref  crossref  mathscinet  isi  elib
    8. S. N. Popova, “Zero-one law for random subgraphs of some distance graphs with vertices in $\mathbb Z^n$”, Sb. Math., 207:3 (2016), 458–478  mathnet  crossref  crossref  mathscinet  adsnasa  isi  elib
    9. Ph. Pushnyakov, “On the Number of Edges in Induced Subgraphs of a Special Distance Graph”, Math. Notes, 99:4 (2016), 545–551  mathnet  crossref  crossref  mathscinet  isi  elib
    10. S. N. Popova, “Zero-one laws for random graphs with vertices in a Boolean cube”, Siberian Adv. Math., 27:1 (2017), 26–75  mathnet  crossref  crossref  mathscinet  elib
    11. A. Sagdeev, “Lower Bounds for the Chromatic Numbers of Distance Graphs with Large Girth”, Math. Notes, 101:3 (2017), 515–528  mathnet  crossref  crossref  mathscinet  isi  elib
    12. A. Sagdeev, “The Chromatic Number of Space with Forbidden Regular Simplex”, Math. Notes, 102:4 (2017), 541–546  mathnet  crossref  crossref  mathscinet  isi  elib
    13. A. Sokolov, “On the Chromatic Numbers of Rational Spaces”, Math. Notes, 103:1-2 (2018), 111–117  mathnet  crossref  crossref  mathscinet  isi  elib
    14. A. V. Berdnikov, “Chromatic numbers of distance graphs with several forbidden distances and without cliques of a given size”, Problems Inform. Transmission, 54:1 (2018), 70–83  mathnet  crossref  isi  elib
    15. Yu. A. Demidovich, “Distance Graphs with Large Chromatic Number and without Cliques of Given Size in the Rational Space”, Math. Notes, 106:1 (2019), 38–51  mathnet  crossref  crossref  isi  elib
    16. A. A. Sagdeev, “On a Frankl–Wilson Theorem”, Problems Inform. Transmission, 55:4 (2019), 376–395  mathnet  crossref  crossref  isi  elib
    17. Sagdeev A.A. Raigorodskii A.M., “On a Frankl-Wilson Theorem and Its Geometric Corollaries”, Acta Math. Univ. Comen., 88:3 (2019), 1029–1033  mathscinet  isi
    18. Ph. A. Pushnyakov, A. M. Raigorodskii, “Estimate of the Number of Edges in Special Subgraphs of a Distance Graph”, Math. Notes, 107:2 (2020), 322–332  mathnet  crossref  crossref  isi  elib
  • Математический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:515
    Full text:187
    First page:64

    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020