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 that the lower bound on edges in a non-2-DP-colorable $k$-uniform hypergraph is equal to $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\ge 3$.

The previous versions of paper contains a significant error

Cited by in corpus (1)

• On the number of partitions of the hypercube ${\mathbf{Z}}_q^n$ into large subcubes