DP-Colorings of Uniform Hypergraphs and Splittings of Boolean Hypercube into Faces

Abstract

We develop a connection between DP-colorings of $k$-uniform hypergraphs of order $n$ and coverings of $n$-dimensional Boolean hypercube by pairs of antipodal $(n-k)$-dimensional faces. Bernshteyn and Kostochka established a lower bound on the number of edges in a non-2-DP-colorable $k$-uniform hypergraph namely, $2^{k-1}$ for odd $k$ and $2^{k-1}+1$ for even $k.$ They proved that these bounds are tight for $k=3,4$. In this paper, we prove that the bound is achieved for all odd $k\geq 3$.