2009/01/23 by Alan Frieze, Frieze, Alan, Páll Melsted +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.0901.3699
openalex publication_date 2009/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of constructing a (near) random proper q-colouring of a simple k-uniform hypergraph with n vertices and maximum degree Δ. (Proper in that no edge is mono-coloured and simple in that two edges have maximum intersection of size one). We give conditions on q,Δso that if these conditions are satisfied, Glauber dynamics will converge in O(nlog n) time from a random (improper) start. The interesting thing here is that for k≥ 3 we can take q=o(\D).