|
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
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.
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
Linking options:
https://www.mathnet.ru/eng/sm8344https://doi.org/10.1070/SM2015v206n10ABEH004498 https://www.mathnet.ru/eng/sm/v206/i10/p3
|
Statistics & downloads: |
Abstract page: | 965 | Russian version PDF: | 440 | English version PDF: | 54 | References: | 68 | First page: | 43 |
|