论文标题
改进的界限，以随机着色简单超图
Improved bounds for randomly colouring simple hypergraphs
论文作者
论文摘要
我们研究了在$ k $ - 均匀的简单超图中对几乎均匀的$ q $颜色进行采样的问题，并具有最高度$δ$。对于任何$Δ> 0 $，如果$ k \ geq \ frac {20（1+δ）Δ$和$ q \ geq Q \ geq Q Q \ geq Q Q \ frac {\ frac {2+δ} {k-4/δ-4}} $，我们的algorithm的运行时间，我们的algorithm is $ \ tilde是$ \ tilde {o \ tirde {cd cd cd cd c cd c cyt c c cyt c c c c cd c c c cytrmmm n^{1.01}）$，其中$ n $是顶点的数量。我们的结果所需的颜色比以前的一般超图（Jain，Pham和Voung，2021; He，Sun和Wu，2021）的颜色少，并且不需要$ω（\ log n）$颜色，与Frieze and Anastos（2017年）不同。
We study the problem of sampling almost uniform proper $q$-colourings in $k$-uniform simple hypergraphs with maximum degree $Δ$. For any $δ> 0$, if $k \geq\frac{20(1+δ)}δ$ and $q \geq 100Δ^{\frac{2+δ}{k-4/δ-4}}$, the running time of our algorithm is $\tilde{O}(\mathrm{poly}(Δ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 $Ω(\log n)$ colours unlike the work of Frieze and Anastos (2017).
