ARTICLE
TITLE

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

SUMMARY

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

 Articles related