DP-colorings of hypergraphs

Classical problems in hypergraph coloring theory are to estimate the minimum number of edges, m ₂ (r) (respectively, m ₂ ^∗ (r)), in a non-2-colorable r-uniform (respectively, r-uniform and simple) hypergraph. The best currently known bounds are c⋅r∕logr⋅2 ^r ⩽m ₂ (r)⩽C⋅r ² ⋅2 ^r andc ^′ ⋅r ^−ε ⋅4 ^r ⩽m ₂ ^∗ (r)⩽C ^′ ⋅r ⁴ ⋅4 ^r ,for any fixed ε>0 and some c, c ^′ , C, C ^′ >0 (where c ^′ may depend on ε). 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 m˜ ₂ (r) (respectively, m˜ ₂ ^∗ (r)) denote the minimum number of edges in a non-2-DP-colorable r-uniform (respectively, r-uniform and simple) hypergraph. By definition, m˜ ₂ (r)⩽m ₂ (r) and m˜ ₂ ^∗ (r)⩽m ₂ ^∗ (r). While the proof of the bound m ₂ ^∗ (r)=Ω(r ⁻³ 4 ^r ) due to Erdős and Lovász also works for m˜ ₂ ^∗ (r), we show that the trivial lower bound m˜ ₂ (r)⩾2 ^r−1 is asymptotically tight, i.e., m˜ ₂ (r)⩽(1+o(1))2 ^r−1 . On the other hand, when r⩾2 is even, we prove that the lower bound m˜ ₂ (r)⩾2 ^r−1 is not sharp, i.e., m˜ ₂ (r)⩾2 ^r−1 +1. Whether this result holds for infinitely many odd values of r remains an open problem. Nevertheless, we conjecture that the difference m˜ ₂ (r)−2 ^r−1 can be arbitrarily large.