Improved bounds for randomly colouring simple hypergraphs

MaRDI QIDQ6390820zbMATH OpenFDO

Authors Weiming Feng, Heng Guo, Jiaheng Wang

Publication date 11 February 2022

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 $kgeqfrac20(1+delta)delta$ and $qgeq100Delt{a}^{frac2+deltak-4/delta-4}$, the running time of our algorithm is $ildeO(mathrmpoly(Deltak)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(logn)$ colours unlike the work of Frieze and Anastos (2017).

This page was built for publication: Improved bounds for randomly colouring simple hypergraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390820)