The chromatic number of random Borsuk graphs. Issue 3 (5th November 2019)

• Record Type: Journal Article
• Authors: Kahle, Matthew; Martinez‐Figueroa, Francisco
• Is Part Of: Random structures & algorithms. Volume 56:Issue 3(2020)
• Page Start: 838
• Page End: 850
• Publication Date: 2019-11-05
• Subjects: random graphs -- topological combinatorics -- Borsuk–Ulam; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20897
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : We study a model of random graph where vertices are n i.i.d. uniform random points on the unit sphere S d in R d + 1, and a pair of vertices is connected if the Euclidean distance between them is at least 2− ϵ . We are interested in the chromatic number of this graph as n tends to infinity. It is not too hard to see that if ϵ >0 is small and fixed, then the chromatic number is d +2 with high probability. We show that this holds even if ϵ →0 slowly enough. We quantify the rate at which ϵ can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik–Schnirelman–Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor—if ϵ →0 faster than this, we show that the graph is ( d +1)‐colorable with high probability.25