Speaker: Hemanshu Kaul (IIT)
Title: DP-coloring of graphs from random covers
Abstract: DP-coloring (also called correspondence coloring) of graphs is a generalization of list coloring that has been widely studied since its introduction by Dvo\v{r}\'{a}k and Postle in 2015. Intuitively, DP-coloring generalizes list coloring by allowing the colors that are identified as the same to vary from edge to edge. Formally, DP-coloring of a graph $G$ is equivalent to an independent transversal in an auxiliary structure called a DP-cover of $G$ (that arises from related concept of covering maps in topology).
In this talk, we will discuss the notion of random DP-covers (equivalently, random lifts introduced by Amit and Linial in 2002) and study the behavior of DP-coloring from such random covers. We will describe results about the probability that a graph is or is not DP-colorable from a random cover. These results support the following threshold behavior on random $k$-fold DP-covers as $\rho$ goes to infinity where $\rho$ is the maximum density of a graph: graphs are non-DP-colorable with high probability when $k$ is sufficiently smaller than $\rho/\ln\rho$, and graphs are DP-colorable with high probability when $k$ is sufficiently larger than $\rho/\ln\rho$. Our results depend on $\rho$ growing fast enough and imply a sharp threshold for dense enough graphs. For sparser graphs, we analyze DP-colorability in terms of degeneracy and show bounds on cover size $k$ that are within a factor of 2 of each other, for density at least polylog in number of vertices. We also prove fractional DP-coloring analogs of some of these results.
This is joint work with A. Bernshteyn, D. Dominik, and J. Mudrock.