Independence numbers and chromatic numbers of the random subgraphs of some distance graphs. (October 2015)

• Record Type: Journal Article
• Authors: Bogolubsky, L. I.; Gusev, A. S.; Pyaderkin, M. M.; Raigorodskii, A. M.
• Is Part Of: Sbornik. Volume 206:Number 10(2015)
• Page Start: 1340
• Page End: 1374
• Publication Date: 2015-10
• Subjects: Primary 05C80 -- Secondary 05C15 -- 05C69 -- 05D10; random graph -- distance graph -- independence number -- chromatic number.; Mathematics -- Periodicals; 510.5
• DOI: 10.1070/SM2015v206n10ABEH004498
• Languages: English
• ISSNs: 1064-5616

Abstract

Abstract: This work is concerned with the Nelson-Hadwiger classical problem of finding the chromatic numbers of distance graphs in . Most consideration is given to the class of graphs defined as follows: where is the Euclidean inner product. In particular, the chromatic number of was recently found by Balogh, Kostochka and Raigorodskii. The objects of the study are the random subgraphs whose edges are independently taken from the set, each with probability . The independence number and the chromatic number of such graphs are estimated both from below and from above. In the case when is a prime power and, the order of growth of and is established. Bibliography: 51 titles.