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 g e q 3

.

Full work available at URL: https://arxiv.org/abs/1905.04461

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (1)

This page was built for publication: DP-colorings of uniform hypergraphs and splittings of Boolean hypercube into faces