Independence numbers and chromatic numbers of the random subgraphs of some distance graphs

L. I. Bogolubsky ; A. S. Gusev ; M. M. Pyaderkin ; A. M. Raigorodskii

Sbornik. Mathematics, Tome 206 (2015) no. 10, pp. 1340-1374

Résumé

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.

Détail

Keywords: random graph, distance graph, independence number, chromatic number.