Improved bounds for randomly colouring simple hypergraphs

Abstract

We study the problem of sampling almost uniform proper $q$-colourings in $k$-uniform simple hypergraphs with maximum degree $\Delta$. For any $\delta >0$, if $k\ge \frac{20(1+\delta )}{\delta }$ and $q\ge 100{\Delta }^{\frac{2+\delta }{k-4/\delta -4}}$, the running time of our algorithm is $\tilde{O}(\mathrm{poly}(\Delta k)\cdot n^{1.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 $\Omega (\log n)$ colours unlike the work of Frieze and Anastos (2017).