DP-colorings of hypergraphs

• Published in: European journal of combinatorics 2019-05, Vol.78, p.134-146
• Main Authors: Bernshteyn, Anton, Kostochka, Alexandr
• Format: Article
• Language: English
• ISSN: 0195-6698; 1095-9971
• DOI: 10.1016/j.ejc.2019.01.011

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