This article is cited in
29 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)=\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.
UDC:
519.179.4
MSC: Primary
05C80; Secondary
05C15,
05C69,
05D10 Received: 10.02.2014 and 12.12.2014
DOI:
10.4213/sm8344