Sbornik: Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Sb.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Sbornik: Mathematics, 2015, Volume 206, Issue 10, Pages 1340–1374
DOI: https://doi.org/10.1070/SM2015v206n10ABEH004498
(Mi sm8344)
 

This article is cited in 28 scientific papers (total in 28 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
References:
Abstract: This work is concerned with the Nelson-Hadwiger classical\linebreak problem of finding the chromatic numbers of distance graphs in Rn. Most consideration is given to the class of graphs G(n,r,s)=(V(n,r),E(n,r,s)) defined as follows:
V(n,r)={x=(x1,,xn):xi{0,1},x1++xn=r},E(n,r,s)={{x,y:(x,y)=s}},
where (x,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 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 rs is a prime power and r2s+1, the order of growth of α(G(G(n,r,s),p)) and χ(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
НШ-2519.2012.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.
Received: 10.02.2014 and 12.12.2014
Bibliographic databases:
Document Type: Article
UDC: 519.179.4
MSC: Primary 05C80; Secondary 05C15, 05C69, 05D10
Language: English
Original paper language: Russian
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”, Sb. Math., 206:10 (2015), 1340–1374
Citation in format AMSBIB
\Bibitem{BogGusPya15}
\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 Sb. Math.
\yr 2015
\vol 206
\issue 10
\pages 1340--1374
\mathnet{http://mi.mathnet.ru/eng/sm8344}
\crossref{https://doi.org/10.1070/SM2015v206n10ABEH004498}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3438562}
\zmath{https://zbmath.org/?q=an:1331.05191}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2015SbMat.206.1340B}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000367229400001}
\elib{https://elibrary.ru/item.asp?id=24850568}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84953283845}
Linking options:
  • https://www.mathnet.ru/eng/sm8344
  • https://doi.org/10.1070/SM2015v206n10ABEH004498
  • https://www.mathnet.ru/eng/sm/v206/i10/p3
  • This publication is cited in the following 28 articles:
    1. Random Struct Algorithms, 62:1 (2023), 3  crossref
    2. A. M. Raigorodskii, V. S. Karas, “Asymptotics of the Independence Number of a Random Subgraph of the Graph G(n,r,<s)”, Math. Notes, 111:1 (2022), 124–131  mathnet  crossref  crossref  mathscinet  isi
    3. D. A. Zakharov, “Chromatic Numbers of Some Distance Graphs”, Math. Notes, 107:2 (2020), 238–246  mathnet  crossref  crossref  mathscinet  isi  elib
    4. 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
    5. Mohar B., Wu H., “Fractional Chromatic Number of a Random Subgraph”, J. Graph Theory, 95:3 (2020), 467–472  crossref  mathscinet  isi  scopus
    6. M. Alishahi, A. Taherkhani, “On the random version of the era's matching conjecture”, Discret Appl. Math., 254 (2019), 1–9  crossref  mathscinet  zmath  isi  scopus
    7. 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  mathscinet  isi  elib
    8. A. Kupayskii, “Degree versions of theorems on intersecting families via stability”, J. Comb. Theory Ser. A, 168 (2019), 272–287  crossref  mathscinet  isi  scopus
    9. S. Kiselev, A. Kupavskii, “Sharp bounds for the chromatic number of random kneser graphs”, Acta Math. Univ. Comen., 88:3 (2019), 861–865  mathscinet  isi
    10. M. M. Pyaderkin, “On the chromatic number of random subgraphs of a certain distance graph”, Discret Appl. Math., 267 (2019), 209–214  crossref  mathscinet  zmath  isi
    11. M. Alishahi, H. Hajiabolhassan, “Chromatic number of random Kneser hypergraphs”, J. Combin. Theory Ser. A, 154 (2018), 1–20  crossref  mathscinet  zmath  isi  scopus
    12. A. S. Gusev, “Clique numbers of random subgraphs of some distance graphs”, Problems Inform. Transmission, 54:2 (2018), 165–175  mathnet  crossref  isi  elib
    13. A. Kupavskii, “Random Kneser graphs and hypergraphs”, Electron. J. Comb., 25:4 (2018), P4.52, 16 pp.  mathscinet  zmath  isi
    14. 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
    15. 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
    16. 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
    17. A. M. Raigorodskii, “On the stability of the independence number of a random subgraph”, Dokl. Math., 96:3 (2017), 628–630  crossref  crossref  mathscinet  zmath  isi  elib  scopus
    18. 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
    19. L. Iskhakov, M. Mironov, “Diameters of Random Distance Graphs”, J Math Sci, 227:4 (2017), 407  crossref
    20. 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
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Statistics & downloads:
    Abstract page:1027
    Russian version PDF:460
    English version PDF:94
    References:81
    First page:43
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025