2019/01/31 by Matthew Kahle, Francisco Martinez‐Figueroa, Francisco Martinez-Figueroa
Computer Science · Mathematics · #Chromatic scale #Computational Geometry and Mesh Generation #Constant (computer programming) #Euclidean distance #Euclidean geometry #Graph #Limits and Structures in Graph Theory #Random geometric graph #Random graph #Random regular graph #Topological and Geometric Data Analysis #math.AT #math.CO #math.MG #math.PR
paper · pdf · doi:10.1002/rsa.20897
published as Random Struct Alg. 2020; 56: 838-850 · 17 pages. Minor revisions and corrections from v1. References added
openalex created_date 2019/02/21 · arxiv created 2019/08/02 · openalex publication_date 2019/11/05 · arxiv updated 2021/08/27 · openalex updated_date 2026/08/06
We study a model of random graph where vertices are n i.i.d. uniform random points on the unit sphere S d in , 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