RUS  ENG
Full version
JOURNALS // Matematicheskii Sbornik // Archive

Mat. Sb., 2015 Volume 206, Number 10, Pages 3–36 (Mi sm8344)

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


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

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025