2022/02/11 by Feng, Weiming, Guo, Heng, Wang, Jiaheng
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2202.05554
We study the problem of sampling almost uniform proper q-colourings in k-uniform simple hypergraphs with maximum degree Δ. For any δ> 0, if k ≥\frac20(1+δ)δ and q ≥ 100Δ(2+δ)/(k-4/δ-4), the running time of our algorithm is O(poly(Δk)⋅ n1.01), where n is the number of vertices. Our result requires fewer colours than previous results for general hypergraphs (Jain, Pham, and Voung, 2021; He, Sun, and Wu, 2021), and does not require Ω(log n) colours unlike the work of Frieze and Anastos (2017).