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 $\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)=\bigl\{\mathbf{x}=(x_1,\dots,x_n) : x_i\in\{0, 1\},\, x_1+\dots+x_n=r\bigr\}, \\ E(n,r,s)=\bigl\{\{\mathbf{x}, \mathbf{y}: (\mathbf{x}, \mathbf{y})=s\}\bigr\}, \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
НШ-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
Russian version:
Matematicheskii Sbornik, 2015, Volume 206, Number 10, Pages 3–36
DOI: https://doi.org/10.4213/sm8344
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”, Mat. Sb., 206:10 (2015), 3–36; 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 Mat. Sb.
\yr 2015
\vol 206
\issue 10
\pages 3--36
\mathnet{http://mi.mathnet.ru/sm8344}
\crossref{https://doi.org/10.4213/sm8344}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3438562}
\zmath{https://zbmath.org/?q=an:06537979}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2015SbMat.206.1340B}
\elib{https://elibrary.ru/item.asp?id=24850568}
\transl
\jour Sb. Math.
\yr 2015
\vol 206
\issue 10
\pages 1340--1374
\crossref{https://doi.org/10.1070/SM2015v206n10ABEH004498}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000367229400001}
\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:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математический сборник Sbornik: Mathematics
    Statistics & downloads:
    Abstract page:965
    Russian version PDF:440
    English version PDF:54
    References:68
    First page:43
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024