DP-Colorings of Hypergraphs

Abstract

Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, $m_2(r)$ (respectively, $m_2^{\ast }(r)$), in a non-$2$-colorable $r$-uniform (respectively, $r$-uniform and simple) hypergraph. The best currently known bounds are \[c \cdot \sqrt{r/\log r} \cdot 2^r \,\leqslant\, m_2(r) \,\leqslant\, C \cdot r^2 \cdot 2^r \qquad \text{and} \qquad c' \cdot r^{-\varepsilon} \cdot 4^r \,\leqslant\, m_2^\ast(r) \,\leqslant\, C' \cdot r^4 \cdot 4^r,\] for any fixed $\epsilon >0$ and some $c$, $c^{\prime }$, $C$, $C^{\prime }>0$ (where $c^{\prime }$ may depend on $\epsilon$). In this paper we consider the same problems in the context of DP-coloring (also known as correspondence coloring), which is a generalization of list coloring introduced by Dvořák and Postle and related to local conflict coloring studied independently by Fraigniaud, Heinrich, and Kosowski. Let ${\tilde{m}}_2(r)$ (respectively, ${\tilde{m}}_2^{\ast }(r)$) denote the minimum number of edges in a non-$2$-DP-colorable $r$-uniform (respectively, $r$-uniform and simple) hypergraph. By definition, ${\tilde{m}}_2(r)⩽m_2(r)$ and ${\tilde{m}}_2^{\ast }(r)⩽m_2^{\ast }(r)$. While the proof of the bound $m_2^{\ast }(r)=\Omega (r^{-3}{4}^r)$ due to Erdős and Lovász also works for ${\tilde{m}}_2^{\ast }(r)$, we show that the trivial lower bound ${\tilde{m}}_2(r)⩾2^{r-1}$ is asymptotically tight, i.e., ${\tilde{m}}_2(r)⩽(1+o(1))2^{r-1}$. On the other hand, when $r⩾2$ is even, we prove that the lower bound ${\tilde{m}}_2(r)⩾2^{r-1}$ is not sharp, i.e., ${\tilde{m}}_2(r)⩾2^{r-1}+1$. Whether this result holds for any odd values of $r$ remains an open problem. Nevertheless, we conjecture that the difference ${\tilde{m}}_2(r)-2^{r-1}$ can be arbitrarily large.

13 pages; v4: added updated references to recent results of Potapov