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., 2015, Volume 206, Number 10, Pages 3–36 (Mi msb8344)  

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

Independence numbers and chromatic numbers of the random subgraphs of some distance graphs

L. I. Bogolubskya, A. S. Guseva, M. M. Pyaderkina, A. M. Raigorodskiiabc

a Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
b Department of Innovations and High Technology, Moscow Institute of Physics and Technology
c Buryat State University, Institute for Mathematics and Informatics

Abstract: This work is concerned with the Nelson-Hadwiger classical\linebreak problem of finding the chromatic numbers of distance graphs in $\mathbb R^n$. Most consideration is given to the class of graphs $G(n, r,s)=(V(n, r), E(n,r,s))$ defined as follows:
\begin{gather*} V(n, r)=\{\mathbf{x}=(x_1,…,x_n) : x_i\in\{0, 1\},  x_1+…+x_n=r\},
E(n,r,s)=\{\{\mathbf{x}, \mathbf{y}: (\mathbf{x}, \mathbf{y})=s\}\}, \end{gather*}
where $(\mathbf{x}, \mathbf{y})$ is the Euclidean inner product. In particular, the chromatic number of $G(n,3,1)$ was recently found by Balogh, Kostochka and Raigorodskii. The objects of the study are the random subgraphs $\mathscr{G}(G(n,r,s), p)$ whose edges are independently taken from the set $E(n,r,s)$, each with probability $p$. The independence number and the chromatic number of such graphs are estimated both from below and from above. In the case when $r-s$ is a prime power and $r\leq 2s+1$, the order of growth of $\alpha(\mathscr{G}(G(n,r,s), p))$ and $\chi(\mathscr{G}(G(n,r,s), p))$ is established.
Bibliography: 51 titles.

Keywords: random graph, distance graph, independence number, chromatic number.

Funding Agency Grant Number
Russian Foundation for Basic Research 12-01-00683
Ministry of Education and Science of the Russian Federation МД-6277.2013.1
This work was supported by the Russian Foundation for Basic Research (grant no. 12-01-00683) and by the Council of the President of the Russian Federation for the Support of Young Russian Scientists and Leading Scientific Schools, grant nos. МД-6277.2013.1 and НШ-2519.2012.1.

Author to whom correspondence should be addressed


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

English version:
Sbornik: Mathematics, 2015, 206:10, 1340–1374

Bibliographic databases:

UDC: 519.179.4
MSC: Primary 05C80; Secondary 05C15, 05C69, 05D10
Received: 10.02.2014 and 12.12.2014

Citation: L. I. Bogolubsky, A. S. Gusev, M. M. Pyaderkin, A. M. Raigorodskii, “Independence numbers and chromatic numbers of the random subgraphs of some distance graphs”, Mat. Sb., 206:10 (2015), 3–36; Sb. Math., 206:10 (2015), 1340–1374

Citation in format AMSBIB
\by L.~I.~Bogolubsky, A.~S.~Gusev, M.~M.~Pyaderkin, A.~M.~Raigorodskii
\paper Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
\jour Mat. Sb.
\yr 2015
\vol 206
\issue 10
\pages 3--36
\jour Sb. Math.
\yr 2015
\vol 206
\issue 10
\pages 1340--1374

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. 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
    2. M. E. Zhukovskii, A. M. Raigorodskii, “Random graphs: models and asymptotic characteristics”, Russian Math. Surveys, 70:1 (2015), 33–81  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib  elib
    3. 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
    4. B. Bollobás, B. P. Narayanan, A. M. Raigorodskii, “On the stability of the Erdős-Ko-Rado theorem”, J. Combin. Theory Ser. A, 137 (2016), 64–78  crossref  mathscinet  zmath  isi  elib  scopus
    5. 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
    6. M. M. Pyaderkin, “Independence Numbers of Random Subgraphs of Distance Graphs”, Math. Notes, 99:4 (2016), 556–563  mathnet  crossref  crossref  mathscinet  isi  elib
    7. A. Kupavskii, “On random subgraphs of Kneser and Schrijver graphs”, J. Combin. Theory Ser. A, 141 (2016), 8–15  crossref  mathscinet  zmath  isi  scopus
    8. M. M. Pyaderkin, A. M. Raigorodskii, “On random subgraphs of Kneser graphs and their generalizations”, Dokl. Math., 94:2 (2016), 547–549  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    9. A. M. Raigorodskii, “Combinatorial geometry and coding theory*”, Fund. Inform., 145:3 (2016), 359–369  crossref  mathscinet  zmath  isi  scopus
    10. M. M. Pyaderkin, “On the stability of some Erdős–Ko–Rado type results”, Discrete Math., 340:4 (2017), 822–831  crossref  mathscinet  zmath  isi  scopus
    11. D. D. Cherkashin, A. M. Raigorodskii, “on the Chromatic Numbers of Low-Dimensional Spaces”, Dokl. Math., 95:1 (2017), 5–6  crossref  crossref  mathscinet  zmath  isi  elib  elib  scopus
    12. S. G. Kiselev, A. M. Raigorodskii, “On the chromatic number of a random subgraph of the Kneser graph”, Dokl. Math., 96:2 (2017), 475–476  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    13. A. M. Raigorodskii, “On the stability of the independence number of a random subgraph”, Dokl. Math., 96:3 (2017), 628–630  crossref  crossref  zmath  isi  elib  scopus
    14. N. M. Derevyanko, S. G. Kiselev, “Independence numbers of random subgraphs of some distance graph”, Problems Inform. Transmission, 53:4 (2017), 307–318  mathnet  crossref  isi  elib
    15. M. Alishahi, H. Hajiabolhassan, “Chromatic number of random Kneser hypergraphs”, J. Combin. Theory Ser. A, 154 (2018), 1–20  crossref  mathscinet  zmath  isi  scopus
    16. A. S. Gusev, “Clique numbers of random subgraphs of some distance graphs”, Problems Inform. Transmission, 54:2 (2018), 165–175  mathnet  crossref  isi  elib
    17. A. Kupavskii, “Random Kneser graphs and hypergraphs”, Electron. J. Comb., 25:4 (2018), P4.52, 16 pp.  zmath  isi
    18. Alishahi M., Taherkhani A., “On the Random Version of the Era'S Matching Conjecture”, Discret Appl. Math., 254 (2019), 1–9  crossref  mathscinet  zmath  isi  scopus
    19. M. M. Pyaderkin, “On Threshold Probability for the Stability of Independent Sets in Distance Graphs”, Math. Notes, 106:2 (2019), 274–285  mathnet  crossref  crossref  isi  elib
    20. D. A. Zakharov, “O khromaticheskikh chislakh nekotorykh distantsionnykh grafov”, Matem. zametki, 107:2 (2020), 210–220  mathnet  crossref
    21. F. A. Pushnyakov, A. M. Raigorodskii, “Otsenka chisla reber v osobykh podgrafakh nekotorogo distantsionnogo grafa”, Matem. zametki, 107:2 (2020), 286–298  mathnet  crossref
  • Математический сборник Sbornik: Mathematics (from 1967)
    Number of views:
    This page:449
    Full text:81
    First page:43

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